6.4. Strong Induction vs. Induction vs. Well Ordering 141
Above, we group some terms, use the assumptionP.n/, and then simplify. This
shows thatP.n/impliesP.nC1/. By the principle of induction,P.n/is true for
alln 2 N.
Where exactly is the error in this proof?Homework Problems
Problem 6.6.
Claim 6.4.1.If a sequence of positive integers has sumn 1 , then the product of
elements in the sequence is at most 3 n=3.
For example, the sequence 2, 2, 3, 4, 4, 7, has the sum:
2 C 2 C 3 C 4 C 4 C 7 D22;and sure enough, the product is:
2 2 3 4 4 7 D 1344
3 22=3
3154:2;I:(a)Use strong induction to prove thatn 3 n=3for every integern 0.(b)Prove the claim by induction.Hint:Use induction on thelength of the sequencerather than on the value of the
sum.
Problem 6.7.
For any binary string, ̨, let num. ̨/be the nonnegative integer it represents in
binary notation. For example, num. 10 /D 2 , and num. 0101 /D 5.
AnnC 1 -bit adderadds twonC 1 -bit binary numbers. More precisely, an
nC 1 -bit adder takes two lengthnC 1 binary strings
̨nWWDan:::a 1 a 0 ;
ˇnWWDbn:::b 1 b 0 ;and a binary digit,c 0 , as inputs, and produces a lengthnC 1 binary string
nWWDsn:::s 1 s 0 ;