Discrete Mathematics for Computer Science

Strong Form of Mathematical Induction 71

In practice, you may often try to work out the Inductive step first. You will then see

certain values-and you may as well assume that no must be one of them-for which the ar-

gument doesn't use the inductive hypothesis. These values are identified as the base cases.

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

ao=l, al=1, and an =2.anl_+3.an_2forn>>2

Prove by induction that bn = ½.3n + ½ .(- 1 )n is a closed form for the sequence.

Solution. Letno =OandT= {n eN :b, =an}.

(Base step) Identify n = 0, 1 as the base cases. The defined values in such a definition

often are the base cases. Evaluate b 0 and bl directly:

bo = 1(30 + (-1)O) = 1(1 + 1) = 1 = ao

bl = 1(31 + (-1)1) = 1(3 - 1) = 1 = al

So, 0, 1 e T.

(Inductive step) Now, let n > 2, and assume for k = 0, 1,...,n - 1 that k E T. Prove

that n e T by showing that an = bn:

an = 2at-I + 3an-2 (by definition of an)

= 2. 1 (3n-1 + (-1)n-1) + 3. 1(3Q 2 + (-1)n-2) (by inductive hypothesis)

2 2

= 3fn-1 + (-1)n-1 + 3 .3n-2 + 2(-- 2-

2 2

We know that (-I)n-2 = (-1)n, (-1)n-1 --(-1)n, and 3n-1 = 3 .3n-2. So,

(^3 3)
an = 3.3fn-2 +- 3. 3fn-2 - )n + 3-(1)
2 2
=29"3 n-2 +- I(-1)n

2 +

1 3n + I(-1)n

2 2

=bn

as desired. Therefore, n E T.

By the Strong Form of Mathematical Induction, T = N. That is, b, = •n +-

2 (- 1)n is a closed form for the terms of the recursively defined sequence.^0

Unlikely as it might seem, we can use the Strong Form of Mathematical Induction to

show which amounts of postage can be made from a fixed number of several denominations

of stamps.

Example 3. The country of Oz issues only 3-cent and 8-cent stamps. What amounts of
postage are possible with just these two kinds of stamps?

Solution. Obviously, some packages will require a lot of surface area to affix all the
required postage! By experimentation, we can find out that all of 0, 3, 6, 8, 9, 11, 12, 14,
15, 16, 17, 18, 19, 20, and 21 cents are possible. Since we are getting all amounts of 14