Page 368 - Discrete Mathematics and Its Applications

5.3 Recursive Definitions and Structural Induction 347

Recall from Section 2.4 that the Fibonacci numbers, f 0 ,f 1 ,f 2 ,..., are defined by the
equations f 0 = 0,f 1 = 1, and

f n = f n−1 + f n−2

for n = 2, 3, 4,.... [We can think of the Fibonacci number f n either as the nth term of the
sequence of Fibonacci numbers f 0 ,f 1 ,... or as the value at the integer n of a function f (n).]
We can use the recursive definition of the Fibonacci numbers to prove many properties of
these numbers. We give one such property in Example 4.
√
EXAMPLE 4 Show that whenever n ≥ 3, f n >α n−2 , where α = (1 + 5)/2.

Solution: We can use strong induction to prove this inequality. Let P (n) be the statement
f n >α n−2 . We want to show that P (n) is true whenever n is an integer greater than or equal to 3.
BASIS STEP: First, note that
√
2
α< 2 = f 3 , α = (3 + 5)/2 < 3 = f 4 ,

so P(3) and P(4) are true.
INDUCTIVE STEP: Assume that P(j) is true, namely, that f j >α j−2 , for all integers j with
3 ≤ j ≤ k, where k ≥ 4.We must show that P(k + 1) is true, that is, that f k+1 >α k−1 . Because
2
2
α is a solution of x − x − 1 = 0 (as the quadratic formula shows), it follows that α = α + 1.
Therefore,
k−1 2 k−3 k−3 k−3 k−3 k−2 k−3
α = α · α = (α + 1)α = α · α + 1 · α = α + α .

By the inductive hypothesis, because k ≥ 4, we have

f k−1 >α k−3 , f k >α k−2 .

Therefore, it follows that

f k+1 = f k + f k−1 >α k−2 + α k−3 = α k−1 .

Hence, P(k + 1) is true. This completes the proof. ▲

Remark: The inductive step shows that whenever k ≥ 4, P(k + 1) follows from the assumption
that P(j) is true for 3 ≤ j ≤ k. Hence, the inductive step does not show that P(3) → P(4).
Therefore, we had to show that P(4) is true separately.

We can now show that the Euclidean algorithm, introduced in Section 4.3, uses O(log b)
divisions to find the greatest common divisor of the positive integers a and b, where a ≥ b.

THEOREM 1 LAMÉ’S THEOREM Let a and b be positive integers with a ≥ b. Then the number of
divisions used by the Euclidean algorithm to find gcd(a, b) is less than or equal to five times
the number of decimal digits in b.