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.