A sequence of numbers is weakly decreasing when each number in the sequence is  the numbers after it. (This implies that a sequence of just one number is weakly decreasing.) Here’s a bogus proof of a very important true fact, every integer greater than 1 is a product of a unique weakly decreasing sequence of primes —a p u sp, for short. Explain what’s bogus about the proof.

Lemma 6.4.1. 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.1 by strong induction, letting the induction

hypothesis, P.(n), be n is a pusp:

So Lemma 6.4.1 will follow if we prove that P.(n) holds for all n  ≥2.

Base Case (n = 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 that n ≥2 and that i is a pusp for every integer i where 2 ≥ i < n C 1. We must show that P.(n + 1) holds, namely, that n + 1 is also a pusp. We argue by cases: If nC1 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, n C 1 has no other prime factors. So n + 1 is a pusp, that is P.(n + 1) holds in this case. Otherwise, n+1 is not prime, which by definition means n+1 = km for some integers k;m such that 2 _ k;m < nC1. Now by the strong induction hypothesis, we know that k and m are pusps. It follows immediately that by merging the unique prime sequences for k and m, in sorted order, we get a unique weakly decreasing sequence of primes whose product equals n+1. So n+1 is a pusp, in this case as well. So P.(n + 1) holds in any case, which completes the proof by strong induction that P.(n) holds for all n ≥ 2.