This post serves as an informal1 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:
- A man is hanging in the air.
801is written on his belly.
- That man is under the parachute now.
800is written on the photograph.
- 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
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
0 (the ground), that he was falling down until grounding.
Now let's review an important nuance about an inductive step. Observe that the
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.
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.