What is the evidence for mathematical induction

Complete induction - Serlo "Math for non-freaks"

This is an important method of proof that you will come across frequently in your studies. You can compare their mode of action with the domino effect. But what exactly does a “proof with the domino effect” look like? Let us first consider an example problem that can be solved with the help of complete induction.

A sample task [edit]

Our example task is the “Gaussian sum formula”, also called “little Gauss”. It is so called because the nine-year-old Carl Friedrich Gauß discovered this sum formula in a math lesson (Gauß is the brilliant mathematician whose face was later to adorn the ten-mark note in Germany). According to anecdote[1] could the little Gauss the sum of the first Enter natural numbers immediately and without long calculations.

His idea was that it was between exactly Pairs of numbers are there, their sum is: , , and so on up . If you generalize your "trick", you get the following formula:

For any natural number is the sum equal .

Well. We could now start making this claim for single natural numbers to prove:

For :

, that's right ✔

For :

, also true ✔

and so on…

But this is not a way of proving, because there are infinitely many natural numbers and it is therefore fundamentally impossible to calculate all the sums (think of Gauss's poor classmates, how they tried to add up the individual numbers one after the other). So we need a different solution method. We told you in the introduction to this chapter that this problem can be solved by induction and that this method of proof is similar to a domino effect. But how can a domino effect be used in this task? To do this, let's analyze the task:

If you read through the problem, you will see that there is a free variable in the problem (the natural number ). If you insert a certain value for this free variable, you get a concrete statement. By doing the math you can determine whether this statement is true or false. If you z. B. for the number begins, the (true) statement arises:

The sum is equal to .

Such an expression, which contains one (or more) free variables and which turns into a statement by assigning values ​​to these variables, is called and with designated. means something like: A form of expression with a name and the free variables , so in dependence of . The above statement would therefore be . Here are a few more examples:

reads: The sum is equal to .

reads: The sum is equal to .

It is our task to prove that the statement form when substituting all natural numbers always gives a true statement. Such a form of statement, which always delivers a true statement for all natural numbers, is called “generally valid in “.

Our task is comparable to a row of dominoes.

But how can you bring the domino effect into play now? We will find an analogy between the statement form and a row of dominoes: Imagine an infinitely long row of dominoes that starts somewhere in the room. This row of dominoes is numbered (the first domino is one, the second is two, and so on). Now we have a relationship between the domino series and the form of assertion to be proven a. We say the first domino for the statement stands, the second domino for the statement and so on. Let us now assume that when a domino falls, the truth of the statement assigned to it has been proven. So if domino number falls over is the statement true and in the case of domino number falling is the statement true.

We have now reduced the problem of the task to the problem, known to us from childhood, of trying to make a row of dominoes fall over.

Question: What do you have to do with it all Do dominoes fall over? How does the domino row have to be structured for this?

If you think about it, you will come up with two conditions that you must meet in order for all of the dominoes to fall over.

  1. You have to knock over the first domino.
  2. The row of dominoes must be set up in such a way that if one of the dominoes falls, its successor also falls over.

If both conditions are met, all the stones in the domino row fall over one after the other ("domino effect"). So you have to make sure that both are met.

Question: What are the two solution steps from the answer to the question just posed if we translate this back into the original problem of proving the general validity of a statement form?

  1. First solution step: Show that the proposition form for is satisfied.
  2. Second solution step: Show that assuming that the proposition form is for any is fulfilled, the form of the statement also applies to the successor must be fulfilled.
Illustration of complete induction

You can see that the problem is solved by proving these two solution steps: First of all, in the first solution step it is shown that the assertion for true is. If we now apply this knowledge to the second solution step (if so is), it follows that the assertion also applies to must be true. If we apply the second step again, the truth will follow for and when used again for and so on ...

So we have to prove the above two solution steps in order to solve the problem. Here is the proof with the two necessary solution steps:

1st solution step: For is the statement to be proven . By calculating the right hand side, one shows that this statement is true.

2nd solution step: Let us assume that the statement for has already been proven. So let's assume that:

We now need the empirical formula for to prove. So we have to prove that:

Using term transformations, we now show that the left side of the equation is equal to the right side of the equation. So we need to find term reformulations of the following form:

The necessary term transformations are:

So, assuming the given equation, we can transform the left side of the target equation into the right side of the target equation. With this we have proven the target equation.

We found such a short and elegant solution to the task (Gauss' teacher would certainly be proud of us ).

The principle of complete induction

Image illustrating the domino effect during full induction

But what is the principle of complete induction? To do this, let's look at the example exercise above and try to generalize the principle of proof used.

First of all, we notice that it is a statement form whose only free variable is a natural number. The task now is to prove that the statement form is fulfilled for all natural numbers, i.e. that it is generally valid in is.

Now, in the first step, we have proven that the proposition form for the smallest natural number is fulfilled (in our example above, this smallest natural number was one; however, in certain cases it can also be a different natural number, depending on how it is proving task is). This step is called and, in our analogy above, corresponds to knocking over the first domino.

In the second step we proved that if the proposition is for any natural number is fulfilled, they too for