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$.
