Vollständige Induktion

Aus ÖMO Wiki

Inhaltsverzeichnis

1 Vollständige Induktion

Vollständige Induktion

Einleitung

Die vollständige Induktion funktioniert anschaulich erklärt wie das Stiegensteigen. Wenn man weiß, wie man von einer Stufe auf die nächste kommt, kann man die gesamte Stiege erklimmen.

Ähnlich funktioniert es in der Mathematik. Gilt eine Beziehung für n+1 (wobei n eine natürliche Zahl ist), unter der Voraussetzung, dass die Beziehung bereits für n gilt, so muss die Beziehung für alle $k \in \mathbb{N}$ gelten. Dazu ist es aber wichtig, dass es eben ein n gibt, für das die Beziehung gilt. Um diese Notwendigkeit am Stiegensteigen-Beispiel zu verdeutlichen, würde das in etwa bedeuten, dass man die erste Stufe auch findet.

Anwendungsbereiche

Die vollständige Induktion eignet sich sehr gut, um Beziehungen, die für fast alle natürlichen Zahlen gelten, zu beweisen. Ebenfalls sehr häufig kommt die vollständige Induktion bei Ungleichungen zum Einsatz.

Es gibt auch einige Modifikationen der vollständigen Induktion, so wie sie bisher beschrieben worden ist. So kann sie beispielsweise auch so ausgeführt werden, dass man zuerst zeigt, dass wenn die Beziehung für n gilt, sie auch für 2n oder für n+2 gilt. Dann muss allerdings auch gezeigt werden, dass wenn sie für n gilt, sie auch für n-1 gilt. Um das ganze wieder durch Stiegensteigen zu erklären: Wenn ich nur zwei Stufen vorwärts und nur eine Stufe rückwärts steigen kann, erreiche ich immer noch jede beliebige Stufe.

Durchführung anhand eines einfachen Beispiels

Am besten, wir veranschaulichen uns das Ganze nun an einem (prominenten) Beispiel:

$\sum_{i=1}^n i = \frac{n(n+1)}{2}$

Diese Identität ist für alle natürlichen Zahlen zu zeigen.

Das Wichtigste (und bei Wettbewerben meist das trivialste) ist erst einmal, den "Induktionsanfang" zu sichern, also solche n finden, für das die Beziehung erfüllt ist. Üblicherweise beginnt man bei n=1, das wollen wir auch machen:

$1 = \frac{1 \cdot 2}{2}$

Dies ist also offensichtlich erfüllt. Trotzdem ist dieser Schritt unerlässlich und absolut notwendig.

Als nächstes wollen wir nun den Schritt von n auf n+1 wagen ("Induktionsschluss"). Wir lehren diese Identität sozusagen das Treppensteigen.

$\sum_{i=1}^{n+1} i = \sum_{i=1}^{n} i + n+1$

Nun dürfen, ja eigentlich müssen wir verwenden, dass die Beziehung bereits für n gilt, es gilt also $\sum_{i=1}^n i = \frac{n(n+1)}{2}$ . Wir erhalten also

$\sum_{i=1}^{n} i + n+1 = \frac{n(n+1)}{2} + n+1 = \frac{n^2 + n + 2n + 2}{2} = \frac{(n+1)(n+2)}{2}$

Dies entspricht also genau dem zu Zeigenden, wobei man n in n+1 übergehen lässt. Somit haben wir gezeigt, dass die Beziehung unter der Voraussetzung, dass sie für n stimmt, auch für n+1 stimmt.

Da die Beziehung nach Induktionsanfang bereits für n=1 gilt, gilt sie also auch für k=n+1=2. Daher gilt sie auch für m=k+1=3 und so weiter.

Durchführung anhand eines Gebietswettbewerbbeispiels

Konkret soll also das erste Beispiel des Gebietswettbewerbs 2000 gelöst werden: Für welche natürlichen Zahlen n gilt $2 n > 10 n 2 - 60 n + 80$ ?

Ein paar kleine Vorüberlegungen sind natürlich unerlässlich. Wir können aufgrund der Gestalt der Ungleichung erwarten, dass $2 n$ irgendwann viel schneller wachsen wird als das Polynom. Suchen wir also zuerst einmal ein n, für das die Ungleichung gilt: $n = 0:1 > 80$ falsche Aussage
$n = 1:2 > 30$ falsche Aussage
$n = 2:4 > 0$ wahre Aussage

Versuchen wir nun den Induktionsschluss von n auf n+1:

2 n + 1 > 10(n + 1) 2 - 60(n + 1) + 80

2 * 2 n > 10 n 2 + 20 n + 10 - 60 n - 60 + 80

Wir dürfen wiederum verwenden, dass bereits <m>2^n > 10n^2-60n+80</m> gilt. Wir können also auf der linken Seite der Ungleichung $2 n$ durch $10 n 2 - 60 n + 80$ ersetzen. Ist dann die linke Seite noch immer echt größer als die rechte, so haben wir gezeigt, dass die Ungleichung für alle n größer einem $n 0$ ist:

$2*2^n > 2*(10n^2-60n+80) >\!\!\!\!{}^?\ 10n^2 + 20n + 10 - 60n - 60 + 80$

Zusammenfassen der Glieder ergibt

$10n^2-60n+80 >\!\!\!\!{}^?\ 20n - 50$

$n^2 - 8n + 13 >\!\!\!\!{}^?\ 0$

Ergänzen auf ein vollständiges Quadrat ergibt

$(n-4)^2 >\!\!\!\!{}^?\ 3$

Ist also n > 6, so gilt die Ungleichung auf jeden Fall für alle n größer als ein $n 0$ , das selbst größer oder gleich 6 ist. Nun haben wir aber erst für n=2 die Gültigkeit der Ungleichung gefunden. Wir müssen daher zusätzlich noch größere n untersuchen, da die vollständige Induktion erst ab n=6 klappen würde:

$n = 3:8 > - 10$ wahre Aussage
$n = 4:16 > 0$ wahre Aussage
$n = 5:32 > 30$ wahre Aussage
$n = 6:64 > 80$ falsche Aussage
$n = 7:128 > 150$ falsche Aussage
$n = 8:256 > 240$ wahre Aussage

Für alle n>8 greift nun die vollständige Induktion. Daher haben wir als Lösung des Beispiels: die Ungleichung gilt für alle natürlichen Zahlen n außer für n=0, n=1, n=6 und n=7.

Dieses Beispiel zeigt sehr schön, dass es für die Vollständige Induktion sehr wichtig ist, dass der Induktionsanfang auch gilt.

Abschließende Worte zur Vollständigen Induktion

Die Vollständige Induktion ist ein sehr mächtiges Werkzeug, gerade bei Gebietswettbewerben kommen häufig Beispiele vor, die mit vollständiger Induktion weitgehend gelöst werden können.

Schließlich soll aber auch darauf hingewiesen werden, dass mit Hilfe der Vollständigen Induktion nur die Gültigkeit für jeweils endliche Werte von n gezeigt werden kann, nicht die Gültigkeit für unendliche Werte von n.

Wikipedia: Induktion (Mathematik)

Vollständige Induktion

Aus ÖMO Wiki

Inhaltsverzeichnis