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

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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.