1.3 Natürliche Zahlen und Vollständige Induktion (Fortsetzung 2)
In seltenen Fällen gilt die Aussage nicht bereits für n=1, sondern erst ab einer größeren Zahl \(n_0\).
Diese Zahl muss man zuerst irgendwie herausfinden. Anschließend geht man fast genauso vor, nur den Induktionsanfang führt man mit der Zahl \(n=n_0\) statt mit \(n=1\) durch.
Beispielsweise ist die Aussage \(3n^3<3^ n\) für \(n=1,2,3,4,5\) falsch, für alle natürlichen Zahlen \(n\geq 6\) jedoch wahr. Dies lässt sich mit Vollständiger Induktion beweisen, wenn man den Induktionsanfang bei \(n_0=6\) macht.
Dazu vergewissert man sich, dass \(3\cdot 6^3=648<3^6=729\) ist. Der Induktionsschritt von \(n\) nach \(n+1\) darf dann ebenfalls die Bedingung \(n\geq 6\) benutzen, und lautet in Kurzform beispielsweise
\(3(n+1)^3=3n^3+9n^2+9n+3\leq 3n^3+3n^3+\frac{1}{4}n^3 +3 < 3 \cdot 3^n=3^{n+1}\).
Als weitere Anwendung des Prinzips der Vollständigen Induktion leiten wir noch eine nützliche Ungleichung her.
\((1+h)^n\geq 1+nh.\)
Das beweisen wir nun mittels Vollständiger Induktion nach \(n\). Die Zahl \(h\) ist dabei fest, aber im Rahmen der oben gemachten Einschränkungen (\(h>-1\) und \(h\neq 0\)) frei wählbar.
Induktionsanfang (n=1):
Setzt man auf beiden Seiten der Behauptung für \(n=1\) ein, erhält man die offenbar wahre (Un-)Gleichung \(1+h\geq 1+h\).
Induktionsschritt (von n nach n+1):
Wir dürfen als Induktionsvoraussetzung benutzen, dass die Ungleichung für eine Zahl \(n\) gilt. Daraus wollen wir dann folgern, dass sie auch für die nächste Zahl \(n+1\) korrekt ist. Dazu berechnen wir die linke Seite der Ungleichung mit \(n+1\) statt \(n\):
\(\begin{array}{rcl}\Rightarrow(1+h)^{n+1}&=&(1+h)\cdot(1+h)^n\\&\geq&(1+h)(1+nh)\;\leftarrow\,\;\text{Induktionsvoraussetzung}\\&=&1+(n+1)h+nh^2>1+(n+1)h.\end{array}\)
Damit gilt die Ungleichung auch für die Zahl n+1.
Nach dem Prinzip der Vollständigen Induktion reicht das aus, um sicherzugehen, dass die Bernoullische Ungleichung tatsächlich für alle natürlichen Zahlen \(n\in \mathbb{N}\) gilt.
☐
Sie können sich nun entscheiden. Wenn Sie noch mehr Beispiele zur Vollständigen Induktion sehen möchten, können Sie dem ersten Link folgen. Sie können aber auch direkt mit dem nächsten Abschnitt über Abzählmethoden fortfahren