Discrete Mathematics

----------------------'PROOF

METHODS

AND

INDUCTION

19

Blocks

and

Towers

Given an unlimited number

of

blocks

of

heights 3 and 7, towers

of

what height can

be

built?

Try

some possible heights:

1.

no

2.

no

3. yes, 3

4.

no

5.

no

6.

3+3

7.

7

8.

no

9.

3+3+3

10.

3+7

II.

no

12.

3+3+3+3

13.

7+3+3

14.

7+7

15.

3+3+3+3+3

16.

7+3+3+3

From this point on, can we make towers

of

greater height?

Define

P(n) to

be

"we can build a tower

of

height n". We prove this by strong induction:

Dill

\In;?;

12

(P(n))

1.

(Base)

P(l2)

Use 3 + 3 + 3 + 3

2. (lnductivestep)

Vn;?:l2[(Vi,l2::5i::5n(P(n)))=>P(n+l)]

3. QED Strong induction

Here is the idea for the inductive