Discrete Mathematics for Computer Science

Strong Form of Mathematical Induction 69

n = pi "P2""Pi Aqlj q2...qj

so n can be factored into a product of primes. Therefore, n E T.

By the Strong Form of Mathematical Induction, T = {n e N : n > 1}. 0

1.10.1 Using the Strong Form of Mathematical Induction

The Strong Form of Mathematical Induction is often used to prove a closed form for the

elements of a recursively defined sequence like the Fibonacci sequence. A closed form

for the elements is a representation for each term that can be computed without knowing

any other element(s) of the sequence. Exercise 16 in Section 1.11 is to show that the nth

Fibonacci number can be computed as

1 (I+-f)ln±-1 ~ 11V l~- Il,-)n\ 5 l

Fn =--I"---/I"

.,/5- \2 1-

for each n E N. This expression is a closed form for the Fibonacci sequence.

The next example is similar to the result about Fibonacci numbers, but the computa-

tions are less complex. The verification of the closed form for the Fibonacci numbers is

left as an exercise.

Example 1. The terms of a sequence are given recursively as

ao=0, al =2, and an =^4 (al1-a,-2) forn_>^2

Prove by induction that bn = n. 2' is a closed form for the sequence. That is, prove that

an = bn for every n E N.

Solution. Let no = 0 and T = {n E N : bn = an}. In this case, two elements of the se-

quence, ao and al, are defined directly. As is fairly typical, these special cases constitute

the base cases for the proof.

(Base step) The two base cases are n = 0 and n = 1 Evaluating b 0 and bj gives bo = 0

and b 1 = 2. Thus, ao = bo and al = bl, so 0, 1 E T.

(Inductive step) We now deal with any n such that n > 2. Assume that for all k where

0 < k < n, k E T. Prove that n E T by showing an = bn. Since n > 2, n - 1, n - 2 > 0,

son - 1, n -2 E T.

an =^4 (an-I - an-2) (by definition of an)

= 4((n - 1)2n-1 - (n - 2)2n-2) (by inductive hypothesis)

= 4(n- 2n-1 - 2n-1 - n. 2n-2 + 2. 2n-2)

= 4(n(2n- - 2n-2) - (2n-1 - 2.2n-2))

= 4(n(2. 2n-2 - 2n-2) - (2.2n-2 - 2. 2n-2))

=4.n.2n-2 = n.2n

Therefore, bn = an and n E T.

By the Strong Form of Mathematical Induction, T = N. That is, bn = n 2n is a closed
form for the terms of the recursively defined sequence. E