Prove formula for sum of Fibonacci sequence numbers by mathematical induction.

Question

We need to prove the following using proof by induction. I don't want the actual answer if you can avoid it, I just can't figure out how to do it because when I do it how my notes read I am supposed to it doesn't work.

Anyway, this is what we were given on the paper;

 

Knowing that:    F_n+1 = F_n + F_n-1     where  F₁ = 1 and F₂ = 1    , prove the following by mathematical induction:

 

 n

 Σ   F_i² = F_n × F_n+1           n≥1

ⁱ⁼¹

 

 

 

 

Answer 1

Freya,

 

Let P(n) be Σⁿ_i=1 F_i² = F_n x F_n+1

 

In a proof by induction the first (Basis) step is to show P(1) is true so:

 

P(1): F₁² = F₁ x F₂    

         

         1² = 1 x 1  is true

 

Now we assume P(k) is true. (Inductive Hypothesis)

 

The inductive proof step:

 

Using the Inductive Hypothesis you want to now show P(k+1) is true:

 

(1) F₁² + F₂² + F₃² + ... F_k² + F_k+1²  = F_k x F_k+1 + F_k+1²

 

 

Can you do the rest of the proof from here?