Skip to main content

Subsection 8.10.2 The Fibonacci Sequence

Recall that we can define a sequence of numbers by specifying one, or some small number, of starting values. Then we write a formula that computes the values of later elements from preceding ones. Notice the natural correspondence between the structure of a definition like this and the structure of an inductive proof. Thus, no surprise, we can often use induction to prove claims about sequences defined in this way.

We used exactly this technique to define the Fibonacci sequence:

f1 = 1, (The first element is 1.)

f2 = 1, (So is the next one.)

for all k  2, fk+1 = fk + fk-1 (Other elements are computed from the two previous ones.)

So the first several terms of the sequence are 1, 1, 1+1=2, 2+1=3, 3+2=5, 5+3=8, 8+5=13.

Exercises Exercises

1.

Define the Fibonacci sequence as follows:

f1 = 1, (i.e., the first element of the sequence is 1)

f2 = 1, (and so is the second element)

for all k > 2, fk+1 = fk + fk-1 (other elements computed from the two previous ones)

Prove that for all n ≥ 1: \((\sum_{i = 1}^{n}{f_{i}^{2})} = \ f_{n}f_{n + 1}\)

The proof is by induction on n.

Define: P(n) ≡ \((\sum_{i = 1}^{n}{f_{i}^{2})} = \ f_{n}f_{n + 1}\)

Base case: Write a proof of the base case.

Induction step: Begin by writing the induction hypothesis

Write your proof.

Answer.
Base case: Write a proof of the base case. When you’re done, click here to check it. When clicked, should see: P(1): (∑_(i=1)^n▒〖f_i^2)〗= 1^2=1 f_n f_(n+1) = 1  1 = 1. Induction step: Begin by writing the induction hypothesis. When you’re done, click here to check it. When clicked, should see: (∑_(i=1)^n▒〖f_i^2)〗= f_n f_(n+1) Write your proof. If you need a hint, click here. If clicked, should see: Start by writing an expression for ∑_(i=1)^(n+1)▒f_i^2 . Then see if you can manipulate that to get the result that you need. If you need another hint, click here. If clicked, should see: (∑_(i=1)^(n+1)▒〖f_i^2)〗 = (∑_(i=1)^n▒f_i^2 ) + f_(n+1)^2 Now try to use the induction hypothesis to rewrite the right hand side of this equation. When you’ve finished your proof, click here to see ours. When clicked, should see: Base case: P(1): (∑_(i=1)^n▒〖f_i^2)〗= 1^2=1 f_n f_(n+1) = 1  1 = 1. Induction step: (∑_(i=1)^(n+1)▒〖f_i^2)〗 = (∑_(i=1)^n▒〖f_i^2)〗 + f_(n+1)^2 = f_n f_(n+1) + f_(n+1)^2 Induction hypothesis = f_n f_(n+1) + f_(n+1) f_(n+1) = f_(n+1) (f_n+ f_(n+1)) = f_(n+1) f_((n+1)+1) Definition: f_(n+2)=f_n+ f_(n+1)