Größere Schriftzeichen   

Beispiel für einen Induktionsbeweis:

Wir beweisen die Aussage ''Für alle natürlichen Zahlen n gilt: Die Summe aller natürlichen Zahlen von 1 bis n ist n(n+1)/2''.

Um die Struktur der ''Beweisführung durch vollständige Induktion'' möglichst offenzulegen, bezeichnen wir mit An die Aussage ''Die Summe aller natürlichen Zahlen von 1 bis n ist n(n+1)/2''. In Formeln besagt sie

1 + 2 + 3 + ... + n   =   n ( n + 1 )
2
 .
(1)
Insgesamt haben wir damit unendlich viele Aussagen definiert: A1, A2, A3 usw. Jede dieser Aussagen kann zunächst wahr oder falsch sein. Unser Ziel ist es, die Richtigkeit aller zu beweisen.

Noch eine kleine Vorbemerkung: Ist n eine natürliche Zahl, so ist An+1 die Aussage ''Die Summe aller natürlichen Zahlen von 1 bis n+1 ist (n+1)(n+2)/2'', oder, in Formeln

1 + 2 + 3 + ... + n + ( n + 1 )   =   ( n + 1 ) ( n + 2 )
2
 .
(2)

Die rechte Seite ergibt sich, indem das n im Ausdruck n(n+1)/2 durch n+1 ersetzt wird.

Nun der Beweis:

Zunächst ist A1 eine wahre Aussage (Induktionsanfang). Das läßt sich direkt nachprüfen, indem in (1) für n die Zahl 1 eingesetzt wird. Es ergibt sich die Aussage 1 = 1, welche zweifellos stimmt.

Nun nehmen wir an, An sei für irgendein n wahr (Induktionsannahme oder Induktionsvoraussetzung) und versuchen, daraus auf die Richtigkeit von An+1 zu schließen (Induktionsschluß). Die Summe aller natürlichen Zahlen von 1 bis n+1 ist gleich

(Summe aller natürlichen Zahlen von 1 bis n) + ( n + 1 ) .
(3)
Laut Induktionsannahme ist die Summe aller natürlichen Zahlen von 1 bis n gleich n(n+1)/2, woraus sich mit (3) die Summe aller natürlichen Zahlen von 1 bis n+1 zu
n ( n + 1 )
2
  +  n + 1
(4)
ergibt. Dies kann zu
n ( n + 1 )
2
  +  n + 1
=
n ( n + 1 )
2
 + 2 ( n + 1 )
2
   =
=
n ( n + 1 ) + 2 ( n + 1 )
2
   =   ( n + 1 ) ( n + 2 )
2
umgeformt werden und ist identisch mit der rechten Seite von (2). Damit ist die Richtigkeit von An+1 - unter der Voraussetzung jener von An - gezeigt. Aus der (probeweise angenommenen) Richtigkeit einer der Aussagen folgt die Richtigkeit der nächsten!

Nun sind wir auch schon fertig: Daß A1 wahr ist, haben wir oben überprüft. Daher ist auch A2 wahr (denn A2 ist die auf A1 folgende Aussage), und ebenso ist A3 wahr (denn A3 ist die auf A2 folgende Aussage), usw.

Wir haben also den Satz An ist wahr für alle natürlichen Zahlen n bewiesen.


Bemerkung:

Der Satz läßt sich auch anders beweisen. Als Carl Friedrich Gauß, einer der weitblickendsten deutschen Mathematiker, in Schulzeiten (man schrieb das späte 18. Jahrhundert) alle Zahlen zwischen 1 und 100 addieren sollte, machte er das zum Erstaunen seines Lehrers so:

gesucht ist: 1 + 2 + 3 + . . . + 98 + 99 + 100
nochmals: 100 + 99 + 98 + . . . + 3 + 2 + 1
Summe beider: 101 + 101 + 101 + . . . + 101 + 101 + 101

Das Doppelte der gesuchten Zahl ist also 101 × 100 = 10100; die gesuchte Zahl ist 5050. Dieses Verfahren läßt sich ohne Weiteres auf die Summe aller natürlichen Zahlen von 1 bis n verallgemeinern (versuchen Sie es!) und liefert genau die Formel (1).