Math Is Fun Forum

  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2007-02-02 08:57:26

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

HELP , Number theory

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

#2 2007-02-02 10:12:10

Ricky
Moderator
Registered: 2005-12-04
Posts: 3,791

Re: HELP , Number theory

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

#3 2007-02-05 09:12:14

Stanley_Marsh
Member
Registered: 2006-12-13
Posts: 345

Re: HELP , Number theory

So,there are 2, 3, base cases induction right?  That will be very kool and convenient!


Numbers are the essence of the Universe

Offline

Board footer

Powered by FluxBB