How to prove this Fibonacci sequence statement: $F^2_{n+1} - F^2_{n-1} = F_{2n}$ So the statement is:
Prove: $$F^2_{n+1} - F^2_{n-1} = F_{2n}$$
How could this be proven with induction?
What about without induction?
For induction I got here: (already tested $n=1$, and assumed $n=k$ held true)
$$F^2_{k+2} - F^2_{k} = F_{2k + 2}$$
$$(F_{k+1} + F_{k})^2 - (F_{k-1} + F_{k-2})^2 = F_{2k+1} + F_{2k}$$
Then you get some cancelation based off the $n=k$ case
$$2F_{k+1}F_k + F_k^2 - 2F_{k-1}F_{k-2} - F_{k-2}^2 = F_{2k+1}$$
This is where I am stuck for the induction proof.
I have no idea where to begin with the non-induction proof.
 A: Consider this matrix:
$$A=\begin{bmatrix}1&1\\1&0\end{bmatrix}.$$
Matrix $A$ is such that
$$A^n=\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}.$$
Compute both $(A^n)^2$ and $A^{(2n)}$ (they are equal) and compare them entrywise:
$$\begin{align}(A^n)^2&=
\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}
\cdot\begin{bmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{bmatrix}
\\
&=\begin{bmatrix}F^2_{n+1}+F^2_n &F_{n+1}F_{n}+F_{n}F_{n-1}\\ F_{n}F_{n+1}+F_{n-1}F_n &F^2_n+F^2_{n-1}\end{bmatrix}
\\
&\equiv \begin{bmatrix}F_{2n+1}&F_{2n}\\F_{2n}&F_{2n-1}\end{bmatrix}=A^{(2n)}.\end{align}$$
So
$$\begin{align}F_{2n}&=F_{n+1}F_n+F_{n-1}F_n=(F_{n+1}+F_{n-1})F_n=(F_{n+1}+F_{n-1})(F_{n+1}-F_{n-1})\\&=F^2_{n+1}-F^2_{n-1}.\end{align}$$
A: To prove it without induction, you can use the general formula for Fibonacci numbers:
$$F_n=\frac{ \phi_+^n - \phi_-^n}{\sqrt 5}$$
Where $\phi_\pm=\frac{1\pm\sqrt{5}}{2}$.
A: A direct proof:
$$F_{k+1}^2-F_{k-1}^2=(F_{k+1}-F_{k-1})(F_{k+1}+F_{k-1})=F_k(F_{k+1}+F_{k-1})=F_kF_{k+1}+F_{k-1}F_k\tag1$$
Summing both sides of (1) over $k$ and using this theorem, we arrive at our required result.
A: An alternative method other than induction:
Just by comparison of Fibonacci and Lucas numbers, you can easily find following two identities for all $n\ge 1$: $$L_n=F_{n-1}+F_{n+1}$$ and $$F_{2n}=F_{n}L_{n}$$
The product of these two equations leads to:
 $$F_{2n}L_n=F_{n}L_{n}\left(F_{n-1}+F_{n+1}\right)$$
Since $L_{n}\ne 0$ when $n\ge 0$, we can cancel $L_{n}$ from both side leading to:
 $$F_{2n}=F_{n}\left(F_{n-1}+F_{n+1}\right)$$
Now, by substituting $F_{n}=F_{n+1}-F_{n-1}$, we get:
$$F_{2n}=\left(F_{n+1}-F_{n-1}\right)\left(F_{n+1}+F_{n-1}\right)=F_{n+1}^2-F_{n-1}^2$$
Done.
