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?
Best Answer
We can prove more general identity, i.e. $F_{n+m+1}=F_{m+1}F_{n+1}+F_{m}F_{n}$.
Let's prove above by mathematical induction on $n$.
For $n=0$ we have $F_{m+1}=F_{m+1}$
Suppose it is true for all $0\leqslant n \leqslant k$.
Let's prove it for $n=k+1$ then $$F_{k+m+2}=F_{k+m}+F_{k+m+1}=(F_{m+1}F_{k}+F_{m}F_{k-1})+(F_{m+1}F_{k+1}+F_{m}F_{k})=F_{m+1}(F_k+F_{k+1})+F_m(F_{k-1}+F_k)=F_{m+1}F_{k+2}+F_mF_{k+1}$$
The first two parentheses were derived from induction assumption for $n=k-1$ or $n=k$.
Thus, we have proved our initial statement. If we put $n=m$ we get $$F_{2n+1}=F_{n+1}^2+F_n^2$$