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 …

Wir müssen also die obigen beiden Lösungsschritte beweisen, um die Aufgabe zu lösen. Hier ist der Beweis mit den beiden notwendigen Lösungsschritten:

1. Lösungsschritt: Für lautet die zu beweisende Aussage . Durch Nachrechnen der rechten Seite, zeigt man, dass diese Aussage wahr ist.

2. Lösungsschritt: Gehen wir davon aus, dass die Aussage für bereits bewiesen ist. Gehen wir also davon aus, dass gilt:

Wir müssen nun die Summenformel für beweisen. Wir müssen also beweisen, dass gilt:

Fangen wir auf der linken Seite dieser zu beweisenden Gleichung an:

Unter Annahme der gegebenen Gleichung können wir also die linke Seite der Zielgleichung in die rechte Seite der Zielgleichung umformen. Damit haben wir die Zielgleichung bewiesen.

Wir haben so eine kurze und elegante Lösung der Aufgabe gefunden (Gauß' Lehrer wäre sicherlich stolz auf uns :).).

Das Prinzip der vollständigen Induktion [Bearbeiten]

Bild zur Veranschaulichung des Dominoeffekts bei der vollständigen Induktion

Doch was ist nun das Prinzip der vollständigen Induktion? Dazu schauen wir uns die obige Beispielaufgabe an und versuchen, das dabei verwendete Beweisprinzip zu verallgemeinern!

Zunächst stellen wir fest, dass es sich um eine Aussageform handelt, deren einzige freie Variable eine natürliche Zahl ist. Die Aufgabe besteht nun darin, zu beweisen, dass die Aussageform für alle natürlichen Zahlen erfüllt, also allgemeingültig in ist.

Nun haben wir im ersten Schritt bewiesen, dass die Aussageform für die kleinste natürliche Zahl erfüllt ist (in unserem obigen Beispiel war diese kleinste natürliche Zahl die Eins; in bestimmten Fällen kann es aber auch eine andere natürliche Zahl sein, je nachdem wie die zu beweisende Aufgabe lautet). Dieser Schritt wird Induktionsanfang genannt und entspricht in unserer obigen Analogie dem Umstoßen des ersten Dominosteins.

Im zweiten Schritt haben wir bewiesen, dass, wenn die Aussageform für eine beliebige natürliche Zahl erfüllt ist, sie auch für erfüllt sein muss. Dieser Schritt wird Induktionsschritt genannt und entspricht in unserer obigen Analogie der Tatsache, dass die Dominoreihe so aufgebaut sein muss, dass beim Fall eines Dominosteins auch der nächste Dominostein umfallen muss. Die dabei getroffene Annahme, dass die Aussageform für ein beliebiges erfüllt ist, nennt man Induktionsvoraussetzung oder auch Induktionsannahme (das war die gegebene Gleichung im zweiten Lösungsschritt). Die unter Annahme der Induktionsvoraussetzung zu beweisende Aussage wird Induktionsbehauptung genannt (das war unsere obige Zielgleichung). Der Induktionsschritt hat also die 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.