Posted by: holdenlee | September 13, 2012

Putnam 2011/A2 and writing understandable solutions


In this post, I’ll give the motivation and solutions to A2 from last year’s Putnam exam, and mention what strategy we can learn from it. Finally, I’ll use this as an example of how to write good solutions in curriculum.

A2. Let a_1,a_2,\ldots and b_1,b_2,\ldots be sequences of positive real numbers such that a_1=b_1=1 and b_n=b_{n-1}a_n-2 for n=2,3,\ldots Assume that the sequence (b_j) is bounded. Prove that

S=\sum_{n=1}^{\infty} \frac{1}{a_1\cdots a_n}.

converges, and evaluate S.

Let’s solve A2. This looks crazy. A sum which converges to the same thing no matter what we choose for infinitely many terms of the sequence b_j, as long as the sequence is bounded? If we don’t know what to do, at least we can massage the problem into a nicer form: Since only the a_j appear in the sum, and (b_j) is the sequence we have information about, let’s write the a_j in terms of the b_j. From b_n=b_{n-1}a_n-2 we have

a_n=\frac{b_n+2}{b_{n-1}}. \qquad(1)

Can we find guess what S needs to be? The problem suggests it’s always the same, so we’ll pick 1=b_1=b_2=\cdots. Then a_n=3 for n\ge 2, and we get that S is a geometric series.

S=1+\sum_{n=1}^{\infty} \frac{1}{3^n}=\boxed{\frac{3}{2}}.

We conjecture that S is always equal to \frac{3}{2}.

Now what? Since the clock is ticking and we can’t think of anything to do, let’s just start adding up a few terms. Let S_m=\sum_{n=1}^m \frac{1}{a_1\cdots a_n} be the mth partial sum. Noting a_1=b_1=1 and using (1), we put everything except the first term over a common denominator.

S_1=1.

S_2=1+\frac{1}{b_2+2}.

S_3=1+\frac{1}{b_2+2}+\frac{1}{b_2+2}\frac{b_2}{b_3+2}=1+\frac{(b_3+2)+b_2}{(b_2+2)(b_3+2)}.

This looks complicated, but let’s try to compare it to \frac{3}{2}. We rewrite

S_3=1+\frac{\frac{1}{2}(b_2+2)(b_3+2)-\frac{1}{2}b_2b_3}{(b_2+2)(b_3+2)}=\frac{3}{2}-\frac{1}{2}\frac{b_2b_3}{(b_2+2)(b_3+2)}.

OK, let’s do the same for n=4. We omit some of the steps; do them yourself.

S_4=1+\frac{1}{b_2+2}+\frac{1}{b_2+2}\frac{b_2}{b_3+2}+\frac{1}{b_2+2}\frac{b_2}{b_3+2}\frac{b_3}{b_4+2}=\frac{3}{2}-\frac{1}{2}\frac{b_2b_3b_4}{(b_2+2)(b_3+2)(b_4+2)}.

We see a pattern! (What is it?) Even S_2 fits into this pattern, because we have S_2=\frac{3}{2}-\frac{1}{2}\frac{b_2}{b_2+2}. Now, given that this pattern holds, we need to show that the subtracted term goes to 0. Since we’re multiplying numbers of the form \frac{x}{x+2} together, the subtracted term would go to 0 if \frac{x}{x+2} has absolute value smaller than 1, and is bounded away from 1, which we can check. We are now ready to write a formal proof. (I’ll write a complete proof, at the cost of some repetition with the above material.)

Proof of A2.

The equation b_n=b_{n-1}a_n-2 gives us

a_n=\frac{b_n+2}{b_{n-1}}. \qquad(1)

Lemma 1 (Formula for partial sum). For any n\ge 2,

{}S_m:=\sum_{n=1}^m \frac{1}{a_1\cdots a_n}=\frac{3}{2}-\frac{1}{2}\frac{b_2\cdots b_m}{(b_2+2)\cdots (b_m+2)}.

Proof of Lemma 1. We proceed by induction. For m=2, we find by computation S_2=1+\frac{1}{b_2+2}=\frac{3}{2}-\frac{1}{2}\frac{b_2}{b_2+2}. Now suppose the lemma holds for m; we show it holds for m+1. We have, using the induction hypothesis and (1) (noting a_1=1) that

S_{m+1}=S_m+\frac{1}{a_1\cdots a_{m+1}}=\frac{3}{2}-\frac{1}{2}\frac{b_2\cdots b_m}{(b_2+2)\cdots (b_m+2)}+\frac{b_2\cdots b_n}{(b_2+2)\cdots (b_{m+1}+2)}.

=\frac{3}{2}+\frac{-\frac{1}{2}b_2\cdots b_m(b_{m+1}+2)+b_2\cdots b_m}{(b_2+2)\cdots (b_m+2)(b_{m+1}+2)}=\frac{3}{2}-\frac{1}{2}\frac{b_2\cdots b_m}{(b_2+2)\cdots (b_m+2)}.

