Sum of Squares for Odd Fibonacci Numbers

Question

I am trying to prove the following theorem by induction:

THEOREM:

For the Fibonacci sequence $F_1$, $F_2$, ... , $F_n$ defined as,

• $F_1$ = $F_2$ = 1
• $F_n$ = $F_{n-1}$ + $F_{n-2}$ for n >= 3,

For every n >= 2, $F_{2n+1}$ = $F^2_{n+1}$ + $F^2_n$.

I have gotten it down quite a few steps, but I feel like I am stuck. Did I take a wrong path, or am I on the right path? Any hints as to what should be the next step?

PROOF:

Basis step: Show that the theorem holds for n = 2.

$F_{2n+1}$ = F5 = 5

$F^2_{n+1}$ + $F^2_n$ = $F^2_3$ + $F^2_2$ = $2^2$ + $1^2$ = 5

The basis step holds

Inductive step:

Assume that for some n > 2, $F_{2n+1}$ = $F^2_{n+1}$ + $F^2_n$

Want to show: The theorem holds for n+1

Let I(n) = $F_{2n+1}$

By the inductive hypothesis, I(n) = $F^2_{n+1}$ + $F^2_n$

I(n+1) = $F_{2(n+1) + 1}$ = $F_{2n+3}$

I(n+1) = $F_{2n+2}$ + $F_{2n+1}$

I(n+1) = $F_{2n+2}$ + I(n)

I(n+1) = $F_{2n+2}$ + $F^2_{n+1}$ + $F^2_n$

I(n+1) = $F_{2n+1}$ + $F_{2n}$ + $F^2_{n+1}$ + $F^2_n$

I(n+1) = $F^2_{n+1}$ + $F^2_n$ + $F_{2n}$ + $F^2_{n+1}$ + $F^2_n$

...

...

I(n+1) = $F^2_{n+2}$ + $F^2_{n+1}$ <- What I am trying to get to

Any help is appreciated, I have looked at other posts on the same problem but... they aren't really helping me.

Answer 1

We have: $$ M=\begin{pmatrix}0&1 \\ 1&1\end{pmatrix},\qquad M^k=\begin{pmatrix} F_{k-1}& F_k \\ F_k & F_{k+1}\end{pmatrix}\tag{1}$$ from which it follows that $\det(M^k)=\det(M)^k$, or: $$ F_{k-1}F_{k+1}-F_k^2 = (-1)^k,\tag{2} $$ and: $$ F_{2k-1}=M^{2k}_{(1,1)} = F_{k-1}^2+F_k^2\tag{3}$$ as wanted.

Answer 2

You're quite close. Following your induction, consider

$ F_{2n+1} + F_{2n}$ + $F^2_n$

Notice that $F_{2n}=F_{2n+1}-F_{2n-1}$, so the last expression becomes

$2F_{2n+1} -F_{2n-1} +F_n^2=2F_{n+1}^2+2F_n^2-F_n^2-F_{n-1}^2+F_n^2$

Notice now that

$F_{n-1}^2 = F_{n+1}^2-2F_{n+1}F_n+F_n^2$ Substituting this we get

$ F_{n+1}^2+F_n^2+2F_{n+1}F_n=(F_{n+1} +F_n)^2=F_{n+2}^2$

So in the end we have

$I(n+1) = F_{n+2}^2+F_{n+1}^2$ as we wanted.