Der Beweis mit vollständiger Induktion ist ein Beweisprinzip für Aussagen über natürliche Zahlen \(n\), die größer oder gleich einem bestimmten Startwert sind. Die Aussage, die von \(n\) abhängt, bezeichnen wir mit \(A(n)\). Der Startwert, ab dem die Aussage gelten soll, bezeichnen wir mit \(n_0\). Oft wird der Startwert \(n_0\) den Wert \(0\) oder \(1\) annehmen. Es gibt aber auch Behauptungen, die ab einem anderen Startwert gelten.

Den Beweis, dass die Aussage \(A(n)\) für alle \(n\ge n_0\) gilt, unterteilt man in einen Induktionsanfang und einen Induktionsschritt:

Im Induktionsanfang wird also bewiesen, dass die Aussage für eine kleinste Zahl gilt. Wir werden später an einem Beispiel sehen, dass es unbedingt notwendig ist, den Induktionsanfang zu zeigen. Verzichtet man hierauf, dann lassen sich beliebige Behauptungen beweisen.

Beim Induktionsschritt wird bewiesen, dass wenn die Aussage für eine bestimme, aber beliebige Zahl \(n\) gilt, sie auch für die nächst größere Zahl \(n+1\) gelten muss. Da ausgehend vom Startwert der Induktionsschritt unendlich oft durchgeführt werden kann, muss die Aussage dann für alle natürlichen Zahlen ab dem Startwert gelten. Der Induktionsschritt wird häufig auch als Induktionsschluss bezeichnet.

Man kann sich das Beweisprinzip der vollständigen Induktion wie das Umstoßen von Dominosteinen vorstellen. Fällt der erste Dominostein und wird durch jeden fallenden Dominostein der nächste Dominostein umgestoßen, dann wird schließlich jeder Dominostein umfallen.

Dies wird in der folgenden Animation verdeutlicht. Als Startwert wurde \(n_0=0\) gewählt. Über den Schieberegler können Sie \(n\) zwischen dem Startwert und dem Wert \(10\) variieren. Dies kann auch animiert geschehen. Starten Sie hierzu die Animation durch Anklicken von \(\blacktriangleright\). Durch einen Klick auf \(\parallel\) können Sie die Animation anhalten.

Ist der Startwert \(n_0\) nicht \(0\), sondern \(1\), \(2\), ..., so können aus der Aussage \(A(n_0)\) nur die folgenden Aussagen \(A(n_0+1)\), \(A(n_0+2)\), ... abgeleitet werden.

Schauen Sie sich hierzu die folgende Animation an. Sie können den Startwert \(n_0\) auf dem Schieberegler zwischen \(0\) und \(4\) variieren. Die Aussagen \(A(n)\) beginnen dann bei \(A(n_0)\). Auch hier können Sie über den Schieberegler \(n\) die Dominosteine animiert fallen lassen. Starten Sie hierzu die Animation durch Anklicken von \(\blacktriangleright\). Durch einen Klick auf \(\parallel\) können Sie die Animation anhalten.