Mathematics for Computer Science

(Frankie) #1

Chapter 6 Induction140


Problem 6.3.
Prove by induction:


1 C

1


4


C


1


9


CC


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 CCnD
n.nC1/
2

But now we’re going to prove acontradictorytheorem!


False Theorem.For alln 0 ,


2 C 3 C 4 CCnD

n.nC1/
2

Proof. We use induction. LetP.n/be the proposition that 2 C 3 C 4 CCnD
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 CCnDn.nC1/=2. Then we can
reason as follows:


2 C 3 C 4 CCnC.nC1/DŒ 2 C 3 C 4 CCnçC.nC1/

D
n.nC1/
2

C.nC1/

D
.nC1/.nC2/
2
Free download pdf