I'm proceeding by induction, but I have no idea how to do the inductive step. The Fibonacci sequence takes on the definition:
$F(0)=0$
$F(1) = 1$
$F(2) = 1$
So far, my proof is as follows:
Base Case:
$F(2) = 1 = F(1)^2 + F(0)^2$. This case holds
Inductive Step: We assume the claim holds for $n$ and show it holds for $n+1$…
$F(2n+1) = F(2n)+F(2n-1)=F(2n) + F(n-1)^2+F(n)^2$
I am stuck on how to reduce this expression to $F(n)^2 + F(n+1)^2$…
Edit: Thank you for the responses. I realize I made an egregious error in defining the fibonacci sequence. I have corrected it to the definition we use in my class.
Edit by DS : Now changed the indexing to the standard convention of the Fibonacci numbers.
Best Answer
We need a second part to our inductive hypothesis \begin{eqnarray*} F_{2n-1}=F_{n-1}^2+ F_n^2 \\ F_{2n}=F_{n}(F_{n+1}+F_{n-1}) \end{eqnarray*} To prove the first equation \begin{eqnarray*} F_{2n+1}=F_{2n}+F_{2n-1}= F_{n}(F_{n+1}+F_{n-1}) + F_{n-1}^2+ F_n^2 \\= F_{n-1}(F_{n-1}+F_n)+F_n^2+F_nF_{n+1}= F_{n+1}^2+F_{n}^2. \end{eqnarray*} To prove the second equation \begin{eqnarray*} F_{2n+2}=F_{2n+1}+F_{2n}= F_{n+1}^2+F_{n}^2+F_{n}(F_{n+1}+F_{n-1}) \\ =F_{n+1}(F_{n+1}+F_{n})+F_{n}(F_{n}+F_{n-1})= F_{n+1}(F_{n+2}+F_{n}). \end{eqnarray*}