TITLE: Prove Fibonacci Sequence Property: $x^2_n + x^2_{n+1}=x_{2n+1}$
QUESTION [2 upvotes]: 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?

REPLY [7 votes]: 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.
{"set_name": "stack_exchange", "score": 2, "question_id": 3065643}