1.3 Natürliche Zahlen und Vollständige Induktion (Fortsetzung 1)
Eine Art "‘Dominoprinzip"’, mit dem man Aussagen, die für alle natürlichen Zahlen gelten, nachweisen kann, funktioniert wie folgt:
Aus der Gültigkeit der Formel für ein beliebiges n (zum Beispiel für die Zahl \(n=1\), aber auch für \(n=999\, 999\)), folgert man die Gültigkeit für die Zahl \(n+1\) (also für \(n=2\) oder eben \(n=1\, 000\, 000\)).
Dann argumentiert man folgendermaßen:
Man prüft zuerst nach, dass die Summenformel für \(n=1\) stimmt.
Weil sie für \(n=1\) stimmt, stimmt sie auch für \(n=2\).
Weil sie für \(n=2\) stimmt, stimmt sie auch für \(n=3\).
Weil sie für \(n=3\) stimmt, stimmt sie auch für \(n=4\).
Undsoweiterundsofort...
Will man sicher sein, dass die Formel (zum Beispiel) auch für die Zahl \(n=999\, 999\) stimmt, dann muss man diesen Schritt (natürlich nur in Gedanken) so lange durchführen, bis man bei \(n=999\, 999\) angekommen ist. Dass das wirklich funktioniert, liegt daran, dass man die Argumentation nicht für eine konkrete Zahl, sondern für beliebiges n durchführt.
Im Prinzip könnte man sich auf diese Art bis zu jeder noch so großen Zahl durchhangeln. Aus diesem Grund, weil man auf diese Weise bis zu jeder beliebigen Zahl n kommen könnte, muss die Formel tatsächlich für alle natürlichen Zahlen n stimmen. Dieses Verfahren nennt man Prinzip der Vollständigen Induktion oder kurz Vollständige Induktion.
-
Induktionsanfang (auch Verankerung genannt):
Man zeigt, dass die Aussage/Formel für eine Zahl \(n_0\) (meist für \(n_0=1\)) stimmt -
Induktionsschritt (auch Schluss von n nach n+1 genannt):
Man zeigt, dass die Aussage/Formel auch für die Zahl n+1 richtig ist, wenn man voraussetzt, dass sie für die Zahl n stimmt
Wenn man im Induktionsschritt benutzt, dass \(A(n)\) speziell für die Zahl n wahr ist, dann nennt man das die Induktionsvoraussetzung .
In unserem Beispiel sehen diese beiden Argumentationsschritte konkret so aus:
1.Schritt: Induktionsanfang bei n=1:
Hier ist nicht viel nachzurechnen, man setzt n=1 auf beiden Seiten der Vermutung ein, und erhält so
\(1=1^2\)
und sieht sofort, dass die Gleichung erfüllt ist.
2.Schritt: Induktionsschritt von n nach n+1
Wenn tatsächlich $1+3+5+7+\ldots + (2n-1)= n^2$ (das ist hier die Induktionsvoraussetzung) gilt, dann ist
\(\begin{array}{rcl}1+3+\ldots+(2n-1)+(2n+1)&\!=&\\\underbrace{\left(1+3+\ldots+(2n-1)\right)}_{=n^2}+(2n+1)&\!=&\!n^2+2n+1=(n+1)^2.\end{array}\)
Die Formel stimmt also auch für die Zahl \(n+1\).
Mit dem oben beschriebenen Prinzip der Vollständigen Induktion folgert man nun, dass die Formel wirklich für alle natürlichen Zahlen n stimmt.