Discrete Mathematics

222

DISCRETE

MATHEMATICS'--------------------------

It

can

be

summarized as follows:

Suppose

we

want to prove a property

of

positive integers.

Also

suppose that

we

can

prove two facts:

(a)

n = 1 has the property

of

positive integers,

and

(b) whenever

n-

1 has the property, then n also has the property (n

~

1)

.

The

principle

of

induction says that

if

(a)

and

(b) are true, then every natural

number

has the property.

For

more details

see

the first chapter

of

this book.

Often the best way to try to carry

out

an induction

proof

is the following: we

try

to prove the statement

(for a general value

of

n), and

we

are allowed

to

use that the statement ...