Math for Non-Geeks/Mathematical induction

{{#invoke:Math for Non-Geeks/Seite|oben}}

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 how does it actually look like? Let's look at an example, where we solve a problem by induction.

An example

Our example is called "Gauss summation formula", or "small Gauss". It is called that way 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:

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

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 have told you in 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 look closer 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:

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

Template:-

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}$".

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.

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

So to prove solve the problem, all we need to do is prove the two steps of the solution given above. Here is the proof to the necessary solution step: Template:-

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

The induction principleTemplate:Anchor

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 claims is true for the smallest natural number - in the case of the example above, the smallest number for which the claim was true 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 assumptive step is called the induction claim. This was the goal equation is the example above. The inductive step has the form:

Let us summarize: The induction can be applied to prove the universality of propositional forms $A(n)$ whose one 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(n=k)$ is true, then also $A(n=k+1)$ is 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 assumption of the induction assumption the induction claim is true.

Accordingly, the induction step has the following form:

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 how to solve problems by induction.

Induction: a short Q&A

{{#invoke:Math for Non-Geeks/Seite|unten}}