Mathematics for Computer Science

Chapter 6 Induction140

Problem 6.3.
Prove by induction:

1 C

1

4

C

1

9

C


C

1

n^2

< 2

1

n

; (6.7)

for alln > 1.

Problem 6.4. (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 6.1.1 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 6.5.
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!

False Theorem.For alln 0 ,

2 C 3 C 4 C


CnD

n.nC1/

2

Proof. We use induction. LetP.n/be the proposition that 2 C 3 C 4 C


CnD
n.nC1/=2.
Base case:P.0/is true, since both sides of the equation are equal to zero. (Recall
that a sum with no terms is zero.)
Inductive step:Now we must show thatP.n/impliesP.nC1/for alln 0. So
suppose thatP.n/is true; that is, 2 C 3 C 4 C


CnDn.nC1/=2. Then we can
reason as follows:

2 C 3 C 4 C


CnC.nC1/DΠ2 C 3 C 4 C


CnçC.nC1/

D

n.nC1/

2

C.nC1/

D

.nC1/.nC2/

2