Proving Generating Function holds a specific recurrence.

Question

Consider the generating function $$\dfrac{1}{1 − 2x − x^2} = \sum_{n=0}^{\infty}a_nx^n$$

Prove that for each integer $n \ge 0$, $$a_n^2+a_{n+1}^2 = a_{2n+2}$$

Hint: Find a $2 \times 2$ matrix $A$ such that $$A^{n+2} =\begin{bmatrix}a_n &a_{n+1}\\ a_{n+1} &a_{n+2}\end{bmatrix}$$ and consider the top left entry of the matrix product $A^{n+2}A^{n+2}$.

Looking at the hint, I think about how we used matrices and eigenvalues to find the closed form expression of recurrence relations, but I can only really do that for stuff of the form $a_n=a_{n-1}+a_{n-2}$, and I'm not sure how the matrix product fits in there.

Instead, I tried to find the generating function for the recurrence listed above as: $$\begin{align*} a_n^2+a_{n+1}^2 &= a_{2n+2}\\ \left(x^n\right)^2a_n^2+\left(x^n\right)^2a_{n+1}^2 &= \left(x^n\right)^2a_{2n+2}\\ \sum_{n=0}^{\infty}\left(x^n\right)^2a_n^2+\sum_{n=0}^{\infty}\left(x^n\right)^2a_{n+1}^2 &= \sum_{n=0}^{\infty}\left(x^n\right)^2a_{2n+2}\\ A(x)^2+\dfrac{A(x)^2}{x^2} &= \sum_{n=0}^{\infty}x^{2n}a_{2n+2}\\ A(x)^2+\dfrac{A(x)^2}{x^2} &= \dfrac{A(x)}{x^2}\\ x^2A(x)^2+A(x)^2&=A(x)\\ A(x)=\dfrac{1}{x^2+1} \end{align*}$$

But that's clearly not what we wanted. What mistakes did I make, and how does the hint fit into all of this? Thanks!

Answer 1

Too long for a comment $$\frac{1}{1 − 2x − x^2}=\frac{1}{(1+\sqrt2+x)(\sqrt2-1-x)}=\frac{1}{2\sqrt2}\left(\frac{1}{1+\sqrt2+x}+\frac{1}{\sqrt2-1-x}\right)$$ $$=\frac{1}{2\sqrt2}\sum_{n=0}^\infty\left(\frac{x^n}{(\sqrt2-1)^{n+1}}+(-1)^n\frac{x^n}{(\sqrt2+1)^{n+1}}\right)$$ Then, given that $\frac{1}{(\sqrt2+1)^{n+1}}=\frac{(\sqrt2-1)^{n+1}}{(\sqrt2+1)^{n+1}(\sqrt2-1)^{n+1}}=(\sqrt2-1)^{n+1}$ $$a_n=\frac{1}{2\sqrt2}\left(\frac{1}{(\sqrt2-1)^{n+1}}+(-1)^n\frac{1}{(\sqrt2+1)^{n+1}}\right)=\frac{1}{2\sqrt2}\left((\sqrt2+1)^{n+1}+(-1)^n(\sqrt2-1)^{n+1}\right)$$ and $$a_{n+1}=\frac{1}{2\sqrt2}\left((\sqrt2+1)^{n+2}+(-1)^{n+1}(\sqrt2-1)^{n+2}\right)$$ Then $$a_n^2+a_{n+1}^2=\frac{1}{8}\left((\sqrt2+1)^{2n+2}+(\sqrt2-1)^{2n+2}+(\sqrt2+1)^{2n+4}+(\sqrt2-1)^{2n+4}\right)$$ $$=\frac{1}{8}\left((\sqrt2+1)^{2n+2}+(\sqrt2-1)^{2n+2}+(\sqrt2+1)^{2n+2}(3+2\sqrt2)+(\sqrt2-1)^{2n+2}(3-2\sqrt2)\right)$$ $$=\frac{1}{2\sqrt2}\left((\sqrt2+1)^{2n+3}+(\sqrt2-1)^{2n+3}\right)=a_{2n+2}$$

Answer 2

Define $f(x)$ by $$f(x)= \frac{1}{1-2x-x^2} = \sum_{n=0}^{\infty} a_n x^n$$ so $$f(x) -2x f(x) -x^2 f(x) = 1$$ From this equation we deduce $a_0=1$, $a_1=2$, and $a_{n+2} -2a_{n+1} -a_n = 0$ for $n \ge 0$. It follows by induction on $n$ that if we let $$A = \begin{pmatrix} 0 &1 \\ 1 &2 \end{pmatrix}$$ then $$A^{n+2} =\begin{pmatrix} a_n &a_{n+1} \\ a_{n+1} &a_{n+2} \end{pmatrix}$$ for $n \ge 0$. Now we can compute $$A^{n+2} \cdot A^{n+2} = \begin{pmatrix} a_n^2+a_{n+1}^2 & a_n a_{n+1} + a_{n+1} a_{n+2} \\ a_n a_{n+1} + a_{n+1} a_{n+2} & a_{n+1}^2 a_{n+2}^2 \end{pmatrix}$$ On the other hand, $$A^{n+2} \cdot A^{n+2} = A^{2n+2+2} = \begin{pmatrix} a_{2n+2} & a_{2n+3} \\ a_{2n+3} & a_{2n+4} \end{pmatrix}$$ Comparing the upper-left elements in these two matrices, we see $$a_n^2+a_{n+1}^2 = a_{2n+2}$$