5
$\begingroup$

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

Question:

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
    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?2012-08-24
  • 0
    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 ?2012-08-24
  • 0
    so you say that this fact needs to be proved too, not to be skipped by words.2012-08-24
  • 1
    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.2012-08-24

1 Answers 1