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 \(\displaystyle a_n\). By writing

\(\displaystyle 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

\(\displaystyle 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

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

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

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

\(\displaystyle \lambda ^2 = 2\lambda + 1 \qquad \Rightarrow \qquad \lambda = 1 \pm \sqrt{2} \ ,\)

and thus the general solution is

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

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

\(\displaystyle 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

\(\displaystyle \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 \(\displaystyle n \ge 0\) there is an index \(\displaystyle m\) such that \(\displaystyle a_n^2 + a_{n+1}^2 = a_m\).