<s>[INST] Identity of Fibonacci sequence Let $F_n$ be a Fibonacci sequence with initial terms $F_0=0, F_1=1$ and $F_{n+1}=F_n+F_{n-1}$ for $n\geqslant 1$.
Prove that $F_n^2+F_{n+1}^2=F_{2n+1}$ for $n\geqslant 0$ (with mathematical induction).
My efforts: For $n=0$ it is true.
Suppose that our statement holds for $0\leqslant k \leqslant n$ i.e. $F_k^2+F_{k+1}^2=F_{2k+1}$
Let's try to prove it for $k=n+1$. $$F_{2n+3}=F_{2n+1}+F_{2n+2}=F_{n+1}^2+(F_{n}^2+F_{2n+2})= ?$$
Here I'm stuck and I have applied different methods but none of them brings a positive result.
Can anyone help to complete this?
 [/INST] We can actually prove two different identities (1) and (2), of which you were asked to prove (1):
$$F_{n+1}^2+F_{n+2}^2=F_{2n+3} \quad \text{(1)}$$
$$F_{n+2}^2-F_{n}^2=F_{2n+2} \quad \text{(2)}$$
Note that the Fibonacci numbers are numbered starting from $F_1$.
We can proceed by induction. Suppose that we have the two equations
$$F_n^2+F_{n+1}^2=F_{2n+1} \quad \text{(3)}$$
$$F_{n+1}^2-F_{n-1}^2=F_{2n} \quad \text{(4)}$$
The base cases are trivial.
First Step: Prove (2).
Now, adding (3) and (4), we obtain :
\begin{align}
2F_{n+1}^2+F_n^2-F_{n-1}^2 &= F_{2n+1}+F_{2n}\\\\
(F_{n+1}-F_n)^2+F_{n+1}^2 + 2F_{n+1}F_n - F_{n-1}^2&= F_{2n+2}\\\\
(F_{n-1})^2+F_{n+1}^2 + 2F_{n+1}F_n - F_{n-1}^2&= F_{2n+2}\\\\
(F_{n+1}+F_{n})^2-F_{n}^2&= F_{2n+2}\\\\
F_{n+2}^2-F_{n}^2&= F_{2n+2} \quad \text{(2)}
\end{align}
As desired. $\square$
Second Step: Prove (1). Now that we have (2), we are home free!
Adding (2) and (3), we obtain :
\begin{align}
F_{n+2}^2-F_n^2+F_{n}^2+F_{n+1}^2 &= F_{2n+2}+F_{2n+1}\\\\
F_{n+2}^2+F_{n+1}^2 &= F_{2n+3} \quad \text{(1)}
\end{align}
And we are done. $\square$
</s>