Mathematical induction – "Math for Non-Geeks"

The principle of induction is an important method of proof that you will encounter again and again over the course of your studies. The way it works is comparable with the domino effect. But what does it actually look like? Let's look at an example in which we solve a problem by induction.

An example

Carl Friedrich Gauß

Our example is called "the Gauss summation formula", or "small Gauss". It is called that because the nine-year-old Carl Friedrich Gauss discovered it in a math lesson in school. Gauss is the genius mathematician whose portrait would later be printed on the German 10-Mark notes. It is said that the young Gauss was able to determine the sum of the first $100$ natural numbers immediately and without further calculations.

His idea was that there are exactly $50=100/2$ pairs of numbers between $1\dots 100$ whose sum is $101$: $1+100$, $2+99$, $3+98$ and so on until $50+51$. The result would then be $(1+100)\cdot 50$. Generalizing this, we obtain the formula:

For every natural number $n$ the sum $1+2+3+\dots +n$ equals $(1+n)\cdot \frac{n}{2}$.

Now we can start to prove this claim for every single natural number $n$:

For $n=1$:

$1=\frac{1(1+1)}{2}$, correct ✔

For $n=2$:

$1+2=3=\frac{2(2+1)}{2}$, also correct ✔

and so on…

But it is not possible to prove the above formula in this way as there are infinitely many natural numbers (think of the poor classmates of Gauß trying to sum up one by one every single number!). Obviously, we need a different technique for the proof. I told you at the beginning of this chapter that this formula can be proved by mathematical induction, and that this technique is similar to the domino effect. But how can the domino effect be used here? Let us take a closer look at the example:

If you read through the task, you will realize that there is a free variable in the task definition (the natural number $n$). If you use a specific value for this free variable, you get a concrete result. By recalculating, you can determine if this statement is true or false. For example, if you substitute $n$ with the number $42$, the (true) statement reads:

The sum $1+2+3+\dots +42$ is equal to $\frac{42\cdot (42+1)}{2}$.

Such an expression, which contains one free variable $n$ and yields a result by assigning a value to this variable, is a statement form denoted by $A(n)$. This can be extended to statement forms depending on more variables $n,m,\mathrm{...}$ which are then denoted by $A(n,m,\mathrm{...})$. $A(n)$ means something like: a statement form with the name $A$ and the free variable $n$, that is, the statement form $A$ depends on the value of the variable $n$. The above statement would therefore be $A(42)$. Here more examples:

$A(1)$ reads: The sum $1$ is equal to $\frac{1\cdot (1+1)}{2}$.

$A(4)$ reads: The sum $1+2+3+4$ is equal to $\frac{4\cdot (4+1)}{2}$.

Our goal is now to prove that our statement holds true regardless of the value we choose for $n$. Such a statement is said to be "universally valid in $\mathbb{N}$".

The induction principle is comparable to a domino series.

How can we bring the domino effect into play now? For this purpose, we will find an analogy between our statement and a domino series: imagine an infinitely long series of domino pieces starting somewhere in the room. This domino series is numbered (the first domino is one, the second is two, and so on). Now we introduce a relationship between the domino series and the statement to be proven $A(n)$. We say that the first domino piece stands for the statement $A(1)$, the second domino piece for the statement $A(2)$, and so on. Let us now assume that when a domino piece falls, the truth of the statement assigned to it is proven. So, if domino number seven falls, the statement $A(7)$ is true, and in the case of domino number $23$, the proposition $A(23)$ is true.

The domino effect.

We have now reduced our task to a problem known since childhood: wanting to bring down a domino series.

Question: What do we need to do to make all the dominoes fall over? How should the domino series be built?

If you think about it, you will come up with two conditions that have to be fulfilled to make all dominoes fall over.

1. You have to hit the first domino piece.
2. The domino series must be constructed in such a way that, in case a domino piece falls over, its successor also falls over.

If both conditions are met, all the tiles in the domino series fall one after another ("domino effect"). So you have to make sure that both conditions are fulfilled.

Question: How can the two answers just given be translated back to the original problem, in order to prove the universality of our statement?

1. First step: Show that the statement for $n=1$ is fulfilled.
2. Second step: Show that, assuming that the statement is true for any $n=k$, the statement holds true also for the successor $n=k+1$.

Illustration of the induction principle.

Let us see how the proof of these two steps provides the proof of our original problem. First of all, one shows that the first step is fulfilled, that is, that the assertion for $n=1$ is true. If we now apply this knowledge to the second step (that is, if $n=k=1$), it follows that the claim for $n=k+1=1+1=2$ must be true. If we apply the second step again, the truth follows for $n=2+1=3$ and if applied again for $n=3+1=4$ and so on …

So to solve the problem, all we need to do is prove the two steps of the solution given above. Here are the proofs of the two necessary steps:

Solution step 1: For $n=1$, the claim we need to prove is: $1=\frac{1\cdot (1+1)}{2}$. By simply calculating the right side, this is how we can show the claim is true.

Solution step 2: Let us assume that the claim is already proven for $n=k$. By this assumption, it then holds:

$\underset{\text{This equation is given.}}{\underbrace{1+2+3+\dots +k=\frac{k\cdot (k+1)}{2}}}$

Now we have to prove the sum formula for $k+1$. This means we have to show:

$\underset{\text{Goal: this equation must be shown/proven!}}{\underbrace{1+2+3+\dots +k+(k+1)=\frac{(k+1)\cdot ((k+1)+1)}{2}}}$

