6.4. Strong Induction vs. Induction vs. Well Ordering 155
Homework Problems
Problem 6.23.
A group ofn 1 people can be divided into teams, each containing either 4 or
7 people. What are all the possible values ofn? Use induction to prove that your
answer is correct.
Problem 6.24.
The following Lemma is true, but theproof given for it below is defective. Pin-
pointexactlywhere the proof first makes an unjustified step and explain why it is
unjustified.
Lemma 6.4.3. For any primepand positive integersn;x 1 ;x 2 ;:::;xn, ifp j
x 1 x 2 :::xn, thenpjxifor some 1 in.
Bogus proof.Proof by strong induction onn. The induction hypothesis,P.n/, is
that Lemma holds forn.
Base casenD 1 : WhennD 1 , we havepjx 1 , therefore we can letiD 1 and
concludepjxi.
Induction step: Now assuming the claim holds for allkn, we must prove it
fornC 1.
So supposepjx 1 x 2 xnC 1. LetynDxnxnC 1 , sox 1 x 2 xnC 1 Dx 1 x 2 xn 1 yn.
Since the righthand side of this equality is a product ofnterms, we have by induc-
tion thatpdivides one of them. Ifpjxifor somei < n, then we have the desired
i. Otherwisepjyn. But sinceynis a product of the two termsxn;xnC 1 , we have
by strong induction thatpdivides one of them. So in this casepjxiforiDnor
iDnC 1.
Problem 6.25.
The Fibonacci numbers
0;1;1;2;3;5;8;13;:::
are defined as follows. LetF.n/be thenth Fibonacci number. Then
F.0/WWD0; (6.14)
F.1/WWD1; (6.15)
F.m/WWDF.m 1/CF.m 2/ form2: (6.16)
Indicate exactly which sentence(s) in the following bogus proof contain logical
errors? Explain.