You are not logged in.
Pages: 1
I don't understand why this proof holds , the logic is so strange
Prove:Every positive integer can be written as a product of primes
Here is the proof
Since an empty product is equal to 1 , we can write 1 as the empty product ofprimes , Let n>=2 , suppose that every postive integer less than n is a product of primes . If n is prime , we are done. If n is composite , then n=dm , where 1<d<m<n .By the induction hypothesis , d and m are both products of primes ,and so n=dm is a product of primes .
What I don't understand is that ,why induction can be used like that , It seems all proof is based on hypothesis , I wonder that will holds.
Numbers are the essence of the Universe
Offline
Try a few examples and you'll see.
2
3
4 = 2*2
5
6 = 3*2
7
8 = 2*2*2
9 = 3*3
10 = 3*5
11
12 = 2*2*3
You should start to see the pattern. As long as a number is not prime, we may reduce it to multiplication of lesser numbers until it is prime.
As for the proof, it's (as I said in the other thread) known as strong induction. You can assume everything less than some k holds, just like you can assume that k-1 holds in "weak" induction because of your base case. If a proof that uses strong induction uses something such as k-2, then you must have two base cases, otherwise the proof may not hold. Similarly, k-3 would require 3 base cases.
"In the real world, this would be a problem. But in mathematics, we can just define a place where this problem doesn't exist. So we'll go ahead and do that now..."
Offline
So,there are 2, 3, base cases induction right? That will be very kool and convenient!
Numbers are the essence of the Universe
Offline
Pages: 1