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.

  • $\begingroup$ 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$. $\endgroup$ – forgottenarrow May 5 at 5:44

Hint:This may help you to solve the problem:

$$\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}$.

  • $\begingroup$ i would use the terms that i sum up and check with the matrix? $\endgroup$ – Brian Hu May 8 at 8:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.