# Recurrence Relation with generating function

We have the generating function $$1/(1−2x−x^2)=\sum_{n=0}^{\infty}a_nx^n$$ Show $$a_n^2 + a_{n+1}^2 = a_{2n+2}$$.

I am thinking of finding a 2 × 2 matrix A and the text gives a hint of $$A^{n+2}= \left( \begin{smallmatrix} a_n&a_{n+1}\\ a_{n+1}&a_{n+2} \end{smallmatrix} \right)$$ and consider the top left entry of the matrix product $$A^{n+2}A^{n+2}$$. I do not exactly understand this hint.

• The hint is saying you can find a $2\times 2$ matrix $A$ such that, $$A^2 = \begin{bmatrix} a_0&a_1\\ a_1&a_2 \end{bmatrix},$$ and for any $n$, $$A^{n+2} = \begin{bmatrix} a_n&a_{n+1}\\ a_{n+1}&a_{n+2} \end{bmatrix}.$$ Then, $$\begin{bmatrix} a_{2n+2} & a_{2n+3}\\ a_{2n+3}&a_{2n+4} \end{bmatrix}=A^{2n+4}=A^{n+2}A^{n+2}=\begin{bmatrix} a_n^2 + a_{n+1}^2&a_na_{n+1}+a_{n+1}a_{n+2}\\ a_na_{n+1}+a_{n+1}a_{n+2}&a_{n+1}^2+a_{n+2}^2 \end{bmatrix}.$$ Setting the top left entries equal yields the result. All that's left is to derive $A$. – forgottenarrow May 5 at 5:44

$$\frac{1}{1-2x-x^2}=\frac{1}{2\sqrt2}.(\frac{1}{x+1-\sqrt2}-\frac{1}{x+1+\sqrt 2}$$
Now expand $$\frac{1}{1+(x-\sqrt2)}$$ and $$\frac{1}{1+(x+\sqrt2)}$$ and sum up terms with identical powers, you get the expansion of $$\frac{1}{1-2x-x^2}$$. Now you can check $$a^2_n+a^2_{n+1}= a_{2n+2}$$.