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?
 A: 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.
A: 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.
A: $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.$
A: 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.
