Lernmodul: Beweisprinzipien

Aufgabe 1

Zeigen Sie mit vollständiger Induktion die folgende Aussage für \(n\ge 4\):

\(\qquad\)

\(n! \gt 2^n\)

Weshalb gilt die Ungleichung erst für einen Startwert von \(4\) und nicht für alle natürlichen Zahlen?

Beweis mit vollständiger Induktion:

Induktionsanfang:

Linke Seite:

\(\qquad\)

\(4!=1\cdot 2 \cdot 3 \cdot 4 =24\)

Rechte Seite:

\(\qquad\)

\(2^4=16\)

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.

\(\enspace\)

 Quellen 

 Glossar