zum Directory-modus

Methode der vollständigen Induktion

Methode der vollständigen Induktion

Das letzte Peano-Axiom bildet die Grundlage für ein wichtiges Beweisprinzip der Mathematik. Man kann es auf Sätze anwenden, in denen in geeigneter Weise natürliche Zahlen auftreten. Die Wahrheit einer unendlichen Sequenz von Aussagen A ( n ) für n = 0 , 1 , 2 , ( n ) lässt sich beweisen, wenn A ( 0 ) wahr ist, und A ( k ) A ( k +1 ) für alle k ist. Dieses Prinzip heißt die Methode der vollständigen Induktion.

Theorem
Sei A ( n ) eine Aussage für jedes n . Wenn (i) A ( 0 ) ist wahr, (ii) für alle k : A ( k ) ist wahr A ( k +1 ) ist wahr gelten. Dann gilt die Aussage A ( n ) für alle n .
Beweis

Ist der Satz nicht wahr, so existiert eine kleinste natürliche Zahl m , für die die Aussage A ( m ) nicht wahr ist. Aber folglich muss die Aussage A ( m -1 ) wahr sein und dies ist gemäß der Implikation A ( m -1 ) A ( m ) unmöglich.

In Fällen, wo die Aussage A ( n ) erst von einem gewissen n 0 an definiert ist, ist die Methode ebenso anwendbar. Man zeigt stattdessen die Gültigkeit der Implikation A ( k ) A ( k +1 ) für alle k n 0 .

Die Methode der vollständigen Induktion besteht aus drei Teilen:

  1. Induktionsanfang. Die Gültigkeit von A ( n 0 ) ist zu zeigen.
  2. Induktionsschritt. Die Gültigkeit der Implikation A ( k ) A ( k +1 ) für alle k n 0 , k ist zu zeigen, d.h. falls A ( k ) wahr ist, so ist auch A ( k +1 ) wahr.
  3. Induktionsschluss. Gemäß dem Satz gilt die Wahrheit der Aussage A ( n ) für n n 0 , n

Beispiel

Gegeben sei die Vermutung

n 2 2 n + 3 für n 3

Wir beweisen die Vermutung mit dem Prinzip der vollständigen Induktion.

  1. Induktionsanfang. A ( 3 ) gilt, da 9 = 3 2 2 3 + 3 = 9 .
  2. Induktionsschritt. Wir versuchen, die Implikation k 2 2 k + 3 ( k +1 ) 2 2 ( k +1 ) + 3 k 3 festzustellen. Rechnen wir ( 2 k +1 ) zu beiden Seiten der Ungleichung k 2 2 k + 3 hinzu, so ergibt sich: k 2 2 k + 3 k 2 + ( 2 k +1 ) 2 k + 3 + ( 2 k +1 ) ( k +1 ) 2 2 k + 2 + 2 k + 2 ( k +1 ) 2 2 ( k + 1 ) + 2 k + 2 ( k +1 ) 2 2 ( k + 1 ) + 3 , da 2 k + 2 3 k 3 ist. Somit ist die Implikation festgestellt.
  3. Induktionsschluss. Folglich ist die Aussage n 2 2 n + 3 für n 3 bewiesen.

Man beachte: Die Methode der mathematischen Induktion beweist eine gegebene Formel, gibt aber keinerlei Andeutung, wie die Formel gefunden wurde. Deswegen ist sie eher eine Bestätigung einer richtigen Hypothese. Wie man zu der richtigen Hypothese gelangt, dafür kann man keine allgemeine Regeln angeben.

<Seite 1 von 1>