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 $m$th 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. (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 gives $f(x)$\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 for all $j$. Then by lemma 2 on $b_1,\ldots, b_m$, we have ${}0 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

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?

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.