Induction proof of $F(n)^2+F(n+1)^2=F(2n+1)$, where $F(n)$ is the $n$th Fibonacci number.

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*}

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.