Can you prove the power series expansion for (1-2x-x^2) has a specific pattern?

[Ackbach]

Here is this week's POTW:

-----

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

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

Re: Problem Of The Week # 250 - Jan 25, 2017

This was Problem A-3 in the 1999 William Lowell Putnam Mathematical Competition.

Congratulations to Kiwi and Theia for their correct solutions! Theia's solution follows:

Spoiler

First, one have to find out the coefficients $$a_n$$. By writing

$$1 = (1 - 2x - x^2)\sum_{n=0}^{\infty}a_nx^n$$

and separating the sum into three different sums and finally manipulating the summing indices, one can write this as

$$1 = a_0 + (a_1 - 2a_0)x + \sum_{v=2}^{\infty}(a_v - 2a_{v-1} + a_{v-2})x^v$$.

This means, one can write

$$\begin{align*} a_0 &= 1 \\ a_1 &= 2 \\ a_v &= 2a_{v-1} + a_{v-2} \ , \end{align*}$$

where $$v \ge 2$$ (integer).

The last line defines a linear difference equation, whose solution can be found through characteristic equation, namely

$$\lambda ^2 = 2\lambda + 1 \qquad \Rightarrow \qquad \lambda = 1 \pm \sqrt{2} \ ,$$

and thus the general solution is

$$a_n = c_1\cdot (1 - \sqrt{2})^n + c_2\cdot (1 + \sqrt{2})^n$$.

By adding the initial conditions ($$a_0 = 1, a_1 = 2$$) one can write the coefficients of the serie in form ($$n$$ integer, $$\ge 0$$):

$$a_n = \frac{1}{4} \Bigl[\bigl(2 - \sqrt{2}\bigr)\cdot \bigl(1 - \sqrt{2}\bigr)^n + \bigl(2 + \sqrt{2}\bigr)\cdot \bigl(1 + \sqrt{2}\bigr)^n \Bigr]$$.

Now one can write

$$\begin{align*}a_n^2 + a_{n+1}^2 &= \frac{1}{4} \Bigl[\underbrace{\bigl(10 - 7\sqrt{2}\bigr)}_{=(2 - \sqrt{2})(1 - \sqrt{2})^2}\cdot \bigl(1 - \sqrt{2}\bigr)^{2n} + \underbrace{\bigl(10 + 7\sqrt{2}\bigr)}_{=(2 + \sqrt{2})(1 + \sqrt{2})^2}\cdot \bigl(1 + \sqrt{2}\bigr)^{2n} \Bigr] \\
& = \frac{1}{4} \Bigl[\bigl(2 - \sqrt{2}\bigr)\cdot \bigl(1 - \sqrt{2}\bigr)^{2n + 2} + \bigl(2 + \sqrt{2}\bigr)\cdot \bigl(1 + \sqrt{2}\bigr)^{2n+2} \Bigr] \\
&= a_{2n+2} \\
&= a_m\end{align*}.$$

Hence for every index $$n \ge 0$$ there is an index $$m$$ such that $$a_n^2 + a_{n+1}^2 = a_m$$.