I couldn't find what is wrong with this strong induction proof, any one knows ?


A sequence of numbers is weakly decreasing when each number in the sequence is $\geq$ 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 pusp, for short.

Explain what’s bogus about the proof.

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

For example, $252 = 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 the lemma by strong induction, letting the induction hypothesis, $P(n)$ be

                         n is a pusp.

So the lemma will follow if we prove that $P(n)$ holds for all $n \geq 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 \geq 2$ and that $i$ is a pusp for every integer $i$ where $2 \leq i < n+1$. We must show that $P(n+1)$ holds, namely, that $n + 1$ is also a pusp. We argue by cases:

If $n+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, $n + 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 = k.m$ for some integers $k,m$ such that $2 \leq k,m < n+1$. 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 \geq2$.

  • 6
    $\begingroup$ Suppose that $km$ and $rs$ are two different non-trivial factorizations of $n+1$; how do you know that the merged prime sequence from $km$ is the same as the merged prime sequence from $rs$? In other words, how do you know that you have uniqueness? $\endgroup$ – Brian M. Scott Aug 24 '12 at 17:00
  • $\begingroup$ but both have unique prime factoization and if we sort n+1 will have too. do you have counter example so that I can understand ? $\endgroup$ – mehdi Aug 24 '12 at 17:08
  • $\begingroup$ so you say that this fact needs to be proved too, not to be skipped by words. $\endgroup$ – mehdi Aug 24 '12 at 17:11
  • 1
    $\begingroup$ The theorem is true, so there isn’t a counterexample. The problem is that your argument doesn’t prove that there is no counterexample. The fact that $k,m,r$, and $s$ all have unique factorizations does not obviously guarantee that $km$ and $rs$ have the same factorizations. $\endgroup$ – Brian M. Scott Aug 24 '12 at 17:15

The flaw in the proof has been explained in a comment by Brian M. Scott. We give an example that illustrates the breakdown. That example cannot be the ordinary integers, since Unique Factorization holds there.

Suppose that our world consists of the set $E$ of even positive integers. Call such an integer eprime if it cannot be expressed as the product of elements of $E$. So for example $6$ is eprime, while $12$ is not.

One could use almost exactly the same argument to "prove" that every element of $E$ is a pusep (the ep at the end is for eprime). However, note that $180=(18)(10)=(30)(6)$, and all four of $18$, $10$, $30$, and $6$ are eprime.

  • $\begingroup$ very good example thanks. $\endgroup$ – mehdi Aug 24 '12 at 17:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.