# Informal Introduction to Mathematical Induction

This post serves as an **informal**^{1} 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.

## Footnotes:

^{1}

For the **formal** introduction, my advice is to consult
The Method of Mathematical Induction by **I. S.
Sominskii**. Of all the sources I looked into, this book provided the most
straightforward explanation of the method.