Lösung für Aufgabe 2.5.10
Für welche $n\in \N$ gilt $2^n > n^2$? Beweisen Sie ihre Vermutung mit vollständiger Induktion!Die Behauptung gilt für alle $n \geq 5$. Wir beweisen mittels vollständiger Induktion. Induktionsanfang: $n=5$ $$32 > 25.$$ Induktionsbehauptung: Für alle $n \geq 5$ gelte $$2^n > n^2.$$ Induktionsschritt $n \to n+1$: $$2^{n+1}=2\cdot 2^n>n^2\cdot 2>n^2+2n+1$$ der letzte Schritt gilt, sobald $2n^2>n^2+2n+1 \Leftrightarrow n^2>2n+1 \Leftrightarrow n^2-2n+1 > 2 \Leftrightarrow (n-1)^2>2.$ Das ist aber für alle $n\geq 3$ der Fall. Wir betrachten aber sowieso nur $n \geq 5$. Deswegen gilt: $$2^{n+1}>(n+1)^2=n^2+2n+1$$ $\Box$