How would you explain mathematical induction to a novice in a simple and intuitive way?

Question

How would you explain induction to a novice in a way that's simple and easy to comprehend? I'm a believer that the mark of someone who understands a topic well is their ability to communicate that topic with ease and simplicity. I think this post is an opportunity for us to exercise our imagination, our intuition, teaching, and communication skills in a rigorous subject matter. Moreover, it could be great place for someone who is struggling to grasp induction to get clarity and insight. I'm interested to see how we can explain this idea without getting too muddled with jargon and notation.

Answer 1

Imagine a ladder in front of you that stretches infinitely into the sky. You would like to know whether it's possible for someone like yourself to start climbing this ladder and continue climbing it forever without stopping. So you examine the ladder and notice that although some rungs are spaced further apart than others, they are still reachable. Of course, this is only true for the rungs you are able to see; there are plenty of rungs way up the ladder too far for you to see. So now you're wondering whether there might actually be a rung that's too far to reach, somewhere way up the ladder, one that would force you too stop climbing at some point.

Hmmm... is there some way to conclude that you could reach every rung without actually being able to inspect every rung?

The answer is yes! I walk up to you and give you $1$ piece of information: "if you are able to grab any arbitrary rung on the ladder, then you will be able to grab the very next one."

You then walk up to the ladder, reach up, and grab the first rung!

That's when it hits you... I told you if you could grab ANY rung, then you could grab the very next one. So now you are certain you can grab the second rung. And then it hits you again... if you're able to grab the second rung, then must be able to grab the third. And if you're able to grab the third rung, then you must be able to grab the fourth... You quickly reason that you'll be able to grab EVERY rung on this ladder, even though you can't inspect them all. And it's all because of two little facts:

$1.$ I said if you could grab any rung on the ladder, any rung at all, then you would be able to grab the very next one.

$2.$ You observed that you could grab the very first rung.

This is precisely how mathematical induction works. The rungs on the ladder are the positive integers $\{1,2,3,...\}.$ Our goal is to conclude something about all of them, but there are infinitely many, making it impractical to inspect each one individually. Instead, we attempt to do two things:

$1.$ Show that if the statement we're proving is true for any one of them, lets call it integer $k$, then it must be true for the very next one, that is, for $k+1$.

$2.$ Show the statement we're proving is true for the very first integer in our set, that is, for the number $1$.

If you can do those two things, then you can prove your statement is true for ALL the positive integers using the same reasoning as in the ladder analogy. This form of reasoning is called induction.

Answer 2

I (and probably everyone else) always compare mathematical induction to domino blocks.

Suppose you have a bunch of domino blocks labeled by the natural numbers. For each block $n$ we have the statement $P(n)$ which says that block $n$ falls.

All mathematical induction says is that all blocks fall over given the following two conditions:

1. The first block falls, i.e. $P(0)$ holds.
2. If a block falls, then the next block is hit and falls as well, i.e. $\forall n\in \mathbb{N}:P(n)\Rightarrow P(n+1)$.