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 )   1 T ( I I )   Für alle     n   gilt : n T n + 1 T ,
    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 . 1 T . b ) Für alle   n   gilt : Wenn   H ( n )   wahr   ist,   so ist   H ( n + 1 )   wahr. n T n + 1 T   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 A B . 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 ) ] o d e r H ( n 0 ) [ Für alle   k : H ( k ) H ( k + 1 ) ] [ Für alle   n n 0 : H ( n ) ]

Beispiel 1

Man beweise durch vollständige Induktion:
i = 1 n i 3 = 1 3 + 2 3 + 3 3 + ... + n 3 = [ n ( n + 1 ) 2 ] 2

  1. Induktionsanfang
    n = 1 :   i = 1 1 i 3 = 1 3 = ( 1 ( 1 + 1 ) 2 ) 2 1 = 1
  2. Induktionsschritt
    Induktionsvoraussetzung (n = k):
    Es gelte i = 1 k i 3 = 1 3 + 2 3 + 3 3 + ... + k 3 = [ k ( k + 1 ) 2 ] 2 .
    Induktionsbehauptung (n = k + 1):
    Es sei i = 1 k + 1 i 3 = 1 3 + 2 3 + 3 3 + ... + k 3 + ( k + 1 ) 3 = [ ( k + 1 ) ( k + 2 ) 2 ] 2 .
    Induktionsbeweis:
    i = 1 k + 1 i 3 = i = 1 k i 3 + ( k + 1 ) 3 = [ k ( k + 1 ) 2 ] 2 + ( k + 1 ) 3 = k 2 ( k + 1 ) 2 + 4 ( k + 1 ) 3 4 = k 2 ( k + 1 ) 2 + 4 ( k + 1 ) 2 ( k + 1 ) 4 = ( k + 1 ) 2 ( k 2 + 4 k + 4 ) 4 = ( k + 1 ) 2 ( k + 2 ) 2 4 = [ ( k + 1 ) ( k + 2 ) 2 ] 2

Beispiel 2

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

  1. Induktionsanfang
    n = 0 :   11 2 + 12 = 133 133 | 133
  2. Induktionsschritt
    Induktionsvoraussetzung (n = k):
    Es gelte 133 | ( 11 k + 1 + 12 2 k 1 ) .
    Induktionsbehauptung (n = k + 1):
    Es sei auch 133 | ( 11 k + 2 + 12 2 k + 1 ) .
    Induktionsbeweis:
    11 k + 2 + 12 2 k + 1 = 11 k + 1 11 + 12 2 k 1 12 2 = 11 k + 1 + 10 11 k + 1 + 12 2 k 1 + 143 12 2 k 1 = 11 k + 1 + 12 2 k 1 + 10 11 k + 1 + 143 12 2 k 1 = 11 k + 1 + 12 2 k 1 + 10 ( 11 k + 1 + 12 2 k 1 ) n a c h   V o r a u s s e t z u n g   d u r c h   133   t e i l b a r + 133 12 2 k 1
    Folglich gilt 133 | ( 11 n + 2 + 12 2 n + 1 ) .

Stand: 2010
Dieser Text befindet sich in redaktioneller Bearbeitung.

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