Discrete Mathematics

----------------------------------------------·PROOFMETHODSANDINDUCTION

29

Base

case Show Q(k), same as P(k), which has already been shown as part

of

the strong induction proof.

Inductive

step

Show Q(n)

~

Q(n + 1), in other words, P(k)

1\

P(k +

1)

1\

.•.

1\

P(n)

~

P(k)

1\

P(k +

1)

1\

...

P(n)

1\

P(n + 1).

This really amounts to showing P(k)

1\

P(k + 1)

1\

....

1\

P(n)

~

P(n +

1)

. But this has already been

shown in the strong induction proof.

Of

course, any ordinary inductive proof is a strong induction proof as well.

We

are allowed to assume

P(l),

... , P(n) to prove P(n + 1), but all we actually use is P(n).

Induction and strong induction ...