Section 3.1 Recursive Definitions
161
Now show the case for k + 1, where k + 1 ≥ 3. (We’ve already proved the
case for n = 1 and the case for n = 2.) Thus we want to show
F(k + 1 + 4) 0 3F(k + 1 + 2) − F(k + 1)
or
F(k + 5) 0 3F(k + 3) − F(k + 1)
From the recurrence relation for the Fibonacci sequence, we have
F(k + 5) = F(k + 3) + F(k + 4)
(F at any value is the sum of F at
the two previous values)
and by the inductive hypothesis, with r = k − 1 and r = k, respectively,
F(k + 3) = 3F(k + 1) − F(k − 1)
and
F(k + 4) = 3F(k + 2) − F(k)
Therefore
F(k + 5) = F(k + 3) + F(k + 4)
= 33F(k + 1) − F(k − 1) 4 + 33F(k + 2) − F(k) 4
= 3 3F(k + 1) + F(k + 2) 4 − 3F(k − 1) + F(k) 4
= 3F(k + 3) − F(k + 1)
(using the recurrence relation again)
This completes the inductive proof.
PRaCtiCe 3 In the inductive proof of Example 3, why is it necessary to prove n = 2 as a special case? ■
example 4
The formula
F(n + 4) = 3F(n + 2) − F(n) for all n ≥ 1
of Example 3 can also be proved without induction, using just the recurrence relation from the definition of Fibonacci numbers. The recurrence relation
F(n + 2) = F(n) + F(n + 1)
can be rewritten as
F(n + 1) = F(n + 2) − F(n)
(1)