Mathematics for Computer Science

5.4. State Machines 145

Figure 5.11 The induction hypothesis for the false theorem.

Inductive step: Assume thatP.n/is true for somen 0 ; that is, for every location
of Bill in a 2 n 2 ncourtyard, there exists a tiling of the remainder. Divide the
2 nC^1  2 nC^1 courtyard into four quadrants, each 2 n 2 n. One quadrant contains
Bill (Bin the diagram below). Place a temporary Bill (Xin the diagram) in each of
the three squares lying near this quadrant as shown in Figure 5.11.
We can tile each of the four quadrants by the induction assumption. Replacing
the three temporary Bills with a single offset tile completes the job. This proves
thatP.n/impliesP.nC1/for alln 0. ThusP.m/is true for allm 2 N, and the
ability to place Bill in the center of the courtyard follows as a special case where
we put Bill in a central square. 

Class Problems

Problem 5.3.
Use induction to prove that

13 C 23 C


Cn^3 D



n.nC1/

2

 2

: (5.6)

for alln 1.
Remember to formally

1. Declare proof by induction.