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 and be sequences of positive real numbers such that and for Assume that the sequence is bounded. Prove that

converges, and evaluate .

**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 , 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 appear in the sum, and is the sequence we have information about, let’s write the in terms of the . From we have

Can we find guess what needs to be? The problem suggests it’s always the same, so we’ll pick . Then for , and we get that is a geometric series.

We conjecture that is always equal to .

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 be the th partial sum. Noting and using (1), we put everything except the first term over a common denominator.

This looks complicated, but let’s try to compare it to . We rewrite

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

We see a pattern! (What is it?) Even fits into this pattern, because we have . 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 together, the subtracted term would go to 0 if 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 gives us

**Lemma 1 (Formula for partial sum). **For any ,

**Proof of Lemma 1.** We proceed by induction. For , we find by computation . Now suppose the lemma holds for ; we show it holds for . We have, using the induction hypothesis and (1) (noting ) that

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.]

**Lemma 2 (Bound for error term).** Let be a positive constant, and suppose . (NOTE THIS IS WHERE WE USE THE BOUNDEDNESS CONDITION.) Then .

**Proof of Lemma 2.** Note is strictly increasing for (as is decreasing). Hence gives .

**Finishing the proof. **Let . Since is bounded, we have for some that for all . Then by lemma 2 on , we have where $latex \varepsilon_m=\frac{1}{2}\left(\frac{C}{C+2}\right)^{m-1}$. By lemma 1, , so this gives

Note also that . Hence .

**Discussion.** What do we learn from this problem?

**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 by SAS Congruence, I say: because of SAS Congruence, . 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.**

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

By:

Mr. Pon September 29, 2012at 2:36 pm

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.

By:

Jon February 15, 2014at 7:09 am