Informal Introduction to Mathematical Induction

This post serves as an informal¹ introduction to mathematical induction, concentrating on the aspects that might not be trivial to grasp.

Mathematical induction is the method of proof in mathematics.

The first thing we should understand is that the term Mathematical Induction is "just" a name of a specific process (method) of thinking. Humanity had "agreed on" this process being commonly useful and "decided on" abstracting it out: giving it a name, such that everyone knowing what this name means could refer to this particular process of thought more concisely. Without the name, mathematicians would have to provide long and detailed descriptions of this method over and over again, for each proof that uses it; struggling to concentrate on the details of a particular case.

When the proof by induction is being explained, it is — rightly — usually metaphorically compared to the sequentially falling dominoes or climbing a ladder. Unfortunately, these metaphors didn't click with me, being specifically confusing when contemplating proofs similar to the one given in the chapter The Tower Of Hanoi of Concrete Mathematics, utilizing the value of n - 1.

Therefore, this post suggests exploring one more imagery, which I called a Parachute metaphor. It correlates not precisely, but might help to better visualize the process of mathematical induction.

Imagine you've been shown the following photographs in order:

1.

A man is hanging in the air.
Number 801 is written on his belly.

2.

That man is under the parachute now.
Number 800 is written on the photograph.

3.

The man is on the ground, the parachute lays near him.
"Never again!" is boldly crossing the scene.

Looking at these photos, we may deduce that the man had jumped with a parachute from a plane. The photos may convince us he was falling down (part of the way with the parachute) until the successful grounding.

Now, the process of mathematical induction consists of two parts: base case (a.k.a. basis) and induction step.

Base case is like the third photo: it confirms that the falling down event will have finished with the successful grounding. The base case is kind of a safety check; with it, we make sure that the formula/theorem we're proving has a boundary (an "exit" point with the Parachute metaphor; an "entry" point considering traditional metaphors). It's analogous to a guard clause, non-coincidentally called base case too, of a recursive function written in any programming language.

Induction step is like the first two photos: they claim the man was present at the heights of 801 and 800. Being aware of the gravity and the third photo, we conclude that the man was also present at all the other heights: down from 801 to 0 (the ground), that he was falling down until grounding.

Now let's review an important nuance about an inductive step. Observe that the numbers 801 and 800 are consecutive (going one after another) natural (used for counting items of something) numbers.

Commonly, proving an inductive step, we first assume that the formula/theorem holds for an arbitrary natural number. Then we check if the formula/theorem holds for the next natural number. If it does, the formula/theorem holds for two consecutive natural numbers, which means, by the property of natural numbers ("natural laws" in the Parachute metaphor; see Peano axioms and inductive axiom for more details), that it holds for other natural numbers too.

And that's all I wanted to express about mathematical induction. I hope my findings help someone trying to contemplate this almost magical method of thinking. I hope it helps you.

For an example application of mathematical induction, take a peek at The Tower of Hanoi: The Closed Form Proof.