Beweise, vollständige Induktion

Das Verfahren der vollständigen Induktion hängt eng zusammen mit der Menge der natürlichen Zahlen bzw. mit Teilmengen natürlicher Zahlen. Es ist immer dann anwendbar, wenn man auf Aussagen trifft, die für alle natürlichen Zahlen gelten, also die die folgende Struktur aufweisen:

Für alle natürlichen Zahlen n(mitnn0) gilt H(n).

Das Verfahren beruht auf der sogenannten Induktionseigenschaft der natürlichen Zahlen. Diese ist Bestandteil des peanoschen Axiomensystems und lautet:

Ist T eine Teilmenge von und gilt
(I)1T(II)Fürallengilt:nTn+1T,
dann ist T=.

Es sei T={n:H(n)} die Menge aller natürlichen Zahlen, für die eine Aussage H(n) wahr ist.
Anwenden der Induktionseigenschaft besagt dann das Folgende.
Wenn man zeigen kann
a)H(1)istwahr,d.h.1T.b)Fürallengilt:WennH(n)wahrist,soistH(n+1)wahr.nTn+1Tfürallen
dann gilt (aufgrund der als Axiom angenommenen Induktionseigenschaft) T=, was wiederum bedeutet H(n) ist für alle n gültig.

Um die Allgemeingültigkeit einer Aussage H(n) über nachzuweisen, hat man also beim Beweis durch vollständige Induktion zwei Schritte zu vollziehen:

  • Induktionsanfang
    Man zeigt, dass H(1) wahr ist.
  • Induktionsschritt
    Man zeigt, dass für alle n gilt: Aus der Annahme, H(n) sei richtig, kann auf die Gültigkeit von H(n+1) geschlossen werden, d. h.:
    H(n)H(n+1)fürallen
    (Inhalt des Induktionsschrittes ist also eine Implikation AB. Das Vorderglied heißt Induktionsvoraussetzung und das Hinterglied dieser Implikation ist die Induktionsbehauptung.)

Wichtig ist, dass beide Schritte verifiziert werden müssen, d. h. als wahr nachzuweisen sind: sowohl der Induktionsanfang (es muss erst einmal eine natürliche Zahl geben, für die H(n) gilt) als auch der Induktionsschritt oder Induktionsschluss (Nachweis der obigen Implikation). Erst dann gilt, dass H(n) für alle wahr n ist.

Die Struktur des Beweises durch vollständige Induktion sieht formal also folgendermaßen aus:
H(1)[Fürallen:H(n)H(n+1)][Fürallen:H(n)]oderH(n0)[Fürallek:H(k)H(k+1)][Fürallenn0:H(n)]

Beispiel 1:

Man beweise durch vollständige Induktion:
i=1ni3=13+23+33+...+n3=[n(n+1)2]2

  • Induktionsanfang
    n=1:i=11i3=13=(1(1+1)2)21=1
  • Induktionsschritt
    Induktionsvoraussetzung (n = k):
    Es gelte i=1ki3=13+23+33+...+k3=[k(k+1)2]2.
    Induktionsbehauptung (n = k + 1):
    Es sei i=1k+1i3=13+23+33+...+k3+(k+1)3=[(k+1)(k+2)2]2.
    Induktionsbeweis:
    i=1k+1i3=i=1ki3+(k+1)3=[k(k+1)2]2+(k+1)3=k2(k+1)2+4(k+1)34=k2(k+1)2+4(k+1)2(k+1)4=(k+1)2(k2+4k+4)4=(k+1)2(k+2)24=[(k+1)(k+2)2]2

Beispiel 2:

Man beweise: Für alle n gilt 133|(11n+2+122n+1).

  • Induktionsanfang
    n=0:112+12=133133|133
  • Induktionsschritt
    Induktionsvoraussetzung (n = k − 1):
    Es gelte 133|(11k+1+122k1).
    Induktionsbehauptung (n + 1 = k):
    Dann sei auch 133|(11k+2+122k+1).
    Induktionsbeweis:
    11k+2+122k+1=11k+111+122k1122=11k+1+1011k+1+122k1+143122k1=11k+1+122k1+1011k+1+143122k1=11k+1+122k1+10(11k+1+122k1)nachVoraussetzungdurch133teilbar+133122k1
    Folglich gilt 133|(11n+2+122n+1).
Learnattack

Gemeinsam zu besseren Noten!Kooperation mit Duden Learnattack

Lernvideos, interaktive Übungen und WhatsApp-Nachhilfe – jetzt Duden Learnattack 48 Stunden kostenlos testen.

Du wirst automatisch zu Learnattack weitergeleitet.
Lexikon Share
Beliebte Artikel
alle anzeigen

Einloggen