Induction and the Fibonacci Sequence

[t.kirschner99]

Homework Statement

Define the Fibonacci Sequence as follows: f₁ = f₂ = 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} $$

Homework Equations

See above.

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!

 

[SammyS]

Homework Statement

Define the Fibonacci Sequence as follows: f₁ = f₂ = 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} $$

Homework Equations

See above.

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!

You're almost there !

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

 

[t.kirschner99]

You're almost there !

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

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 ?

 

[SammyS]

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 ?

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 .