Discrete Mathematics for Computer Science

Mathematical Induction 49

In the proof of Theorem 1, T was defined to be the set of all natural numbers for which

the formula

n

Y- i = n(n + 1)/2

i=O

is true. So, in that case, we choose no = 0. The base step of that proof showed that no =

0 E T. The inductive step showed that if n E T, then n + 1 (" T. Now, by the Principle of

Mathematical Induction, T = {n e N: n > no = 0} = N.

We give a picture of what is involved in an inductive proof in Figure 1.17.

Base step Inductive step

0M

Principle of Mathematical Induction

Values for which the property is TRUE

Figure 1.17 The parts of an inductive proof.

1.72 A Template for Constructing Proofs by Induction

Template 1.12 should help you to understand and construct a proof by induction.

To construct a proof using the Principle of Mathematical Induction, choose an no E

N appropriate to the problem. Let T- = In E N : n >_ no and property P holds for n}I:

"* (Base step) Prove that no e T.

"* (Inductive step) Let n E 7, and prove that n + 1 E T. The assumption that n E

T is called the inductive hypothesis.

"* Infer by the Principle of Mathematical Induction that every natural number n > no

is in T.