The concept of mathematical induction is extremely powerful. At each point in time, it simply asks us to prove something small. Just show the next step, and the next step, and the next step. How is this done? We first show that the first statement is true. And then we show that if a statement is true, then the next statement must be true. If so, this implies that all of the statements must be true, for very little work.
Let's state this idea mathematically.
Consider a set \( S \) satisfying the following properties:
(1) The integer 1 is in the set.
(2) If the positive integer \( k \) is in the set, then so is \( k+1 \).
Then it seems quite natural to think that the set \( S \) must consist of all natural numbers. Indeed, this is true. And because this statement seems so obvious, we turn to a proof by contradiction.
Proof. Suppose that \( S \) is not the set of all natural numbers, then the complement \( S' \) is non-empty, hence must contain a smallest element (using the natural order), which we denote by \( a \). From condition (1), we know that \( a\neq 1 \), so \( a \geq 2 \). From condition (2), we know that if the positive integer \( a-1 \) is in the set, then so is \( a \). Hence, \( a-1 \) is not in the set. But this contradicts the assumption that \( a \) is the smallest element that is not in the set. \(_\square\)
Just how powerful is Induction? I will use it to show that your name is Calvin.
Claim: In a group of \( n \) people, everyone has the same name.
Proof: Let's show that condition (1) holds. In a group of \( n=1 \) people, all of them have the same name.
Let's show that condition (2) holds. Since the positive integer \( k \) is in the set, this means that in a group of any \( k \) people, all of them have the same name. So let's consider a group of \( k+1 \) people. Since the first \( k \) people have the same name, and the last \( k \) people also have the same name, it means that all \( k+1 \) of them must have the same name.
Thus, by Mathematical Induction, the set \( S \) includes all positive integers, so in a group of \( n \) people, everyone has the same name.
In particular, since my name is Calvin, and you are in the set of all \( N \) people on Earth, it follows that your name is also Calvin. \( _\square\)
The above is adapted from Polya's proof that "No horse is of a different color".
Feel free to share your thoughts on the Brilliant.org Discussions.