Vollständige Induktion
Lesen anpassen
Nach dieser Lektion kannst du
das Prinzip der vollständigen Induktion formulieren und mit dem Wohlordnungsprinzip begründen,
Summenformeln, Ungleichungen und Teilbarkeitsaussagen mit Induktionsanfang und Induktionsschritt beweisen,
rekursiv definierte Folgen in eine geschlossene Formel übersetzen und diese beweisen,
die starke Induktion einsetzen, wenn der Schritt mehr als den direkten Vorgänger braucht,
fehlerhafte Induktionsbeweise erkennen und den Fehler benennen.
Vorausgesetzt: Betrag, Dreiecksungleichung und Ungleichungen, Grundlegende Beweistechniken
Wer die ersten ungeraden Zahlen der Reihe nach addiert, erhält immer eine Quadratzahl: , , , . Gilt das für alle Anzahlen von Summanden, auch für eine Million?
Du kannst noch so viele Fälle nachrechnen, für alle unendlich vielen natürlichen Zahlen schaffst du es nicht. Und Beispiele können täuschen. Der Term liefert für lauter Primzahlen: Wer nach vierzig Treffern aufhört, wäre sich sicher. Aber für ist , keine Primzahl.
Man braucht also ein Beweisverfahren für Aussagen der Form "für alle natürlichen Zahlen gilt ...". Die Idee ist die einer Reihe von Dominosteinen: Wenn der erste fällt und jeder fallende Stein seinen Nachfolger umwirft, dann fallen alle. Das ist die vollständige Induktion. In der vorigen Lektion haben wir die Bernoulli-Ungleichung genau aus diesem Grund unbewiesen gelassen; hier holen wir den Beweis nach.
Du hast nachgerechnet, dass für eine Primzahl ist. Was folgt daraus?
Schreibweisen: natürliche Zahlen, Summen, Potenzen
Wir schreiben und . Eine Aussageform ist ein Prädikat wie in der Prädikatenlogik: Für jede eingesetzte Zahl entsteht eine Aussage, die wahr oder falsch ist.
Das Summenzeichen kürzt lange Summen ab. Für Zahlen ist
Der Buchstabe heißt Laufindex; er läuft von der unteren Grenze bis zur oberen Grenze , sein Name ist beliebig. Genau genommen ist die Summe rekursiv definiert, das heißt Schritt für Schritt aus dem vorigen Wert: und . Ebenso die Potenzen: und .
Beispiel: .
Berechne .
Prinzip der vollständigen Induktion
Es sei und eine Aussageform für ganze Zahlen . Es gelte:
- Induktionsanfang: ist wahr.
- Induktionsschritt: Für jedes gilt: Wenn wahr ist, dann ist auch wahr.
Dann ist für alle wahr. Die Annahme " ist wahr" im Schritt heißt Induktionsvoraussetzung, die zu zeigende Aussage Induktionsbehauptung.
Wir benutzen das Wohlordnungsprinzip: Jede nicht leere Teilmenge von hat ein kleinstes Element. Anschaulich: Man prüft der Reihe nach und trifft irgendwann auf das erste Element der Menge.
Beweisidee: Gäbe es Gegenbeispiele, dann gäbe es ein kleinstes. Dessen Vorgänger wäre kein Gegenbeispiel, und der Induktionsschritt wirft den Vorgänger auf das kleinste Gegenbeispiel um.
Angenommen, die Menge ist nicht leer. Nach dem Wohlordnungsprinzip hat sie ein kleinstes Element . Wegen des Induktionsanfangs ist , also und damit . Weil und das kleinste Element von ist, liegt nicht in . Also ist wahr. Der Induktionsschritt mit liefert, dass wahr ist. Das widerspricht . Also ist leer.
Die gaußsche Summenformel
Die gaußsche Summenformel
Behauptung: Für alle gilt : .
Induktionsanfang : Links steht , rechts .
Für die Formel aus der Einleitung lautet der Induktionsschritt . Welcher Term gehört in die Klammer? Schreibe ihn in .
Bernoulli-Ungleichung
Für alle reellen Zahlen und alle gilt
Wir halten fest und führen Induktion über .
Induktionsanfang : .
Induktionsschritt: Es gelte für ein . Wegen ist . Multiplizieren einer Ungleichung mit einer nicht negativen Zahl erhält (für ist das (O4), für sind beide Seiten ). Also
Im letzten Schritt wird benutzt. Das ist die Behauptung für .
Ein späterer Induktionsanfang: 2 hoch n gegen n Quadrat
Ein späterer Induktionsanfang: 2 hoch n gegen n Quadrat
Vergleiche und :
Die Behauptung "" ist für falsch. Wir beweisen sie für alle , also mit .
Induktionsanfang : .
Induktionsschritt: Es gelte für ein . Dann ist
Benutzt werden die Induktionsvoraussetzung, (für ) und . Mit einer feineren Abschätzung ginge der Schritt schon ab . Trotzdem ist die Aussage für und falsch, denn dort fehlt ein wahrer Anfang. Erst Anfang und Schritt zusammen, mit demselben , ergeben einen Beweis.
Teilbarkeit
Teilbarkeit
Für ganze Zahlen heißt ein Teiler von , geschrieben , wenn es ein gibt mit .
Behauptung: Für alle gilt .
Induktionsanfang : .
Induktionsschritt: Es gelte mit . Der Trick ist, den Ausdruck für so umzuformen, dass darin vorkommt:
Also ist . Probe: .
Eine Rekursion auflösen
Eine Rekursion auflösen
Eine Folge sei rekursiv definiert durch und für . (So viele Züge braucht man mindestens beim Spiel "Türme von Hanoi" mit Scheiben.) Die ersten Glieder sind . Das sind immer Zweierpotenzen minus eins.
Vermutung: für alle .
Induktionsanfang: .
Induktionsschritt: Es gelte . Dann ist
Rekursion und Induktion passen zusammen: Die Rekursion sagt, wie aus entsteht, und genau diesen Zusammenhang benutzt der Induktionsschritt. Die Vermutung selbst kommt aus den ersten Gliedern; die Induktion macht aus ihr einen Satz.
Starke Induktion
Es sei und eine Aussageform. Es gelte , und für jedes gelte: Wenn für alle mit wahr ist, dann ist wahr. Dann ist für alle wahr.
Der Unterschied: Im Schritt darf man nicht nur den direkten Vorgänger benutzen, sondern alle früheren Fälle.
Wir wenden die gewöhnliche Induktion auf die Aussageform : " ist wahr für alle mit " an.
ist gerade , also wahr. Gilt , dann liefert die Voraussetzung ; zusammen mit ist das . Also gilt für alle , und damit insbesondere .
Jede Zahl ab 2 ist ein Produkt von Primzahlen
Jede Zahl ab 2 ist ein Produkt von Primzahlen
Behauptung: Jedes ist eine Primzahl oder ein Produkt von Primzahlen.
Induktionsanfang : ist eine Primzahl.
Induktionsschritt: Die Behauptung gelte für alle mit . Ist eine Primzahl, sind wir fertig. Sonst gibt es eine Zerlegung mit ganzen Zahlen und . Nach Voraussetzung sind und Primzahlen oder Produkte von Primzahlen, also auch .
Hier hilft die gewöhnliche Induktion nicht: Die Faktoren von sind kleiner als , aber im Allgemeinen nicht gleich . Zum Beispiel ist , und über zu wissen hilft dabei nichts.
Den Induktionsanfang vergessen
Den Induktionsanfang vergessen
"Behauptung: . Schritt: Gilt das für , dann ist . Also gilt es für alle ."
Der Schritt ist korrekt gerechnet, und trotzdem ist die Formel für jedes falsch: Für steht links und rechts . Der Schritt zeigt nur "wenn es für gilt, dann für ". Ohne einen wahren Startfall fällt kein einziger Dominostein. Prüfe den Induktionsanfang immer zuerst, und prüfe ihn wirklich durch Einsetzen.
Alle Pferde haben dieselbe Farbe
Alle Pferde haben dieselbe Farbe
"Behauptung : In jeder Menge von Pferden haben alle dieselbe Farbe. Anfang : Ein Pferd hat dieselbe Farbe wie es selbst. Schritt: Gegeben seien Pferde . Ohne bleiben Pferde, die nach Voraussetzung gleichfarbig sind; ebenso ohne . Die beiden Gruppen überschneiden sich, also haben alle dieselbe Farbe."
Der Schritt muss für jedes funktionieren, und für tut er das nicht. Bei zwei Pferden sind die beiden Gruppen und . Sie überschneiden sich nicht, und es gibt kein Pferd, über das man die Farben vergleichen könnte. Der Schritt von auf ist also falsch; alle anderen Schritte (ab ) sind zwar richtig, aber sie hängen an diesem einen. Prüfe den Schritt besonders für das kleinste , bei dem er benutzt wird.
Zusammenfassung
Vollständige Induktion: Aus dem Induktionsanfang und dem Induktionsschritt " für jedes " folgt für alle .
Das Prinzip folgt aus dem Wohlordnungsprinzip: Ein kleinstes Gegenbeispiel kann es nicht geben.
Summen und Potenzen sind rekursiv definiert. Im Schritt spaltet man den letzten Summanden oder Faktor ab und setzt die Induktionsvoraussetzung ein.
Bei Ungleichungen schätzt man im Schritt geschickt ab; bei Teilbarkeit formt man so um, dass der Ausdruck für wieder auftaucht.
Der Induktionsanfang darf bei jedem liegen, er muss aber zum Schritt passen ( erst ab ).
Starke Induktion erlaubt im Schritt alle früheren Fälle; sie folgt aus der gewöhnlichen Induktion.
Typische Fehler: Induktionsanfang vergessen und ein Schritt, der für das kleinste nicht funktioniert (Pferde).
Übungen
Berechne mit der gaußschen Summenformel.
Jemand "beweist" für alle so: Gilt , dann folgt durch Addieren von auf beiden Seiten . Was ist falsch?
Die Folge sei definiert durch und für . Berechne die ersten Glieder, stelle eine geschlossene Formel für auf und prüfe sie mit Induktion.
Beweise mit vollständiger Induktion: Für alle gilt .
Beweise mit vollständiger Induktion: Für alle ist durch teilbar.
Für sei (gelesen " Fakultät"). Ab welchem kleinsten gilt für alle ?
Die Fibonacci-Zahlen sind definiert durch und für . Beweise: für alle . Warum brauchst du zwei Startfälle?