cross

Vollständige Induktion

Vollständige Induktion

Merke

Die vollständige Induktion ist ein Beweisverfahren für Aussagen , die für eine Teilmenge der natürlichen Zahlen gelten.

Der Induktionsbeweis gliedert sich in zwei Teile:

  • Den Induktionsanfang: Hier wird die kleinste Zahl, für die die Aussage gezeigt werden soll, eingesetzt und überprüft, ob die Aussage stimmt.
  • Den Induktionsschritt: Angenommen, die Aussage ist wahr, dann wird in diesem Teil des Beweises die Gültigkeit der Aussage gezeigt.

Für den Nachweis, dass eine Aussage wahr ist, müssen sowohl Induktionsanfang als auch Induktionsschritt korrekt sein.

Tipp: Diese Beweisidee lässt sich durch das Umstoßen einer Kette von Dominosteinen veranschaulichen.
Der erste umgeworfene Dominostein symbolisiert den Induktionsanfang. Die Eigenschaft, dass Stein von Stein umgeworfen wird, spiegelt den Induktionsschritt wider.
Nur beide Umstände zusammen lassen die komplette Kette umfallen.

Beispiel

Beweise folgende Aussage : für die -te Ableitung der Funktion gilt:

Die Aussage muss also für alle bewiesen werden.
  • Induktionsanfang: Zeige die Aussage für . Es gilt

    Dies ist aber genau die Aussage . Der Induktionsanfang ist also korrekt.
  • Induktionsschritt: Die Induktionsannahme lautet hier, dass die Aussage stimmt.
    Zu zeigen ist in diesem Schritt, dass dann auch die Aussage stimmt.

    Der Induktionsschritt stimmt damit auch.
  • Da sowohl der Induktionsanfang für als auch der Induktionsschritt korrekt sind, ist die Aussage wahr für alle .

Aufgabe 1

Zeige mittels vollständiger Induktion, dass die Zahl für alle gerade ist.

Lösung zu Aufgabe 1

Die Aussage lautet: ist gerade, wobei .

  • Induktionsanfang: ist gerade.
  • Induktionsschritt: Angenommen ist korrekt, dann zeige, dass auch korrekt ist.

    Nach Voraussetzung ist korrekt, das heißt: ist gerade.
  • Da auch immer gerade ist und die Summe zweier gerader Zahlen immer noch gerade ist, stimmt also auch die Aussage .

Aufgabe 2 – Schwierigkeitsgrad: ***

Beweise durch vollständige Induktion, dass für und folgende Aussage gilt:

Diese Ungleichung wird auch Bernoullische Ungleichung genannt.

Lösung zu Aufgabe 2

Sei , dann gilt

  • Induktionsanfang: ():
  • Induktionsschritt: Angenommen es gilt , dann folgt

    Die letzte Termumformung verwendet nicht nur die Induktionsvoraussetzung
    sondern auch die geforderte Eigenschaft, dass gilt. Es gilt weiter
    Insgesamt gilt also
  • Sowohl Induktionsanfang als auch Induktionsschritt sind korrekt und damit ist die Aussage für alle gezeigt.

Aufgabe 3

Zeige mittels vollständiger Induktion, dass die Zahl für alle durch 3 teilbar ist.

Lösung zu Aufgabe 3

Die Aussage lautet: ist durch teilbar, wobei .

  • Induktionsanfang: ist durch teilbar.
  • Induktionsschritt: Angenommen ist korrekt, dann zeige, dass auch korrekt ist.

  • Nach Voraussetzung ist korrekt, das heißt: ist durch teilbar. Da auch immer durch teilbar ist und die Summe zweier durch teilbarer Zahlen ebenfalls durch teilbar ist, stimmt also auch die Aussage .

Veröffentlicht: 20. 02. 2018, zuletzt modifiziert: 20. 02. 2018