You Are Inductively Calvin

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.

Markdown

Appears as

*italics* or _italics_

italics

**bold** or __bold__

bold


- bulleted
- list

bulleted
list


1. numbered
2. list

numbered
list

Note: you must add a full line of space before and after lists for them to show up correctly

paragraph 1

paragraph 2

paragraph 1

paragraph 2

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

example link

> This is a quote

This is a quote

    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"

# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"

Math

Appears as

Remember to wrap math in $ ... $ or \[ ... \] to ensure proper formatting.

2 \times 3

2 \times 3

2^{34}

2^{34}

a_{i-1}

a_{i-1}

\frac{2}{3}

\frac{2}{3}

\sqrt{2}

\sqrt{2}

\sum_{i=1}^3

\sum_{i=1}^3

\sin \theta

\sin \theta

\boxed{123}

\boxed{123}

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

I 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.

A Former Brilliant Member - 6 years, 10 months ago

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

Joel Tan - 6 years, 8 months ago

If $k=1$ , then the first, and the last person, are exactly the same person.

Calvin Lin Staff - 6 years, 8 months ago

#TooManyCalvins

Alita Toh - 6 years, 5 months ago

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

Ishan Tarunesh - 6 years, 8 months ago

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.

Robert Tran - 6 years ago

@Calvin Lin @Ethan Robinett .......... Why does induction work? ..... the proof gives the proof but can you please explain why it is EXCLUSIVE for natural 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!!

Abhinav Raichur - 6 years, 7 months ago

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.

Bhagirath Mehta - 7 years, 1 month ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

You Are Inductively Calvin

Claim: In a group of n n n people, everyone has the same name.

Comments

Claim: In a group of $n$ people, everyone has the same name.