0
$\begingroup$

I'm reading this wikipedea article:

We need to show that every integer greater than $1$ is a product of primes. By induction: assume it is true for all numbers between $1$ and $n$. If $n$ is prime, there is nothing more to prove (a prime is a trivial product of primes, a "product" with only one factor). Otherwise, there are integers $a$ and $b$, where $n = ab$ and $1 < a ≤ b < n$. By the induction hypothesis, $a = p_1p_2...p_j$ and $b = q_1q_2...q_k$ are products of primes. But then $n = ab = p_1p_2...p_ jq_1q_2...q_k$ is a product of primes.

They said, "If n is prime, there is nothing more to prove...". Haven't we have to show that $P(n) \implies P(n+1)$? Even in the second case where $n$ is not supposed to be prime they do not show that FTA exists for the $n+1$th number. Why is that?

My understanding:

There are two cases, either $n+1$ is prime or it is not. If it is prime then it's fine. If it is not prime then then we must have $n+1=a_1a_2....a_p$ s.t. $a_i<n$ but every number less than $n$ can be factorized in primes so $n+1$ can also be.

$\endgroup$
  • 5
    $\begingroup$ That proof proceeds by strong induction. $\endgroup$ – Zircht Nov 30 '14 at 4:21
  • $\begingroup$ To add to Zircht's comment. This means we assume it is true for all $k<n$ and prove that it is true for $n$. See here. $\endgroup$ – Eoin Nov 30 '14 at 4:22
  • $\begingroup$ Oh, I wasn't aware of this kind of Induction. $\endgroup$ – user103816 Nov 30 '14 at 4:28
  • 1
    $\begingroup$ When it says "assume it is true for all numbers between $1$ and $n$", it means strictly between $1$ and $n$. $\endgroup$ – Gerry Myerson Nov 30 '14 at 4:52
  • 2
    $\begingroup$ You can use "usual induction" to prove that "strong induction" is a valid method of argument. They are logically equivalent, but sometimes strong induction is a more convenient way to do things. $\endgroup$ – Gerry Myerson Nov 30 '14 at 22:33

Your Answer

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

Browse other questions tagged or ask your own question.