Putnam 1999, Problem A-3

Consider the power series expansion
\[
\frac{1}{1 - 2x - x^2} = \sum_{n=0}^\infty a_n x^n.
\]
Prove that, for each integer \(n \geq 0\), there is an integer \(m\) such that
\[
a_n^2 + a_{n+1}^2 = a_m.
\]

Solution:
First solution: Computing the coefficient of $x^{n+1}$ in the identity $(1-2x-x^2)\sum_{m=0}^\infty a_mx^m = 1$ yields the recurrence $a_{n+1} = 2a_n + a_{n-1}$; the sequence $\{a_n\}$ is then characterized by this recurrence and the initial conditions $a_0 = 1, a_1 = 2$.

Define the sequence $\{b_n\}$ by $b_{2n} = a_{n-1}^2 + a_n^2$, $b_{2n+1} = a_n(a_{n-1} + a_{n+1})$. Then
$$2b_{2n+1} + b_{2n} = 2a_na_{n+1} + 2a_{n-1}a_n + a_{n-1}^2 + a_n^2$$
$$= 2a_na_{n+1} + a_{n-1}a_{n+1} + a_n^2$$
$$= a_{n+1}^2 + a_n^2 = b_{2n+2},$$
and similarly $2b_{2n} + b_{2n-1} = b_{2n+1}$, so that $\{b_n\}$ satisfies the same recurrence as $\{a_n\}$. Since further $b_0 = 1, b_1 = 2$ (where we use the recurrence for $\{a_n\}$ to calculate $a_{-1} = 0$), we deduce that $b_n = a_n$ for all $n$. In particular, $a_n^2 + a_{n+1}^2 = b_{2n+2} = a_{2n+2}$.

Second solution: Note that
$$\frac{1}{1-2x-x^2}$$
$$= \frac{1}{2\sqrt{2}}\left(\frac{\sqrt{2}+1}{1-(1+\sqrt{2})x} + \frac{\sqrt{2}-1}{1-(1-\sqrt{2})x}\right)$$
and that
$$\frac{1}{1+(1\pm\sqrt{2})x} = \sum_{n=0}^\infty (1\pm\sqrt{2})^n x^n,$$
so that
$$a_n = \frac{1}{2\sqrt{2}}\left((\sqrt{2}+1)^{n+1} - (1-\sqrt{2})^{n+1}\right).$$

A simple computation (omitted here) now shows that $a_n^2 + a_{n+1}^2 = a_{2n+2}$.

Third solution (by Richard Stanley): Let $A$ be the matrix $\begin{pmatrix} 0 & 1 \\ 1 & 2 \end{pmatrix}$. A simple induction argument shows that
$$A^{n+2} = \begin{pmatrix} a_n & a_{n+1} \\ a_{n+1} & a_{n+2} \end{pmatrix}.$$
The desired result now follows from comparing the top left corner entries of the equality $A^{n+2}A^{n+2} = A^{2n+4}$.