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!


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



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


$$\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}$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.