Induction proof of $F(n)^2+F(n+1)^2=F(2n+1)$, where $F(n)$ is the $n$th Fibonacci number. 
Let $F(n)$ denotes the $n$th number in Fibonacci sequence.  Then for all $n\in\mathbb{N}$,
  $$F(n)^2+F(n+1)^2=F(2n+1).$$

I know how to prove it by using the formula 
$$F(n)=\frac{\left(\frac{1+\sqrt5}{2}\right)^n-\left(\frac{1-\sqrt5}{2}\right)^n}{\sqrt{5}},$$
but is there a way to prove it by induction?
I am year 12 standard so please don't go too deep.
 A: The base cases $n=0$ and $n=1$ are easy to verify.
Note that
\begin{align*}
F(2n+3)&=F(2n+2)+F(2n+1)=(F(2n)+F(2n+1))+F(2n+1)\\
&=F(2n)+2F(2n+1)\\
&=(F(2n+1)-F(2n-1))+2F(2n+1)\\&=
3F(2n+1)-F(2n-1).
\end{align*}
Hence, by the inductive hypothesis,
\begin{align*}
F(2n+3)&=3F(2n+1)-F(2n-1)=3(F(n)^2+F(n+1)^2)-(F(n-1)^2+F(n)^2)\\
&=2F(n)^2+3F(n+1)^2-F(n-1)^2\stackrel{?}{=}F(n+1)^2+F(n+2)^2.
\end{align*}
So it remains to show that
$$F(n+2)^2+F(n-1)^2\stackrel{?}{=}2F(n)^2+2F(n+1)^2$$
which holds because
\begin{align*}
F(n+2)^2+F(n-1)^2&=(F(n+1)+F(n))^2+(F(n+1)-F(n))^2\\&=2F(n)^2+2F(n+1)^2.
\end{align*}
A: It's hard to prove this formula directly by induction, but it's easy to prove a more general formula: $$F(m) F(n) + F(m+1) F(n+1) = F(m+n+1).$$
To do this, treat $m$ as a constant and induct on $n$. You'll need two base cases $$F(m) F(0) + F(m+1) F(1) = F(m+1)$$
$$F(m) F(1) + F(m+1) F(2) = F(m+2)$$
which are trivial and the Fibonacci recurrence respectively. From there, the $n-1$ and the $n$ case are not hard to combine into the $n+1$ case.
A: \begin{align} &F(x)=F(x-1)+F(x-2) = F(2)F(x-1)+F(1)F(x-2). \ \\ \ \\ &F(x-1)=F(x-2)+F(x-3) \\ &\Rightarrow F(x)=F(2)(F(x-2)+F(x-3))+F(1)F(x-2)=(F(1)+F(2))F(x-2) \\ &+F(2)F(x-3)=F(3)F(x-2)+F(2)F(x-3). \ \\ \ \\ &F(x-2)=F(x-3)+F(x-4). \\ &\Rightarrow F(x)=F(3)(F(x-3)+F(x-4))+F(2)F(x-3)=(F(2)+F(3))F(x-3) \\ &+F(3)F(x-4)=F(4)F(x-3)+F(3)F(x-4). \\ &\cdot \\ &\cdot \\ &\cdot \\ &\therefore F(x)=F(k+1)F(x-k)+F(k)F(x-k-1). \\ &x=2k+1; \ F(2k+1)=F(k)^2+F(k+1)^2. \\ \ \\ &\therefore F(x)^2+F(x+1)^2=F(2x+1).\end{align}
