Discrete Mathematics

______________________

PROOF

METHODS

AND INDUCTION

11

This worked

out

nicely because the left hand side (LHS)

of

the

n + 1 equation was easily expressible

in terms

of

then

equation. Also, here the choice

of

P(n)

came directly

out

of

the theorem statement. Some-

times

it

is not so obvious.

Also

in

this example, note that the inductive technique did not help us

to

come

up with the correct expression

n(n

2

+ l) for the summation,

but

only

to

prove that

it

is correct.

We

shall

see

how

to

come

up

with such sums

when

we get

to

the analysis methods section

of

the

course.

MORE

SIMPLE

INDUCTION

Divisibility

Definition Given

two

integers x

andy,

we say ...