Beweis mit vollständiger Induktion:
| |
Induktionsanfang: Linke Seite: \(\qquad\) | \(4!=1\cdot 2 \cdot 3 \cdot 4 =24\) |
Rechte Seite: Da \(4!\gt 2^4\), ist der Induktionsanfang somit gezeigt. Induktionsschritt: Induktionsvoraussetzung: \(\qquad\) | Wir nehmen an, dass für ein festes, aber beliebiges \(n\) gilt: |
\(\qquad\) | \(n! \gt 2^n\qquad (*)\) |
Induktionsbehauptung: \(\qquad\) | Wir behaupten, dass dann auch gilt: |
\(\qquad\) | \((n+1)! \gt 2^{n+1}\) |
Induktionsbeweis: \(\qquad\) | \((n+1)! =(n+1)\cdot \underbrace{n!}_{(*)}\) |
\(\qquad\) | Wir setzen die Induktionsvoraussetzung \((*)\) ein und erhalten: |
\(\qquad\) | \((n+1)! \gt (n+1)\cdot 2^n\) |
\(\qquad\) | Da \((n+1)\) größer als \(2\) für \(n\ge 2\), gilt: |
\(\qquad\) | \((n+1)! \gt (n+1)\cdot 2^n\gt 2\cdot 2^n=2^{n+1}\) |
\(\qquad\) | Hiermit ist die Behauptung bewiesen. |
| |
| \(\blacksquare\) |
Erläuterung zum Startwert:
Bereits beim Induktionsschritt haben wir festgestellt, dass die Ungleichung nur für \(n\ge 2\) gelten kann. Wir betrachten jetzt also die Ungleichung für \(n=2,3,4,5,...\) bis wir einen Wert für \(n\) gefunden haben, ab dem die Ungleichung gilt.
\(\enspace n\enspace\) | \(n!\) | \(2^n\) |
\(2\) | \(2!=1\cdot 2=2\) | \(2^2=4\) |
\(3\) | \(3!=1\cdot 2\cdot 3=6\) | \(2^3=8\) |
\(4\) | \(4!=1\cdot 2\cdot 3 \cdot 4=24\) | \(2^4=16\) |
\(5\) | \(5!=1\cdot 2\cdot 3 \cdot 4\cdot 5=120\) | \(2^5=32\) |
Die Ungleichung ist aufgrund des obigen Induktionsbeweises für \(n\) größer gleich \(4\) korrekt.
Beispiel mit fehlendem Induktionsanfang 