1 Answer | Add Yours
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.
We’ve answered 334,126 questions. We can answer yours, too.Ask a question