Strong Induction: Proving Every Int n>1 is a Product of Primes

[ver_mathstats]

Homework Statement

Every positive integer n > 1 can be written as a product of primes.

Proof: We prove the result by strong induction on n, where n≥2.

Base Case: Note that 2 is prime, hence 2 = p₁, where p₁ is prime.

Inductive Step: Let m ∈ ℤ with m ≥ 2 and assume for all integers k with 2 ≤ k ≤ m, k is a product of primes. We must prove that m + 1 is a product of primes.

We split into two cases, case 1 being m + 1 is prime, and case 2 being m + 1 is not prime.

Why do we use strong induction rather than induction?

Homework Equations

The Attempt at a Solution

I am a little bit confused are we using strong induction because it would not work if n is equal to 1?

If so, why else would we need to prove this with strong induction?

 

[Orodruin]

Did you do the actual proof? The reason you need strong induction is that the argument you will need will be based on all integers smaller than $m+1$ being products of primes, not just $m$. In other words, it will not be sufficient to assume that the statement is true for $m$ to show that it is true for $m+1$.

 

[member 587159]

The most elegant proof (in my opinion) of this doesn't use induction.

Look at the set of all natural numbers $n > 1$ that can't be written as a product of primes. If this set is non-empty (it is our task to prove it is empty, so we want to find a contradiction), we can pick a minimal element $m$ in this set. Thus, $m$ can not be written as a product of primes, meaning that $m$ isn't prime itself or it would be a trivial product. But that $m$ isn't prime means that we can write $m = n_1 n_2$ with $n_1 \neq 1 \neq n_2$. What can you deduce about $n_1,n_2$ and $m$, given that $m$ is minimal? Do you see the contradiction?

 

[Orodruin]

Honestly, I think that that argument is essentially the same as the strong induction argument, which goes through all of the integers looking for the minimal such element and discovering that "nope, this isn't it either".

 

[member 587159]

Honestly, I think that that argument is essentially the same as the strong induction argument, which goes through all of the integers looking for the minimal such element and discovering that "nope, this isn't it either".

I disagree. Induction here obscures things. Moreover, the technique I applied works in more general ring theoretic settings whereas induction is limited to the naturals.

 

[Orodruin]

Induction here obscures things.

This may be true, but you are missing my point. The essence of the argument itself for the smallest such number is the same in this case - clearly if it is true for all $n \leq m$, then you are testing whether or not $m+1$ is the smallest such number.