Discrete Mathematics for Computer Science

50 CHAPTER 1 Sets, Proof Templates, and Induction

The examples that follow show the power of this proof method. Some of the inequal-

ities verified here by induction will appear again in later chapters when we consider the

complexity of programs.

Example 2. For any natural number n such that n > 2, show that n + 1 < n^2 .Since we

wish to prove our result for every n such that n > 2, we must choose no = 2 and let

T= {n E N: n > 2 andn + 1 < n^2 j

According to our template, the proof now has three essential parts: (i) a base step, (ii) an

inductive step, and (iii) an application of the Principle of Mathematical Induction.

For the base step, we must prove that no c T. In this case, we must prove for no = 2

that no + 1 < n2. When the proof of the base step is complete, we know T 0 0, because

no E T. We would then like to know what elements greater than no are also in T. The

elements of T other than no are found using the inductive step and the Principle of Math-

ematical Induction.

The inductive step begins by picking an arbitrary element n of T. We then write

out property P for n to see what this assumption tells us. Here, it means n > 2 and

n+l <n2.

To complete the inductive step, we must show that n + 1 e T. We write out property

P for n + 1 to see what we need to prove. In this case, it means that n + 1 > 2 and (n +

1) + 1 < (n + 1)2. We must then figure out how to prove that property P holds for n + 1

knowing that property P is true for n. When we complete this proof, the Principle of

Mathematical Induction tells us that for all n such that n > no, we have n E T.

Solution. Let no = 2. Let T = {n e N : n > 2 and n + 1 < n^2 ). Prove by induction that

n E T provided n > 2.

(Base step) To show that no E T, show that 2 > 2 and 2 + 1 < 22. Both are obviously

true. Therefore, 2 e T.

(Inductive step) Let n > no. Show that if n e T, then n + 1 E T. That is, assume n > 2

and n + 1 <n^2 , and prove that (i) n + 1 > 2 and (ii) (n + 1) + 1 < (n + 1)2. To prove

(i), observe that since n e T, we have n > 2. Therefore, n + 1 > 2. To prove (ii), use the

following chain of equalities and inequalities:

(n + 1)2 = n^2 + 2n + I

> (n + 1) + 2n + 1 (using the inductive hypothesis: n^2 > n + 1)

> (n + 1) + 1 (using the inductive hypothesis: n > 2 > 0)

Therefore, n + I E T.

By the Principle of Mathematical Induction, T = {n E N : n > 2}. 0

You can see the parts of the template being used as you study Example 3. Identify the

steps of the template as they appear in this example.

Example 3. Recall that n! = n .(n - 1). (n - 2)... 2. 1. For any natural number n such

that n > 4, prove that n! > n^2.

Solution. Let no = 4. Let T = {n E N : n > 4 and n! > n^2 }. Prove by induction for

every natural number n that n E T provided that n > 4.