# Induction and the Fibonacci Sequence

Tags:
1. Aug 1, 2017

### t.kirschner99

1. The problem statement, all variables and given/known data
Define the Fibonacci Sequence as follows: f1 = f2 = 1, and for n≥3, $$f_n = f_{n-1} + f_{n-2},$$

Prove that $$\sum_{i=1}^n f^{2}{}_{i} = f_{n+1} * f_{n}$$

2. Relevant equations

See above.

3. The attempt at a solution

Due to two variables being present in both the Sequence and what needs to be proved, strong induction is required.

Proof that it works for n = 1 and n=2:

$$f_3 = f_{2} + f_{1} = 1 + 1 = 2$$

n=1 LHS $$\sum_{i=1}^1 f^{2}{}_{i} = f^{2}{}_{1} = 1^2 = 1$$
RHS $$f_{1+1} * f_{1} = 1 * 1 = 1$$

n=2 LHS $$\sum_{i=1}^2 f^{2}{}_{i} = f^{2}{}_{1} + f^{2}{}_{2} = 1^2 + 1^2 = 2$$
RHS $$f_{2+1} * f_{2} = 2 * 1 = 2$$

Hypothesis: $$\sum_{i=1}^k f^{2}{}_{k} = f_{k+1} * f_{k}$$

We want to prove: $$\sum_{i=1}^{k+1} f^{2}{}_{i} = f_{k+2} * f_{k+1}$$
It is in my proof where I do not quite know what I am doing:

$$\sum_{i=1}^{k+1} f^{2}{}_{i} = \sum_{i=1}^{k} f^{2}{}_{i} + f^{2}{}_{k+1} = f_{k+1} * f_{k} + f^{2}{}_{k+1} = f_{k+1} (f_{k} + f_{k+1})$$

How do I simplify from here? Not quite sure what to do with these functions.

Thanks all!

2. Aug 1, 2017

### SammyS

Staff Emeritus
You're almost there !

Using the recursive definition of the Fibonacci sequence, what is $\ f_{k} + f_{k+1} \ ?$

3. Aug 1, 2017

### t.kirschner99

Ah thank you for opening my eyes! That would be equal to $$f_{k+2}$$ thus the statement is proven.

One quick question about the hypothesis, would I need to assume that k > 3 ?

4. Aug 1, 2017

### SammyS

Staff Emeritus
You're welcome!

At first I was also thinking that we should only look at k ≥ 3, but the thing you needed to prove was $\ \displaystyle \sum_{i=1}^n f_{i}^{2} = f_{n+1} * f_{n} \,.\$ Everything in this equation is defined for n ≥ 1 .