Discrete Mathematics for Computer Science

48 CHAPTER 1 Sets, Proof Templates, and Induction

Since we have proved that the formula is true for n = 0 and is true for n + 1 whenever

it is true for n, we can conclude that the formula is valid for all natural numbers. This

reasoning is call the Principle of Mathematical Induction. 0

Let T= {n E N : 0+... +n = n(n + 1)/2}:

1. Since 0 E T by the base step, by the inductive step, 0 + 1 = 1 E T.

2. Apply the inductive step again: since 1 E T, 1 + 1 = 2 E T.

3. And again: since 2 c T, 2 + 1 = 3 E T.

To prove that 100 E T, apply the inductive step 100 times. To prove that 10,000 E T,

apply it 10,000 times. For any specific natural number n, one can show that n E T by

showing that 0 E T and then applying the inductive step n times. An inductive proof is

often visualized as an infinite line of dominoes, with the dominoes being pushed over one

at a time starting with the first one. Figure 1.16 gives another way of thinking about what

happens in an inductive proof.

0 1 2 3 4 5 6 7 8 9 10 11

Figure 1.16 Falling dominoes.

A First Form of the Principle of Mathematical Induction

The Principle of Mathematical Induction gives a method for writing a single proof that

proves all natural numbers are in T. Sometimes, this statement of the Principle of Mathe-

matical Induction is called its first form.

Principle of Mathematical Induction

Let T be a subset of the natural numbers (that is, T C N), and let no E N. Suppose

(Base step) no E T, and

(Inductive step) for all natural numbers n such that n > no, if n e T, then

n+1 E T.

Then, every natural number greater than or equal to no is in T. That is,

T = {n : n E N and n > no]