Resolving Recurrence by Induction Problem: $T(0)=0, T(1)=1$ and $T(n)=T(n-1)+T(n-2)$ $\forall n\geq 2$
Given $T(2n)=T(n-1)T(n)+T(n)T(n+1)$ $\forall n\geq 1$, prove by induction that $T(2n)=T(n+1)^2 -T(n-1)^2$ $\forall n \geq 1$
My attempt:
Base Case: $T(0)=0$, $T(1)=1$
Inductive Hypothesis: Assume $T(2n)=T(n+1)^2-T(n-1)^2$ for $n=k$ $\forall n \geq 1$
Inductive Step: Show the inductive hypothesis works for $n=k+1$
\begin{align}
T(2(n+1)) &= T(2n+2)\\
&= T((2n+1)-1) + T((2n+1)-2)&&\text{By definition}\\
&= T(2n+1) + T(2n)&&\text{Simplify}\\
&= T(2n+1) + T(n+1)^2 - T(n-1)^2&&\text{Apply hypothesis}
\end{align}
But after this, I'm stumped. I'm not sure how to continue this proof, or if this is dead end. Any help would be greatly appreciated!
 A: For the base case, i.e., for $n = 1$, you have $T(2) = T(1) + T(0) = 1$, so
$$T(2) = 1 = 1^2 - 0^2 = T(2)^2 - T(0)^2 \tag{1}\label{eq1A}$$
For the inductive step, i.e., $n = k + 1$, using the given first $T(2n)$ formula, plus from the problem statement that $T(k+2) = T(k+1) + T(k) \implies T(k+1) = T(k+2) - T(k)$, gives
$$\begin{equation}\begin{aligned}
T(2(k+1)) & = T((k+1)-1)T(k+1) + T(k+1)T((k+1)+1) \\
& = T(k)T(k+1) + T(k+1)T(k+2) \\
& = T(k)(T(k+2) - T(k)) + (T(k+2) - T(k))T(k+2) \\
& = T(k)T(k+2) - T(k)^2 + T(k+2)^2 - T(k)T(k+2) \\
& = T(k+2)^2 - T(k)^2 \\
& = T((k+1)+1)^2 - T((k+1)-1)^2
\end{aligned}\end{equation}\tag{2}\label{eq2A}$$
This completes the inductive step, i.e., showing the formula works for $n = k + 1$, so by induction the second formula for $T(2n)$ works for all $n \ge 1$. However, note this doesn't actually use, nor does it need to, the inductive hypothesis step, so this could have actually been proven directly instead from the given $T(2n)$ expression.
Other other thing to note is the recurrence $T(n)$ is actually $F_n$, i.e., the Fibonacci sequence.
