Mathematics for Computer Science

Chapter 5 Induction146

2. Identify the induction hypothesisP.n/.


3. Establish the base case.


4. Prove thatP.n/)P.nC1/.


5. Conclude thatP.n/holds for alln 1.

as in the five part template.

Problem 5.4.
Prove by induction onnthat

1 CrCr^2 C


CrnD

rnC^1  1

r 1

(5.7)

for alln 2 Nand numbersr¤ 1.

Problem 5.5.
Prove by induction:

1 C

1

4

C

1

9

C


C

1

n^2

< 2

1

n

; (5.8)

for alln > 1.

Problem 5.6. (a)Prove by induction that a 2 n 2 ncourtyard with a 1  1 statue
of Bill ina cornercan be covered with L-shaped tiles. (Do not assume or reprove
the (stronger) result of Theorem 5.1.2 that Bill can be placed anywhere. The point
of this problem is to show a different induction hypothesis that works.)

(b)Use the result of part (a) to prove the original claim that there is a tiling with
Bill in the middle.

Problem 5.7.
We’ve proved in two different ways that

1 C 2 C 3 C


CnD

n.nC1/

2

But now we’re going to prove acontradictorytheorem!