Mathe für Nicht-Freaks: Vollständige Induktion: Beispiele

{{#invoke:Mathe für Nicht-Freaks/Seite|oben}}

Schema zum Beweis mit vollständiger Induktion

Datei:01-pyramiden-v3.webm Die folgende Übersicht hilft dir, einen Beweis mit Hilfe vollständiger Induktion zu führen, wie sie im Abschnitt „Prinzip der vollständigen Induktion“ definiert wurde. Zwar kannst du viele Induktionsbeweise nach diesem Schema lösen, aber es gibt auch Ausnahmen!

Lösungsweg: Beweis auf Schmierblatt finden

Kein Beweis fällt vom Himmel – so auch kein Induktionsbeweis. Bevor du den gesuchten Beweis aufschreiben kannst, musst du ihn erst einmal finden (klingt logisch, oder? Vorlage:Smiley). Das folgende Schema soll dir dabei helfen. Die einzelnen Fragen beziehungsweise Schritte kannst du auf Schmierpapier oder im Kopf durchführen. In den nächsten Abschnitten wird dieses Schema an typischen Induktionsaufgaben erklärt und exemplarisch angewandt.

Vorüberlegungen

Fragen/Schritt	Anmerkungen
Über welche Variable wird die Induktion geführt?	Oftmals ist diese Variable $n$ (hat sich so etabliert). Dies muss aber nicht sein und ist aufgabenabhängig.
Wie lautet die Aussageform, deren Allgemeingültigkeit zu beweisen ist?	Mach dir klar, wie die Aussageform aussieht, deren Allgemeingültigkeit du beweisen möchtest/musst.

Induktionsanfang

Fragen/Schritt	Anmerkungen
Welchen Wert hast du für die Induktionsvariable im Induktionsanfang? Welches ist die kleinste natürliche Zahl für den Induktionsanfang?	Meistens geht aus der Aufgabenstellung hervor, wie der Induktionsanfang lautet. Manchmal ist dies aber nicht der Fall und du musst den Induktionsanfang selbst herausfinden, etwa durch Probieren.
Wie lautet die zu beweisende Aussage für den Induktionsanfang	Setze in die Aussageform die oben gefundene Zahl für den Induktionsanfang ein.
Finde einen Beweis für den Induktionsanfang	Hier musst du den Beweis für die oben gefundene Aussage finden. Bei Gleichungen bzw. Ungleichungen gelingt dir dies zum Beispiel dadurch, dass du beide Seiten dieser Gleichung oder Ungleichung ausrechnest und die dadurch entstanden Werte vergleichst.

Induktionsschluss

Fragen/Schritt	Anmerkungen
Wie lautet die Induktionsvoraussetzung?	—
Wie lautet die Induktionsbehauptung?	Achte darauf, dass du die Induktionsbehauptung richtig formulierst, dass du also Klammern um $k+1$ setzt. Wenn du zum Beispiel die zu bearbeitende Aussageform $A(n)$ lautet „$2n+1$ ist ungerade“ lautet die Induktionsbehauptung $A(n=k+1)$ nicht „$2k+2$ ist ungerade“, sondern „$2(k+1)+1=2k+3$ ist ungerade“.
Finde den Beweis für den Induktionsschritt	Finde den Beweis dafür, dass unter Annahme der Induktionsvoraussetzung die Induktionsbehauptung gilt. Hier ist Kreativität gefragt, denn es gibt kein Beweisschema F. Aber meistens kannst du Aufgaben des gleichen oder ähnlichen Typs auf ähnliche Weise lösen (natürlich nicht immer). Das heißt, wenn du schon einige Induktionsbeweise gesehen oder durchgeführt hast, wird es dir leichter fallen, ähnliche Aufgaben zur vollständigen Induktion zu lösen. Es heißt mal wieder: Übung macht den Meister!

Beweis aufschreiben

Nachdem du dir den Beweis im Kopf oder auf Schmierpapier überlegt hast, geht es nun darum, einen sauberen und formal richtigen Beweis aufzuschreiben. Das folgende Schema gibt dir eine mögliche Struktur vor, wie du dies machen kannst:

Bedenke, dass das obige Beweisschema nur eine Möglichkeit ist, einen Beweis für vollständige Induktion aufzuschreiben, an dem du dich aber gut orientieren kannst. Sollten dir mal in einer Klausur, Test oder ähnlichem ein paar Punkte der vollständigen Induktion fehlen, schreibe die restlichen trotzdem auf. Oft werden sie auch schon bewertet.

Beweis einer Summenformel Vorlage:Anker

Als erste Beispielaufgabe wähle ich den Beweis einer Summenformel, da dies ein typisches Anwendungsgebiet der vollständigen Induktion ist. Aber auch Produktgleichungen kannst du auf eine ähnliche Art lösen. Unsere Beispielaufgabe lautet:

Beweis aufschreiben

Nun kann der Beweis nach dem obigen Schema aufgeschrieben werden.

Beweise von Ungleichungen Vorlage:Anker

Ungleichung mit Summenformel

Aufgabe

Beweise, dass für alle $n\in \mathbb{N}$ die Ungleichung $\sum _{k=1}^{2^n-1}\frac{1}{k}\ge \frac{n}{2}$ gilt.

Lösungsweg

Ungleichungen zu beweisen, ist ein weiteres Problem, bei der die vollständige Induktion oftmals eingesetzt wird. Hier sind die notwendigen Termumformungen meist raffinierter als beim Beweis von Summenformeln und man muss geschickte Abschätzungen für Terme finden.

Diese Beispielaufgabe beschreibt eine wichtige Abschätzung der harmonischen Reihe, die noch später im Buch relevant wird (die Folge $1,\frac{1}{2},\frac{1}{3},\dots$ nennt man harmonische Folge, die Summe über diese Folge wird dementsprechend harmonische Reihe genannt). Die Aussageform, deren Allgemeingültigkeit zu beweisen ist, lautet:

Nun geht es mit dem Induktionsschritt weiter. Nach Induktionsvoraussetzung nehmen wir an, dass $\sum _{k=1}^{2^n-1}\frac{1}{k}\ge \frac{n}{2}$ für ein bestimmtes $n$ gültig ist. Unsere Aufgabe ist es, zu beweisen, dass unter dieser Annahme $\sum _{k=1}^{2^{n+1}-1}\frac{1}{k}\ge \frac{n+1}{2}$ auch gültig sein muss (beachte, dass wir für die Induktionsbehauptung überall $n$ durch $n+1$ ersetzt haben). Da wir in der vollständigen Induktion irgendwie die Induktionsvoraussetzung verwenden müssen, sollten wir die Summe so zerlegen, dass die Summe der Induktionsvoraussetzung auftritt (mal schauen, ob uns das gelingt und weiterhilft). Es ist $\sum _{k=1}^{2^{n+1}-1}\frac{1}{k}=\sum _{k=1}^{2^n-1}\frac{1}{k}+\sum _{k=2^n}^{2^{n+1}-1}\frac{1}{k}$.

Die rechte Seite der Ungleichung lässt sich auch als Summe schreiben (dadurch können wir beide Seiten besser miteinander vergleichen). Es ist $\frac{n+1}{2}=\frac{n}{2}+\frac{1}{2}$ und somit lautet unsere zu beweisende Ungleichung:

Wir wissen nach der Induktionsvoraussetzung bereits, dass $\sum _{k=1}^{2^n-1}\frac{1}{k}\ge \frac{n}{2}$ ist. Wenn wir nun beweisen könnten, dass $\sum _{k=2^n}^{2^{n+1}-1}\frac{1}{k}\ge \frac{1}{2}$ wäre, wäre unsere Induktionsbehauptung bewiesen. Hier brauchen wir eine geschickte Abschätzung der Summe. Wir wissen, dass die Summanden $\frac{1}{k}$ mit wachsendem $k$ immer kleiner werden. Da wir die Summe nach unten abschätzen müssen, könnten wir alle Summanden mit dem kleinsten in der Summe vorkommenden Summanden abschätzen. Dies gibt uns die Möglichkeit, die Summe zu vereinfachen und daraus vielleicht eine Abschätzung zu bekommen. Der kleinste Summand wäre $\frac{1}{2^{n+1}-1}$. Da sich mit $\frac{1}{2^{n+1}}$ die Summe wahrscheinlich besser zusammenfassen lässt und $\frac{1}{2^{n+1}-1}>\frac{1}{2^{n+1}}$ ist, versuchen wir mal die Abschätzung mit $\frac{1}{2^{n+1}}$. Wir erhalten:

Damit ergibt sich die Ungleichung:

Somit haben wir den Beweis für die Induktionsbehauptung gefunden.

Beweis

Die Aussageform, deren Allgemeingültigkeit zu beweisen ist, lautet:

1. Induktionsanfang:

Für $n=1$ ist Vorlage:Einrücken

2a. Induktionsvoraussetzung:

Sei $\sum _{k=1}^{2^n-1}\frac{1}{k}\ge \frac{n}{2}$ .

2b. Induktionsbehauptung:

Wenn $\sum _{k=1}^{2^n-1}\frac{1}{k}\ge \frac{n}{2}$ ist, dann ist $\sum _{k=1}^{2^{n+1}-1}\frac{1}{k}\ge \frac{n+1}{2}$.

2c. Beweis der Induktionsbehauptung:

Zunächst gilt für alle $n\in {\mathbb{N}}_{\ge 1}$:

Damit ist wegen der Induktionsvoraussetzung:

Ungleichung ohne Summenformel

Aufgabe

Bestimmen Sie alle $n\in {\mathbb{N}}_{>0}$ für die gilt:

Beweis

Die Ungleichung $\frac{4^n}{n+1}<\frac{(2n)!}{(n!{)}^2}$ ist für alle $n\ge 2$ erfüllt.

Beweis von Teilbarkeit Vorlage:Anker

Aufgabe

Beweise, dass alle Zahlen der Form $a_m=m^3+5m$ mit $m\in {\mathbb{N}}_{\ge 0}$ durch 6 teilbar sind.

Lösungsweg

Als letztes Beispiel betrachten wir eine Aufgabe zur Teilbarkeit.

Im Induktionsanfang musst du wie bei den obigen Beispielen die kleinste sinnvoll einsetzbare Zahl einsetzen und die so ausgerechnete Zahl auf die gewünschte Teilbarkeit überprüfen (beachte dabei, dass jede ganze Zahl ein Teiler von $0$ ist).

Im Beweis des Induktionsschritts hilft es meist, den erhaltenen Term, den du auf Teilbarkeit überprüfen sollst, durch Termumformungen auf eine Summe zu bringen, bei der du weißt, dass jeder seiner Summanden durch die gewünschte Zahl teilbar ist. Versuche dabei die Summe in so eine Struktur zu bringen, dass du die Induktionsvoraussetzung verwenden kannst.

Beweis

{{#invoke:Mathe für Nicht-Freaks/Seite|unten}}