2.4 The Principle of Mathematical Induction
In the world of mathematics, the well-ordering principle (WOP) is often taken as an axiom. In this section, we derive a theorem based on the WOP called the principle of mathematical induction (PMI). In high school, you might have done what is called proofs by induction, where you built an argument that was analagous to knocking down an inﬁnite row of dominoes. First, you showed ﬁguratively that you can knock the ﬁrst domino down. Then you showed that if the nth domino falls, then so does the (n + 1)st. This very, very important proof technique is useful when the theorem you’re trying to prove has a form like one of these:
1 + 2 + 3 + ··· + n = (n(n + 1))/2
A ∪ (B1 ∩ B2 ∩ ··· ∩ Bn ) = (A ∪ B1 ) ∩ (A ∪ B2 ) ∩ ··· ∩ (A ∪ Bn )
where the theorem makes a statement about a ﬁnite but unspeciﬁed n number of things, and you want to prove that the claim is true for any n ∈ N.