Discrete Mathematics

______________________

,PROOF

METHODS AND INDUCTION 15

I Proof I Induction. The base,

P(l),

is as before. For the inductive step, n

~

1,

start with an arbitrary

2"

+

1

x

2"+

1

courtyard with an arbitrary square to be left blank. Let's try to tile this, assuming tilings

of

any 2" x

2"

courtyard with

any

square blank.

Again, divide the

2"+

1

x

2"+

1

courtyard into four 2" x

2"

quadrants. One will contain the square that

must be left blank; it can be tiled by inductive hypothesis.

Next, put one tile in the centre, covering one square in each

of

the other 3 quadrants. Now use the

inductive hypothesis three more times to tile the rest

of

the 3 ...