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

  • Thread starter ver_mathstats
  • Start date
  • Tags
    Induction
In summary: This is exactly what the strong induction argument does when you look at it closely.The only difference between the two is that the strong induction argument looks at all ##n \leq m## simultaneously while the argument that I have given looks at them one at a time. But if you are looking at them one at a time, then you are essentially checking them in order from lowest to highest, which is exactly what the strong induction argument does.
  • #1
ver_mathstats
260
21

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 = p1, where p1 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?
 
Physics news on Phys.org
  • #2
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##.
 
  • #3
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?
 
  • #4
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".
 
  • Like
Likes BvU
  • #5
Orodruin said:
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.
 
  • #6
Math_QED said:
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.
 

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

1. What is strong induction?

Strong induction is a mathematical proof technique that allows us to prove a statement for all natural numbers greater than or equal to a given number. It is a more powerful version of mathematical induction, which only allows us to prove a statement for a specific number.

2. How is strong induction used to prove that every integer greater than 1 is a product of primes?

To prove that every integer greater than 1 is a product of primes using strong induction, we first prove the statement for a base case, such as 2. Then, we assume that the statement is true for all integers up to a certain number, and use this assumption to prove the statement for the next integer. By repeating this process, we can prove the statement for all integers greater than 1.

3. Why is strong induction necessary for proving this statement?

This statement cannot be proven using regular mathematical induction because it requires the assumption that the statement is true for all integers up to a certain number. Strong induction allows us to make this assumption and use it to prove the statement for the next integer.

4. Can strong induction be used to prove other statements?

Yes, strong induction can be used to prove many other mathematical statements, particularly those that involve the natural numbers. It is a powerful proof technique that is commonly used in number theory and other areas of mathematics.

5. Are there any limitations to using strong induction?

While strong induction is a useful proof technique, it may not be applicable to all mathematical statements. In some cases, other proof techniques may be more suitable or necessary. Additionally, strong induction can be more complex and challenging to use compared to regular mathematical induction.

Similar threads

  • Calculus and Beyond Homework Help
Replies
13
Views
2K
  • Calculus and Beyond Homework Help
Replies
7
Views
167
  • Calculus and Beyond Homework Help
Replies
3
Views
598
  • Calculus and Beyond Homework Help
Replies
1
Views
1K
  • Calculus and Beyond Homework Help
Replies
6
Views
994
  • Calculus and Beyond Homework Help
Replies
16
Views
1K
  • Calculus and Beyond Homework Help
Replies
5
Views
1K
  • Calculus and Beyond Homework Help
Replies
3
Views
773
  • Calculus and Beyond Homework Help
Replies
1
Views
552
  • Calculus and Beyond Homework Help
Replies
5
Views
2K
Back
Top