Vollständige Induktion: Beispiele – Serlo „Mathe für Nicht-Freaks“

Schema zum Beweis mit vollständiger InduktionBearbeiten

Beispiel einer Aufgabe mit Hilfe der vollständigen Induktion

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 findenBearbeiten

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?  ). 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   (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   setzt. Wenn du zum Beispiel die zu bearbeitende Aussageform   lautet „  ist ungerade“ lautet die Induktionsbehauptung   nicht  ist ungerade“, sondern „  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 aufschreibenBearbeiten

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:

Aussageform, deren Allgemeingültigkeit für   bewiesen werden soll:

<Aussageform aufschreiben, welche bewiesen werden soll>

1. Induktionsanfang:

<gefundenen Beweis für den Induktionsanfang aufschreiben>

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

<Induktionsvoraussetzung formulieren>

2b. Induktionsbehauptung:

<Induktionsbehauptung formulieren>

2c. Beweis des Induktionsschritts:

<gefundenen Beweis für den Induktionsschritt aufschreiben>

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 Bearbeiten

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:

„Beweise durch vollständige Induktion, dass   für alle natürlichen Zahlen   ist.“

Beweisfindung auf dem SchmierblattBearbeiten

Notwendige VorüberlegungenBearbeiten

Frage: Über welche Variable wird die Induktion geführt?

 

Frage: Wie lautet die zu beweisende Aussageform?

 

Der Doppelpunkt steht dabei für „ist definiert durch“.

InduktionsanfangBearbeiten

Frage: Was ist die kleinste sinnvoll einsetzbare natürliche Zahl für  ?

Nach der Aufgabenstellung ist  , also  . Die kleinste, sinnvoll einsetzbare natürliche Zahl ist damit die   , womit die Induktion startet.

Frage: Wie lautet die zu beweisende Aussage für den Induktionsanfang?

Nach dem Einsetzen der   für   in der Aussageform erhalten wir die Aussage:

 

Aufgabe: Finde einen Beweis für den Induktionsanfang.

Bei Summenformeln musst du die im Induktionsanfang entstandene Gleichung verifizieren. Dies erreichst du durch Nachrechnen der beiden Seiten der Gleichung, welche identisch sein müssen. Bei unserer Aufgabe erhalten wir für den linken Term der Gleichung:

 

Für den rechten Term der Gleichung erhalten wir:

 

Damit stimmen beide Seiten der obigen Gleichung überein, so dass   wahr ist.

InduktionsschrittBearbeiten

Frage: Wie lautet die Induktionsvoraussetzung?

Die Induktionsvoraussetzung   lautet  . Wir benutzen hier den Variablennamen  , weil der Name   bereits als Laufindex in der Summe vorkommt.

Frage: Wie lautet die Induktionsbehauptung?

Die Induktionsbehauptung   lautet  .

Aufgabe: Finde den Beweis für den Induktionsschritt.

Wir müssen nun beweisen, dass unter Annahme der Induktionsvoraussetzung die Induktionsbehauptung gilt. Bei Summenformeln können meistens folgende Schritte identifiziert werden:

1. Zerlege die Summe der Induktionsbehauptung so, dass du die Induktionsvoraussetzung anwenden kannst.

Dazu musst du von der Summe so viele Summanden extra schreiben (oder in einer eigenen Summe zusammenfassen), dass die restliche Summe der Summe in der Induktionsvoraussetzung entspricht:

 

2. Induktionsvoraussetzung anwenden.

Nun kann die Induktionsvoraussetzung verwendet werden:

 

Somit müssen wir jetzt folgende Gleichheit beweisen:

 

3. Termumformungen finden, um eine Seite der Gleichung in die andere zu überführen.

Wie du auf die notwendigen Termumformungen kommst wird im Abschnitt „Terme – Notwendige Termumformungen finden“ beschrieben.

Aufgabe: Versuche obige Gleichung durch Termumformumgen zu beweisen

 

Beweis aufschreibenBearbeiten

Nun kann der Beweis nach dem obigen Schema aufgeschrieben werden.

Aussageform, deren Allgemeingültigkeit für   bewiesen werden soll:

 

1. Induktionsanfang:

Für   gilt:

 

Damit ist   wahr.

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

 

2b. Induktionsbehauptung:

 

2c. Beweis des Induktionsschritts:

Es gilt:

 

Damit ist die Induktionsbehauptung bewiesen.

Beweise von Ungleichungen Bearbeiten

Ungleichung mit SummenformelBearbeiten

AufgabeBearbeiten

Beweise, dass für alle   die Ungleichung   gilt.

LösungswegBearbeiten

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   nennt man harmonische Folge, die Summe über diese Folge wird dementsprechend harmonische Reihe genannt). Die Aussageform, deren Allgemeingültigkeit zu beweisen ist, lautet:

 

Frage: Wie lautet der Induktionsanfang?

Fangen wir wie immer mit dem Induktionsanfang an. Wie oben ist die kleinste sinnvoll einsetzbare Zahl für   die  . Die Aussage für  , die wir beweisen müssen, lautet:

 

Nun Rechnen wir die linke Seite der Ungleichung aus und erhalten:

 

Da   ist, ist damit die Ungleichung für   und somit der Induktionsanfang bewiesen.

Nun geht es mit dem Induktionsschritt weiter. Nach Induktionsvoraussetzung nehmen wir an, dass   für ein bestimmtes   gültig ist. Unsere Aufgabe ist es, zu beweisen, dass unter dieser Annahme   auch gültig sein muss (beachte, dass wir für die Induktionsbehauptung überall   durch   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  .

Die rechte Seite der Ungleichung lässt sich auch als Summe schreiben (dadurch können wir beide Seiten besser miteinander vergleichen). Es ist   und somit lautet unsere zu beweisende Ungleichung:

 

Wir wissen nach der Induktionsvoraussetzung bereits, dass   ist. Wenn wir nun beweisen könnten, dass   wäre, wäre unsere Induktionsbehauptung bewiesen. Hier brauchen wir eine geschickte Abschätzung der Summe. Wir wissen, dass die Summanden   mit wachsendem   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  . Da sich mit   die Summe wahrscheinlich besser zusammenfassen lässt und   ist, versuchen wir mal die Abschätzung mit  . Wir erhalten:

 

Frage: Wie viele Summanden hat nun die Summe  ?

Die Summe hat   Summanden.

Damit ergibt sich die Ungleichung:

 

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

BeweisBearbeiten

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

 

1. Induktionsanfang:

Für   ist

 

2a. Induktionsvoraussetzung:

Sei   .

2b. Induktionsbehauptung:

Wenn   ist, dann ist  .

2c. Beweis der Induktionsbehauptung:

Zunächst gilt für alle  :

 

Damit ist wegen der Induktionsvoraussetzung:

 

Ungleichung ohne SummenformelBearbeiten

AufgabeBearbeiten

Bestimmen Sie alle   für die gilt:

 

LösungswegBearbeiten

Vorüberlegung: Wie kommen wir an unsere  , welche die Ungleichung erfüllen?

Zunächst können wir für die ersten natürlichen Zahlen   überprüfen, ob sie die Bedingung erfüllen:

 

Die Aussage ist für   und   wahr. Wir vermuten deswegen, dass die Ungleichung für alle   erfüllt ist.

BeweisBearbeiten

Die Ungleichung   ist für alle   erfüllt.

Aussageform, deren Allgemeingültigkeit für   mit   bewiesen werden soll:

 

1. Induktionsanfang:

 

2. Induktionsschritt:

2a. Induktionsvoraussetzung:

 

2b. Induktionsbehauptung:

 

2c. Beweis des Induktionsschritts:

 

Aus der Induktionsvoraussetzung wissen wir bereits, dass   gilt. Beweisen wir nun deswegen die fehlende Ungleichung:

 

Die untere Ungleichung kann direkt miteinander verglichen werden und ist insbesondere für alle   wahr.

Beweis von Teilbarkeit Bearbeiten

AufgabeBearbeiten

Beweise, dass alle Zahlen der Form   mit   durch 6 teilbar sind.

LösungswegBearbeiten

Als letztes Beispiel betrachten wir eine Aufgabe zur Teilbarkeit.

Frage: Über welche Variable ist die Induktion zu führen?

Die Induktionsvariable ist  .

Frage: Wie lautet die Aussageform, deren Allgemeingültigkeit zu beweisen ist?

 

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   ist).

Frage: Wie lautet der Induktionsanfang?

Der Induktionsanfang ist laut Aufgabenstellung für   zu führen. Wir erhalten  , was durch sechs teilbar ist.

Frage: Wie lautet die Induktionsvoraussetzung?

Die Zahl   ist durch 6 teilbar.

Frage: Wie lautet die Induktionsbehauptung?

Die Zahl   ist durch 6 teilbar.

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.

Frage: Wie lautet der Beweis für den Induktionsschritt?

Wir erhalten nach obiger Vorgehensweise:

 

Nach Induktionsvoraussetzung wissen wir, dass   durch 6 teilbar ist. Der Summand   ist auch durch sechs teilbar. Und wie sieht es mit   aus? Da entweder   oder   gerade ist, ist entweder   oder   durch zwei teilbar. Damit muss auch   durch 6 teilbar sein.

BeweisBearbeiten

Aufgabe: Schreibe den Beweis auf.

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

 

1. Induktionsanfang:

Für   ist   durch 6 teilbar.

2a. Induktionsvoraussetzung:

Es ist   durch 6 teilbar.

2b. Induktionsbehauptung:

  ist durch 6 teilbar.

2c. Beweis der Induktionsbehauptung:

Es ist  . Normalerweise würdest du jetzt Potenzen von m zusammenfassen zu  . Das ist zwar richtig, aber nicht zielführend. Vielmehr musst du den Term   der Induktionsvoraussetzung ins Spiel bringen, hier durch Umordnen, so dass sich   ergibt. Am Term   kannst du nicht sofort ablesen, dass er für alle   durch 6 teilbar ist. Ein weiterer Induktionsbeweis lässt sich jedoch vermeiden, denn wenn du ausklammerst  , ist die Teilbarkeit sofort zu erkennen, weil m oder m+1 durch 2 teilbar ist. Damit sind alle 3 Summanden von   durch 6 teilbar und der Induktionsbeweis in allen Einzelheiten nachvollziehbar geführt.