Let's start on the left side of the equation we need to prove:

$\begin{array}{cc}\stackrel{\text{left side of the equation we want}}{\overbrace{1+2+3+\dots +k+(k+1)}}& =(1+2+3+\dots +k)+(k+1)\\ & \downarrow \text{substitute in the given equation}\\ & =\frac{k\cdot (k+1)}{2}+(k+1)\\ & \downarrow \text{combine the sum into a fraction}\\ & =\frac{k\cdot (k+1)+2\cdot (k+1)}{2}\\ & \downarrow a\cdot b=b\cdot a\\ & =\frac{(k+1)\cdot k+(k+1)\cdot 2}{2}\\ & \downarrow \text{ factor out}(k+1)\\ & =\frac{(k+1)\cdot (k+2)}{2}\\ & \downarrow k+2=(k+1)+1\\ & =\underset{\text{right-hand side of the equation we want}}{\underbrace{\frac{(k+1)\cdot ((k+1)+1)}{2}}}\end{array}$

By assuming that the given equation is true, we can then transform the left side of the equation we want into the right side of the equation we want, such that we've proven the entire equation.

This method has given us a short and elegant solution to the problem.

The induction principle

An illustration of the domino effect within induction

Now, what exactly is the "induction principle" in mathematics? To answer this question, we will use the example problem above as a motivation to generalize this proof method so that it can be applied to other similar problems.

First, we take note that this principle deals with claims whose only free variable is a natural number. The problem to solve in these cases is to show that this claim is true for all natural numbers. In the first step, we showed that this claim is true at the starting natural number - in the case of the example above, the starting value was $n=1$. In the case of other problems, the claim may not be true for certain natural numbers; it may only be true for all natural numbers greater than or equal to some natural number $n$. In this case, $n$ is our "smallest" natural number we want to consider. This step is called the induction base. In our analogy with dominoes, this is the same as the first domino that's knocked over that starts the chain reaction.

In the second step, we showed that if the claim is true for any random natural number $k$, then it must also be true for $k+1$. This step is called the induction step. In our domino analogy, this step can be identified with the idea that a line of dominoes is built such that if one domino is knocked over, the next domino must fall. Assuming that the claim is true for some arbitrarily chosen natural number is called the induction assumption. This was the equation we used in solution step 2 above. The claim that we want to prove using the induction assumption is called the induction claim. This was the goal equation in the example above. The inductive step has the form:

$\stackrel{\text{induction step}}{\overbrace{\underset{\begin{array}{c}\text{induction assumption}\end{array}}{\underbrace{A(k)}}\Rightarrow \underset{\text{induction claim}}{\underbrace{A(k+1)}}}}$

Let us summarize: Induction can be applied to prove the universality of propositional forms $A(n)$ whose only free variable $n$ is a natural number. A proof by induction now works as follows:

1. Induction base: Prove that $A(1)$ is true.
2. Induction step: Prove that if $A(k)$ is true, then $A(k+1)$ is also true. The two claims appearing here are the:
   • Induction assumption: We assume that $A(k)$ is true for a single given $k\in \mathbb{N}$.
   • Induction claim: We claim that $A(k+1)$ is true, which we have to show.
   • 'Proof of the induction step: Proof that under the induction assumption the induction claim is true.

Accordingly, the induction step has the following form:

$\begin{array}{c}\text{induction assumption}\\ |\\ \text{proof}\\ \downarrow \\ \text{induction claim}\end{array}$

Often (especially for simpler problems) induction base and induction assumption are omitted by a book author, if they seem too trivial to be mentioned in detail. Also, the induction base or induction step is sometimes not performed. Textbook authors often only give the hint that a problem can be solved by induction and leave the reader to deal with the respective proof. In this chapter, however, all the sub-steps of induction are explained.

If we now formulate the above method of proof in mathematical language, we get a kind of pattern for how to solve problems by induction.

Definition (Sample: Proof by induction)

Let $A(n)$ be a statement form depending on the variable $n\in \mathbb{N}$. If $A(1)$ is a true statement (induction base) and the implication $A(k)\Rightarrow A(k+1)$ is fulfilled for all $k\in \mathbb{N}$ (induction step), then the statement is valid for all $n\in \mathbb{N}$.

Induction: a short Q&A

Question: Do I always need the induction base and induction step for an induction proof or can I sometimes save one of the two steps?

Induction proofs always include an induction base and an induction step. If you omit either of these steps, your solution will be incomplete and lead to wrong or even obviously stupid conclusions!

You can also use the analogy of the domino series: If you omit the induction base, this corresponds to the fact that you don't knock over the first domino. Assuming that the induction still works without an induction base is like assuming that all dominos fall even though no domino is touched! (which is obviously stupid)

If you leave out the induction step, you could not guarantee that a domino would take its successor with it when it fell. So the domino cascade might stop falling. The conclusion of the induction proof "all dominos will fall" is then simply wrong again.

Question: Since the row of dominos is infinite, it also takes infinite time to fall over. This would mean that a proof by induction would never be complete (since at no finite time did all the stones fall over). Doesn't this mean that the induction proof can never be completed?

This question shows one of the limits of the domino analogy. The time it takes for a domino to fall over and thereby trigger the next one is not relevant for mathematics. For each fixed $n\in \mathbb{N}$, the base case and finitely many applications of the induction step establish $A(n)$. The induction proof itself consists of the base case and the general induction step, both of which can be completed in finite time.

The thought that it might be wrong because of an "infinite" time is a common misconception, one has to get rid of!