Lernmodul: Beweisprinzipien

Funzioni

PrecedenteBeispiel mit einem Produkt 
  Beispiel mit Teilbarkeit Successivo

Beispiel mit einer Ungleichung

Wir zeigen nun ein Beispiel für einen Beweis einer Ungleichung mithilfe der vollständigen Induktion.
Beispiel:
Wir zeigen mit vollständiger Induktion die folgende Aussage für \(n\ge 10\):
\(\qquad\)
\(2^n \gt n^3\)
Zum besseren Verständnis der Aussage schauen wir uns an, welche Werte in Abhängigkeit von \(n\) die Ungleichung auf beiden Seiten annimmt. Hierzu betrachten wir \(n\ge 8\), um zu sehen, dass die Ungleichung tatsächlich erst dann erfüllt ist, wenn \(n\) größer gleich \(10\) ist.
\(\qquad\)
\(2^n \gt n^3\)
\(\enspace n\enspace\)
\(2^n\)
\(n^3\)
\(8\)
\(2^8=256\)
\(8^3=512\)
\(9\)
\(2^9=512\)
\(9^3=729\)
\(10\)
\(2^{10}=1024\)
\(10^3=1000\)
\(11\)
\(2^{11}=2048\)
\(11^3=1331\)
\(12\)
\(2^{12}=4096\)
\(10^3=1728\)
Beweis mit vollständiger Induktion:
Induktionsanfang:
Linke Seite:
\(\qquad\)
\(2^{10}=1024\)
Rechte Seite:
\(\qquad\)
\(10^3=1000\)
Da \(2^{10}\gt 10^3\), ist der Induktionsanfang somit gezeigt.
Induktionsschritt:
Induktionsvoraussetzung:
\(\qquad\)
Wir nehmen an, dass für ein festes, aber beliebiges \(n\) gilt:
\(\qquad\)
\(2^n \gt n^3\qquad (*)\)
Induktionsbehauptung:
\(\qquad\)
Wir behaupten, dass dann auch gilt:
\(\qquad\)
\(2^{n+1} \gt (n+1)^3\)
Induktionsbeweis:
\(\qquad\)
\(2^{n+1}=\underbrace{2^n}_{(*)}\cdot 2\)
\(\qquad\)
Da \(2^n\) laut Induktionsvoraussetzung \((*)\) größer ist als \(n^3\), können wir folgern:
\(\qquad\)
\(2^{n+1}\gt n^3\cdot 2=n^3+n^3\)
\(\qquad\)
Da für \(n\ge 10\) auch \(n \cdot n^2\) größer als \(7 \cdot n^2\), können wir weiter abschätzen:
\(\qquad\)
\(2^{n+1}\gt n^3+n^3\gt n^3+7n^2\)
\(\qquad\)
Nun zerlegen wir \(7n^2\) und erhalten hiermit:
\(\qquad\)
\(2^{n+1}\gt n^3+3n^2+3n^2+n^2\)
\(\qquad\)
Da \(n\gt 1\), ist \(n^2\) auch größer als \(1\). Wir schätzen also weiter ab:
\(\qquad\)
\(2^{n+1}\gt n^3+3n^2+3n^2+n^2\gt n^3+3n^2+3n+1\)
\(\qquad\)
Wir faktorisieren nun die rechte Seite und erhalten die Induktionsbehauptung:
\(\qquad\)
\(2^{n+1}\gt (n+1)^3\)
Durch den Induktionsbeweis haben wir gezeigt, dass der Induktionsschritt richtig ist und die Aussage nun wegen der vollständigen Induktion für alle \(n\in\mathbb{N}\) mit \(n\ge 10\) wahr ist.
\(\blacksquare\)
\(\enspace\)
 Quellen 
 Glossar 
PrecedenteBeispiel mit einem Produkt 
  Beispiel mit Teilbarkeit Successivo