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.

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

Sort by:

TopNewestI feel like a lot of people have trouble with the concept of mathematical induction. I tried to explain it to this kid in my class and he had no idea what I was trying to say. I think of it somewhat like this: Imagine a line of dominoes. If you know that the first domino fell, and if you can prove that if one domino falls, then the next must fall, you've effectively proven that the entire line must have fallen. So it goes for the natural numbers, as you just showed above. Great article.

Log in to reply

If k=1, the first k and last k do not intersect so we cannot proceed.

Log in to reply

If \(k=1\), then the first, and the last person, are exactly the same person.

Log in to reply

#TooManyCalvinsLog in to reply

The fact that not everyone's name is Calvin is that when K = 2 there are two persons and also that every set of one person has the name Calvin, so we cannot proceed as the two people have different names, The induction step breaks at k =2

Log in to reply

The proof fails when establishing that k = 2 works due to the base case k = 1. With 2 only people, there is no intersection between the two subsets. Since k = 2 cannot be established from k = 1, the proof is invalid.

Log in to reply

@Calvin Lin @Ethan Robinett .......... Why does

induction work?..... the proof gives the proof but can you please explain why it is EXCLUSIVE fornatural numbers......... I THINK according to the dominoes intuition,the next domino falls because they are evenly SPACED ... is it the proper spacing of natural numbers that makes it possible, then induction should be true for all real numbers?.........i know i am missing something here!! :|HELP!!Log in to reply

Of course, the "You Are Inductively Calvin" Proof is not true, as mathematical induction does not apply. We can't prove that the next step with k+1 people will be true, as unlike numbers, the names of people are arbitrary.

Log in to reply