## Sunday, January 21, 2007

### Who Loves Algebra? Topic: Algebra. Level: AIME/Olympiad.

Problem: (1999 Putnam - A3) Consider the power series expansion $\displaystyle \frac{1}{1-2x-x^2} = \sum_{n=0}^{\infty} a_nx^n$. Prove that, for each integer $n \ge 0$, there is an integer $m$ such that $a_n^2+a_{n+1}^2 = a_m$.

Solution: Playing around with the expansion for a bit (using geometric series or otherwise), we find that $a_0 = 1$, $a_1 = 2$, $a_2 = 5$ so $a_0^2+a_1^2 = a_2$. Realizing that the calculation gets uglier and uglier, we decide to go for the general case right now. Now we need to find a good expansion. Try partial fractions.

$\displaystyle \frac{1}{1-2x-x^2} = \frac{1}{2\sqrt{2}}\left(\frac{1}{\sqrt{2}-1-x}+\frac{1}{\sqrt{2}+1+x}\right)$.

Now, to simplify our lives, we let $\alpha = \sqrt{2}+1$. Note that $\frac{1}{\alpha} = \sqrt{2}-1$, so this may turn out to be a key substitution. We get

$\displaystyle \frac{1}{2\sqrt{2}}\left(\frac{1}{\sqrt{2}-1-x}+\frac{1}{\sqrt{2}+1+x}\right) = \frac{1}{2\sqrt{2}}\left(\frac{\alpha}{1-\alpha x}+\frac{1}{\alpha} \cdot \frac{1}{1+\frac{x}{\alpha}}\right)$.

Expanding both fractions using a geometric series, we obtain

$\frac{1}{2\sqrt{2}}\displaystyle \sum_{n=0}^{\infty} x^n \cdot \left(\alpha^{n+1}+\frac{(-1)^n}{\alpha^{n+1}}\right)$,

a remarkably simple expression given what we had up there. It remains to show that $a_n^2+a_{n+1}^2$ also has the form of one of those. So, plugging the appropriate values, we see that

$\displaystyle \frac{1}{8}\left[\left(\alpha^{n+1}+\frac{(-1)^n}{\alpha^{n+1}}\right)^2+\left(\alpha^{n+2}+\frac{(-1)^{n+1}}{\alpha^{n+2}}\right)^2\right] = \frac{1}{8} \left(\alpha^{2n+4}+\alpha^{2n+2}+\frac{1}{\alpha^{2n+2}}+\frac{1}{\alpha^{2n+4}}\right)$

because the middle terms in the squaring cancel out nicely (and the $\frac{1}{8}$ came from the squaring of the constant $\frac{1}{2\sqrt{2}}$). So, recalling that when $n = 0$, we had $a_n^2+a_{n+1}^2 = a_{2n+2}$, we want to make that last expression look like $a_{2n+2}$. A clever factorization yields

$\displaystyle \frac{1}{8} \left[ \alpha^{2n+3}\left(\alpha+\frac{1}{\alpha}\right)+\frac{1}{\alpha^{2n+3}} \left(\alpha+\frac{1}{\alpha}\right) \right] = \frac{\alpha+\frac{1}{\alpha}}{8} \left( \alpha^{2n+3}+\frac{1}{\alpha^{2n+3}} \right)$.

Note, however, that $\alpha+\frac{1}{\alpha} = (\sqrt{2}+1)+(\sqrt{2}-1) = 2\sqrt{2}$, so the result is

$\frac{1}{2\sqrt{2}} \left( \alpha^{2n+3}+\frac{(-1)^{2n+2}}{\alpha^{2n+3}} \right) = a_{2n+2}$

by the expansion we found earlier. QED.

--------------------

Comment: That looked like a lot of work, and it was. The hardest parts were definitely (1) finding out that using the partial fraction decomposition was the best way to go, (2) making the substitution that allowed things to cancel nicely, and (3) keeping track of my work. This is a pretty cool result, which you can usually expect from Putnam problems that have large amounts of algebraic manipulation (you'd hope so, anyway). But in the end, we are left with a satisfactory feeling, so it's all good.

--------------------

Practice Problem: (1999 Putnam - B2) Let $P(x)$ be a polynomial of degree $n$ such that $P(x) = Q(x)P^{\prime\prime}(x)$, where $Q(x)$ is a quadratic polynomial and $P^{\prime\prime}(x)$ is the second derivative of $P(x)$. Show that if $P(x)$ has at least two distinct roots then it must have $n$ distinct roots.