# Prove Fibonacci Sequence Property: $x^2_n + x^2_{n+1}=x_{2n+1}$

For Fibonacci Sequence, We know that the recursive difference equation is:

$$x_{n+2} = x_n + x_{n+1}\ \ \ \ n\ \geq 0$$

And that the closed form solution is:

$$x_n = \frac{1}{\sqrt{5}}\left[ \left(\frac{1+\sqrt{5}}{2}\right)^{n} - \left(\frac{1-\sqrt{5}}{2}\right)^{n} \right]\ \ \ \ n \geq 0$$

But how to prove that this fibonacci property is true using this information?:

$$x^2_n + x^2_{n+1}=x_{2n+1}$$

Hint: substitute the closed form expression for the fibonacci sequence into difference equation and verify that its true.

well...I've tried this at least 3 different ways of doing exactly as hinted without much luck...the equation always blows up on me. Any ideas how to prove it?

• Can you show one or more of those 3 different ways? It is hard to guess at what you're doing wrong when we don't know what you're doing. – Henning Makholm Jan 7 at 23:43
• Hint: with $x_0=0,x_1=1$, prove by induction over $m$ that $x_p=x_{m+1}x_{p-m}+x_mx_{p-m-1}$. – Mindlack Jan 8 at 0:06

The 'standard proof' uses strong induction, and I'll leave you to figure that out.

Let $$\varphi$$ and $$\psi$$ represent the two roots of $$x^2-x-1=0$$ where $$\varphi > \psi$$ (i.e. $$\varphi,\psi=\frac{1\pm \sqrt{5}}{2}$$). The given closed form solution is $$F_n=\frac{\varphi ^n-\psi ^n}{\sqrt{5}}$$ so we know $$F_n^2=\frac{\varphi ^{2n}-2(\varphi \psi)^n+\psi ^{2n} }{5}$$ and $$F_{n+1}^2=\frac{\varphi ^{2n+2}-2(\varphi \psi )^{n+1}+\psi ^{2n+2}}{5}$$ so $$F_n^2+F_{n+1}^2=\frac{\varphi ^{2n}-2(\varphi \psi)^n+\psi ^{2n}+\varphi ^{2n+2}-2(\varphi \psi )^{n+1}+\psi ^{2n+2} }{5}$$But we know that $$\varphi \psi =-1$$, so either $$(\varphi\psi)^n=1$$ and $$(\varphi\psi)^{n+1}=-1$$ or $$(\varphi\psi)^n=-1$$ and $$\varphi\psi)^{n+1}=1$$. Either way, the two terms cancel each other, so$$F_n^2+F_{n+1}^2=\frac{\varphi^{2n}(1+\varphi ^2)+\psi ^{2n}(1+\psi^2)}{5}$$It can be easily seen that $$\frac{1+\varphi^2}{\sqrt{5}}=\varphi$$ and $$\frac{1+\psi^2}{\sqrt{5}}=-\psi$$ so the above becomes \begin{align*}F_n^2+F_{n+1}^2&=\frac{\varphi^{2n}(1+\varphi ^2)+\psi ^{2n}(1+\psi^2)}{5}\\ &=\frac{\varphi^{2n}\cdot \varphi\sqrt{5} + \psi^{2n}\cdot (-\psi\sqrt{5})}{5} \\ &=\frac{\sqrt{5}(\varphi^{2n+1}-\psi^{2n+1})}{5} \\ &=\frac{\varphi^{2n+1}-\psi^{2n+1}}{\sqrt{5}} \\ &= F_{2n+1}\end{align*}completing the proof.

• This seems to be the approach being hinted at. From OP's perspective, I think the insight that was missing was that we should expand things in terms of $\varphi$ and $\psi$, rather than in the way one typically "expands and simplifies". – Omnomnomnom Jan 8 at 0:10

For what it's worth, there's a nice approach using matrices. We can characterize the recurrence by $$\pmatrix{x_{n+1}\\x_n} = \pmatrix{1&1\\1&0}\pmatrix{x_{n}\\x_{n-1}}, \quad n \geq 1$$ Let $$F = \pmatrix{1&1\\1&0}$$. As a consequence of this characterization, we end up with the formula $$F^n = \pmatrix{x_{n+1} & x_n\\ x_n & x_{n-1}}$$ We now compute $$(F^n)^2 = \pmatrix{x_{n+1} & x_n\\ x_n & x_{n-1}}^2 = \pmatrix{x_{n+1}^2 + x_n^2 & x_{n+1}x_n + x_n x_{n-1}\\ x_{n+1}x_n + x_n x_{n-1} & x_n^2 + x_{n-1}^2}$$ On the other hand, $$(F^n)^2 = F^{2n} = \pmatrix{x_{2n+1} & x_{2n}\\ x_{2n} & x_{2n-1}}$$ Because the two matrices are equal, their upper-left entries are equal, which is exactly the desired conclusion.

$$x_{2n+1}=x_{2n}+x_{2n-1}=x_2x_{2n}+x_1x_{2n-1}=x_2(x_{2n-1}+x_{2n-2})+x_1x_{2n-1}=(x_1+x_2)x_{2n-1}+x_2x_{2n-2}=x_3x_{2n-1}+x_2x_{2n-2}=x_4x_{2n-2}+x_3x_{2n-3}=\cdots =x_xx_n+x_{n+1}x_{n+1}=x_n^2+x_{n+1}^2.$$

Based on the title of the topic and the hint, you need to plug the Closed form expression into your equality

$$x_{n}^2+x_{n+1}^2-x_{2n+1}$$

and make sure it equals zero identically.

Best way is to taky any CAS and plug the figures. For Wolfram Mathematica

x[n_] := 1/Sqrt[5]*(((1 + Sqrt[5])/2)^n - ((1 - Sqrt[5])/2)^n);

x[a]^2 + x[a + 1]^2 - x[2*a + 1]

Simplify[Out[]]

Then you get something like this

$$\frac{1}{5} \left(\left(\frac{2}{\sqrt{5}+1}\right)^{-a-1}-\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^{a+1}\right)^2+\frac{1}{5} \left(\left(\frac{1}{2} \left(\sqrt{5}+1\right)\right)^a-\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^a\right)^2-\frac{\left(\frac{2}{\sqrt{5}+1}\right)^{-2 a-1}-\left(\frac{1}{2} \left(1-\sqrt{5}\right)\right)^{2 a+1}}{\sqrt{5}}$$

You need to carefully open up all brackets, cancel out the terms to get zero.