Mathematics for Computer Science

Chapter 6 Induction154

Here’s a bogus proof of a very important true fact, every integer greater than 1 is
aproduct of a unique weakly decreasing sequence of primes—a pusp, for short.
Explain what’s bogus about the proof.

Lemma 6.4.2.Every integer greater than 1 is a pusp.

For example, 252 D 7
3
3
2
2 , and no other weakly decreasing sequence of
primes will have a product equal to 252.

Bogus proof.We will prove Lemma 6.4.2 by strong induction, letting the induction
hypothesis,P.n/, be
nis a pusp:

So Lemma 6.4.2 will follow if we prove thatP.n/holds for alln 2.
Base Case(nD 2 ):P.2/is true because 2 is prime, and so it is a length one
product of primes, and this is obviously the only sequence of primes whose product
can equal 2.
Inductive step: Suppose thatn 2 and thatiis a pusp for every integeriwhere
2 i < nC 1. We must show thatP.nC1/holds, namely, thatnC 1 is also a
pusp. We argue by cases:
IfnC 1 is itself prime, then it is the product of a length one sequence consisting
of itself. This sequence is unique, since by definition of prime,nC 1 has no other
prime factors. SonC 1 is a pusp, that isP.nC1/holds in this case.
Otherwise,nC 1 is not prime, which by definition meansnC 1 Dkmfor some
integersk;msuch that 2 k;m < nC 1. Now by the strong induction hypothesis,
we know thatkandmare pusps. It follows immediately that by merging the unique
prime sequences forkandm, in sorted order, we get a unique weakly decreasing
sequence of primes whose product equalsnC 1. SonC 1 is a pusp, in this case as
well.
SoP.nC1/holds in any case, which completes the proof by strong induction
thatP.n/holds for alln 2.


Problem 6.22.
Define thepotential,p.S/, of a stack of blocks,S, to bek.k1/=2wherekis the
number of blocks inS. Define the potential,p.A/, of a set of stacks,A, to be the
sum of the potentials of the stacks inA.
Generalize Theorem 6.3.1 about scores in the stacking game to show that for any
set of stacks,A, if a sequence of moves starting withAleads to another set of stacks,
B, thenp.A/p.B/, and the score for this sequence of moves isp.A/p.B/.
Hint:Try induction on the number of moves to get fromAtoB.