Beweisverfahren der vollständigen Induktion

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ür alle  n gilt: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) ist wahr, d.h.1T.b)Für alle n gilt:Wenn  H(n) wahr ist, so ist H(n+1) wahr.nTn+1T für alle n

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:

  1. Induktionsanfang
    Man zeigt, dass H(1) wahr ist.
     
  2. 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ür alle n

    (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ür alle n:H(n)H(n+1)][Für alle n:H(n)]oderH(n0)[Für alle k:H(k)H(k+1)][Für alle nn0:H(n)]

Beispiel 1

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

  1. Induktionsanfang
    n=1: i=11i3=13=(1(1+1)2)21=1
  2. 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).

  1. Induktionsanfang
    n=0: 112+12=133133|133
  2. Induktionsschritt
    Induktionsvoraussetzung (n = k):
    Es gelte 133|(11k+1+122k1).
    Induktionsbehauptung (n = k + 1):
    Es 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)nach Voraussetzung durch 133 teilbar+133122k1
    Folglich gilt 133|(11n+2+122n+1).

Stand: 2010
Dieser Text befindet sich in redaktioneller Bearbeitung.

Lernhelfer-App für dein Smartphone oder Tablet

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