Mathematical induction – Serlo

Aus Wikibooks
Zur Navigation springen Zur Suche springen
UnderCon icon.svg

Diese Seite ist noch im Entstehen und noch nicht offizieller Bestandteil des Buchs. Gib der Autorin / dem Autor Zeit, die Seite anzupassen!

The complete induction is an importnant 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 with complete induction.

An example[Bearbeiten]

Carl Friedrich Gauß

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 [1] that the young Gauss was able to determine the sum of the first natural numbers immediately and without further calculations.

His idea was that there are exactly pairs of numbers between whose sum is : , , and so on until . The result would then be . Generalizing this, we obtain the formula:

For every natural number the sum equals .

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

For :

, correct ✔

For :

, 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 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 ). 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 with the number , the (true) statement reads:

The sum is equal to .

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

reads: The sum is equal to .

reads: The sum is equal to .

Our goal is now to prove that our statement holds true regardless of the value we choose for . Such a statement is said to be „universally valid in “.

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 . We say that the first domino piece stands for the statement , the second domino piece for the statement , 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 is true, and in the case of domino number , the proposition 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, also his successor falls over.

If both conditions are met, all the tiles in the domino series fall one after an other ("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 the original problem, in order to prove the universality of our statement?

  1. First step: Show that the statement for is fulfilled.
  2. Second step: Show that, assuming that the statement is true for any , the statement holds true also for the successor .
Illustration of the complete 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 is true. If we now apply this knowledge to the second step (that is, if ), it follows that the the claim for must be true. If we apply the second step again, the truth follows for and if applied again for and so on …

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:

Solution step 1: For , the claim we need to prove is: . 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 . By this assumption, it then holds:

Now we have to prove the sum formula for . This means we have to show:

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

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 Principle of Complete Induction [Bearbeiten]

Bild zur Veranschaulichung des Dominoeffekts bei der vollständigen Induktion

But what exactly is the principle of "complete induction"? 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 . 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 . In this case, is our "smallest" natural number we want to consider. This step is called the initial point of induction. 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 , then it must also be true for . erfüllt sein muss. This step is called the inductive 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 assumptive step. 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:

Im Folgenden werden wir nur noch den Begriff „Induktionsvoraussetzung“ verwenden. Fassen wir zusammen: Die vollständige Induktion lässt sich beim Beweis der Allgemeingültigkeit von Aussageformen anwenden, deren eine freie Variable eine natürliche Zahl ist. Zum Beweis durch vollständige Induktion musst du folgendes leisten:

  1. Induktionsanfang: Beweise, dass eine wahre Aussage ist.
  2. Induktionsschritt: Beweise, dass wenn wahr ist, auch wahr sein muss. Dabei können folgende Teilschritte identifiziert werden:
    • Induktionsvoraussetzung: Die Aussage ist wahr für ein bestimmtes .
    • Induktionsbehauptung: Die Aussage ist wahr.
    • Beweis des Induktionsschritts: Beweise, dass unter Annahme der Induktionsvoraussetzung die Induktionsbehauptung wahr ist.

Der Induktionsschritt hat dementsprechend folgende Form:

Oftmals (insbesondere bei einfacheren Aufgaben) werden Induktionsvoraussetzung und Induktionsbehauptung weggelassen, wenn sie dem Autor zu trivial erscheinen, als dass sie ausführlich erwähnt werden müssten. Auch der Induktionsanfang beziehungsweise der Induktionsschritt werden manchmal nicht ausgeführt. Oft geben Lehrbuchautoren nur den Hinweis, dass eine bestimmte Aufgabe durch vollständige Induktion bewiesen werden kann und überlassen dem Leser die Auseinandersetzung mit dem jeweiligen Beweis. In diesem Kapitel werden aber alle Teilschritte der vollständigen Induktion ausgeführt.

Wenn wir nun die obige Beweismethode in mathematischer Sprache formulieren, erhalten wir die Definition der vollständigen Induktion.

Definition (Vollständige Induktion)

Sei eine Aussageform in der freien Variablen . Sei eine wahre Aussage (Induktionsanfang) und die Implikation für alle erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in .

Einige Fragen zur vollständigen Induktion[Bearbeiten]

Question: Muss man zum Beweis mit vollständiger Induktion immer den Induktionsanfang und den Induktionsschritt durchführen oder kann man sich auch unter Umständen einen der beiden Schritte sparen?

Zur vollständigen Induktion gehören immer Induktionsanfang und Induktionsschritt. Wenn du einen der beiden Schritte weglassen würdest, wäre deine Lösung unvollständig und besäße damit keine Beweiskraft.

Die Antwort auf diese Frage kannst du dir auch über die Analogie zur Dominoreihe überlegen: Wenn du den Induktionsanfang weglässt, entspricht dies der Tatsache, dass du den ersten Dominostein nicht umstößt, was zur Folge hat, dass kein Dominostein umfällt.

Wenn du den Induktionsschritt weglässt, könntest du nach der Analogie nicht gewährleisten, dass ein Dominostein beim Umfallen auch seinen Nachfolger mitreißt. Damit könntest du nicht garantieren, dass alle Dominosteine umfallen (zwei Dominosteine könnten zum Beispiel zu weit voneinander entfernt stehen). Deine Lösung hätte dann keine Beweiskraft.

Question: Da die Dominoreihe unendlich ist, benötigt sie auch unendlich lange zum Umfallen. Dies würde bedeuten, dass ein Beweis mit vollständiger Induktion nie vollständig wäre (da zu keiner Zeit alle Steine umgefallen sind). Heißt das nicht, dass man die vollständige Induktion nie zu Ende führen kann?

Diese Frage zeigt eine der Grenzen der Dominoanalogie. Die Zeit, die ein Dominostein benötigt, um umzufallen und dabei den nächsten Stein anzustoßen, ist für die Mathematik nicht relevant. Es ist nur wichtig, dass jeder Stein in endlich vielen Schritten fällt.