Induction on recursive sequences and the Fibonacci sequence

Question

Given :

The Fibonacci sequence is defined recursively by,

$F_0 = 0\\F_1 = 1\\F_n = f_{n - 1} + f_{n - 2}$
for $n ≥ 2$

Use induction to prove that for all integers $n ≥ 0$,

$$\sum_{i=0}^n (f_i)^2 = f_n f_{n+1}$$

What I have so far:

Base Case:

When n = 0, the left hand side equals $(f_i)^2 = 0^2 = 0$

And the right hand side equals $f_0f_1 = 0 (1) = 0$

Therefore, when n = 0, the equation holds true.

Inductive Step:

Assume that for every integer k ≥ 0, $\sum_{i=0}^n (f_i)^2 = f_n f_{n+1}$

Show that $\sum_{i=0}^n (f_i)^2 = f_{k+1} f_{k+2}$

$\sum_{i=0}^{k+1} (f_i)^2 = f_{k+1} f_{k+2} =\\ \sum_{i=0}^k (f_i)^2 = f_k f_{k+1} + (f_{k+1})^2$ Separating out the last term

$(f_kf_{k+1}) + (f_{k+1})^2$ Inductive Hypothesis

If anyone can help out with where I’m supposed to go from here that’d be great. Thanks!

Answer 1

First, you need to get your set-up straight!

The base is fine, but for the step you write:

Assume that for every integer k ≥ 0, $\sum_{i=0}^n (f_i)^2 = f_n f_{n+1}$

That's not good: you make no refernce to $k$, and for the step you do not want to assume anything about all $k \ge 0$ anyway.

Then you write:

Show that $\sum_{i=0}^n (f_i)^2 = f_{k+1} f_{k+2}$

Again, not good: Now you have a $n$ on the left but $k$ on the right. And why the $+1$ in the hypothesis?

Here is what you need to do. Say that $k$ is some arbitrary integer, for which you assume the inductive hypothesis:

$$\sum_{i=0}^k (f_i)^2 = f_k f_{k+1}$$

And what you now want to prove is:

$$\sum_{i=0}^{k+1} (f_i)^2 = f_{k+1} f_{k+2}$$

Well:

$$\sum_{i=0}^{k+1} (f_i)^2 = \sum_{i=0}^k (f_i)^2 + f_{k+1}^2 \overset{Inductive Hypothesis}{=} f_{k} f_{k+1} + f_{k+1}^2 = f_{k+1}(f_{k} + f_{k+1}) = f_{k+1} f_{k+2}$$

Answer 2

Just take $f_{k+1}$ common out of the expression.$$f_{k+1} f_{k}+(f_{k+1})^2=f_{k+1}(f_k+f_{k+1})$$

Now use $F_{n}=F_{n-1}+F_{n-2}$, to get $$f_{k+1}(f_k+f_{k+1})=f_{k+1}f_{k+2}$$

Done!