This finishes the induction step and the proof.  [Side note: if you prefer can also rewrite the sum as a “telescoping sum” to prove this lemma.] \square

Lemma 2 (Bound for error term). Let C be a positive constant, and suppose 0<x<C. (NOTE THIS IS WHERE WE USE THE BOUNDEDNESS CONDITION.) Then \left|\frac{x}{x+2}\right|< \frac{C}{C+2}<1.

Proof of Lemma 2. Note f(x):=\frac{x}{x+2}=1-\frac{2}{x+2} is strictly increasing for x>0 (as \frac{2}{x+2} is decreasing). Hence 0<x<C gives f(x)<f(C)=\frac{C}{C+2}<1\square

Finishing the proof. Let R_m:=\frac{1}{2}\frac{b_2\cdots b_m}{(b_2+2)\cdots (b_m+2)}. Since (b_j) is bounded, we have for some C>0 that b_j<C for all j. Then by lemma 2 on b_1,\ldots, b_m, we have {}0<R_m<\varepsilon_m where $latex \varepsilon_m=\frac{1}{2}\left(\frac{C}{C+2}\right)^{m-1}$. By lemma 1, S_m=\frac{3}{2}-R_m, so this gives

\frac{3}{2}-\varepsilon_m<S_m<\frac{3}{2}.

Note also that \lim_{m\to \infty}\varepsilon_m=0. Hence S=\lim_{m\to \infty} S_m=\frac{3}{2}.

Discussion. What do we learn from this problem?

Key Concept:Try some small cases and look for a pattern. If you need to prove something about a sequence or series, compute the first few terms.

This strategy should NOT be underestimated! The biggest trap in this problem is to immediately jump to keep trying some “fancy tricks” involving sequences and NOT actually computing terms. By contrast when we do the stupid smart thing and actually compute a few small cases, we solve the problem!

A meta-comment on this writeup: Note how I wrote this post. I go through the actual reasoning that a person thinking about this problem would go through, including the questions and doubts he would ask himself along the way. This serves as the motivation. Then I write a formal, well-organized proof (I believe that besides mathematical correctness, the biggest factor in deciding a Putnam score is how well-organized the proof is). Note I delimit the two main steps of the proof, label them, even indicate where I used the conditions. Although this may be overkill, it guarantees a score of 10, rather than a 9 or a 1. Finally, I give a key concept behind the problem–the take-away message, so to speak, even if you forget everything else about the problem. (Of course, on an actual exam, all you would write is the proof.)

This is how you should write solutions that you expect others to learn from. I followed this model when I wrote the geometry curriculum over the summer, imagine that I’m explaining to a student how to solve the problem step-by-step. Even within a sentence, I always put the reason before facts. For example, I don’t say \triangle ABC \cong \triangle DEF by SAS Congruence, I say: because of SAS Congruence, \triangle ABC \cong \triangle DEF. Now you may say this is nitpicky, and indeed we wouldn’t need be so nitpicky in higher math, but if you’re trying to write a curriculum for the average 10th grader who may get discouraged from seeing a bit too many symbols in a equation without knowing why, then these little things matter. And even if you’re smart, the solution still usually reads better. (And even in higher math, I always find it annoying when I stare at a equation for a while and then realize that the reason that it’s true is given below the equation…)

 A single number in the solutions at the back of a textbook or a terse sentence does little to help a student who is having trouble with a problem. Even a few words of motivation before a proof or solution does a great deal to help the student, and this is something I think a lot of textbooks do not do. If you just went and looked at the proof that I wrote here, without the motivation, you might ask: where the heck did this formula come from?!

As a further example, the AMC (American Math Competition) releases a solution guide to their exams, which they fit on a fold-out brochure. Mathew Crawford writes his own solutions to the problems, and his solutions for the AMC10B, for instance, span 23 pages. (See here.) Although it is longer, it is easier to read, full of diagrams, and doesn’t leave a student asking, “How did they come up with that?”

When writing a solution, give reasons and motivations before facts, and discuss the key concept/strategy at the end–some takeaway message that the reader can apply in greater generality.

Advertisements

Responses

  1. I recently began teaching Calculus for the first time. We encountered a proof exercise where the authors had provided an answer of the annoying type you describe above: the proof is there and after an extra hour of individual study I was able to return to my class and present it in a way they could understand. Of course, by then, we were all ticked off at the presentation itself.

    You’re absolutely right that a few extra lines of text setting up the process are invaluable to getting secondary students to appreciate what they see and understand. Without that, even the relatively strong and well-motivated students I teach will disengage.

    http://poliquinmath.net

  2. Very helpful! I was actually looking for something like this. I’ve found a few solutions to this problem, but the motivation for the statement of the lemma was never made explicit.


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: