Definition - Vollständige Induktion

• Involvierte Definitionen:
• Veranstaltung: Mathegrundlagen
• Referenz:
  • Mathegrundlagen
  • AlMa
  • @teschl2013

⠀

Definition: Vollständige Induktion

Die vollständige Induktion ist ein zentrales Prinzip der Beweisführung über den natürlichen Zahlen.

Der Induktionsbeweis funktioniert, indem wir zuerst zeigen, dass eine Aussage für einen Basisfall wahr ist (wobei ). Daraufhin zeigen wir, dass die Aussage auch für beliebige Fälle hält.

Jede Vollständige Induktion beginnt also mit einer Aussage (der Induktionsbehauptung) . Diese Aussage legt kurz dar, was überhaupt zu zeigen ist.

Das weitere Vorgehen lässt sich in drei Schritte unterteilen.

1. Induktionsanfang Hier ist zu zeigen, dass die Aussage für einen Basisfall, e.g. gilt.

2. Induktionsannahme (oft auch: Induktionsvoraussetzung) Hier wird angenommen (bzw. behauptet), dass die Aussage für ein beliebiges hält (aber wichtig: nicht für alle )

3. Induktionsschritt Hier wird gezeigt, dass wenn wahr ist, auch der darauffolgende Fall wahr ist.

4. Abschluss Es wir abschließend festgehalten, dass die Induktionsbehauptung nach dem Prinzip der vollständigen Induktion gilt.

Anmerkung

Starke Induktion (Induktionsannahme für alle )

Manchmal ist es notwendig, bei der Induktionsannahme vorauszusetzen, dass diese nicht nur für ein einziges , sondern sogar für alle gilt.^[vgl. @teschl2013, p. 49]

Vollständige Induktion über Mengen

Bei vollständiger Induktion über Mengen (bei denen z.B. ein Element hinzukommt), kann, um zu der Induktionsannahme zurückzukehren, bspw. genommen werden und dann die Menge aufgeteilt werden in

• und

Beispiele

1. Behauptung: Für alle ist

Induktionsanfang Sei der Basisfall . So gilt

Induktionsannahme Wir nehmen im Folgenden an, es gelte .

Induktionsschritt Es ist zu zeigen, dass auch gilt.

Diese Aussage ist Äquivalent zu (wir ersetzen die Summe durch den Bruch unter Bezugnahme auf die Induktionsannahme).

Es ist nun nur noch zu zeigen, dass

2. Behauptung: Für alle ist durch 43 teilbar.

Induktionsanfang Sei der Basisfall . So gilt .

Induktionsannahme Wir nehmen im Folgenden an, es gelte

Induktionsschritt Es ist zu zeigen, dass auch durch 43 teilbar ist.

Dreiundvierzig teilt sowohl den linken, als auch den rechten Teil. Weshalb?

1. wird geteilt, weil der rechte Part der Induktionsannahme entspricht und damit durch 43 teilbar ist.
2. wird geteilt, weil 43 ein Faktor in der Multiplikation ist. .

3. Behauptung: Für alle gilt

Induktionsanfang Sei der Basisfall . So gilt: Der Basisfall hält also.

Induktionsannahme Wir nehmen an, dass für hält.

Induktionsschritt Es ist zu Zeigen, dass für alle gilt

Um zu einer Lösung zu kommen führen wir nun eine Zangenbewegung aus. Wir beginnen mit Links.

Links:

Jetzt habe ich keine Idee mehr, ich schaue mir also Rechts an. Rechts:

Wir finden: Rechts und Links sind nun identisch.

1.2.6 Aufgabe: Beweisen Sie folgende Aussage mit vollständiger Induktion. für alle .

Induktionsanfang Sei der Basisfall . Dann gilt was offensichtlich hält.

Induktionsannahme Wir nehmen an, dass für hält.

Induktionsschritt Es ist zu Zeigen, dass für alle gilt

Wobei Links:

Und Rechts: | Induktionsannahme einsetzen

Wir müssen also zeigen, dass

Es gilt , daher kann das ganze also durchaus klappen.

Damit gilt wieder, Links und Rechts sind identisch.