Homework Help

What is the proof for the math theory of induction?

user profile pic

kimsteinberg | (Level 1) Salutatorian

Posted September 24, 2012 at 4:36 PM via web

dislike 0 like

What is the proof for the math theory of induction?

1 Answer | Add Yours

user profile pic

degeneratecircle | High School Teacher | (Level 2) Associate Educator

Posted September 24, 2012 at 5:32 PM (Answer #1)

dislike 2 like

Are you asking why the technique of proof by induction is valid? Often this is just assumed as an axiom, in which case there is no proof. It's just built into the system. The Peano axioms, for instance, have the principle of induction as an axiom.

Induction is equivalent to the well-ordering principle, though, so if you assume well-ordering, then you can prove induction works (and vice versa). If that's what you have to do, it goes as follows:

Assume well-ordering, so that every nonempty subset of the natural numbers has a smallest element. Now, if P(n) is some statement depending on n and P(0) is true, and also if the truth of P(n) implies the truth of P(n+1) for all n, we can now prove that P(n) is true for all n. We'll use a proof by contradiction.

Assume that P(n) is false for some natural number n. Then by well-ordering there must be some smallest n for which P(n) is false. Call this smallest value k. Note that k is not equal to 0, since we're assuming that P(0) is true. Thus, and this is a crucial part of the proof, k-1 is a natural number. Since k is the smallest natural number for which P(k) is false, P(k-1) must be true. But we've assumed that if P(k-1) is true, then so is P(k), which is a contradiction because we said above that P(k) is false. Thus there can't be any natural number n such that P(n) is false, which is what we wanted to prove.

The links below give more information and a slightly different form of my proof.

 

 

Sources:

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes