Aloha :)
Gegeben ist die Rekursionsgleichung:$$F(n+1)=2\cdot(n+1)\cdot F(n)\quad;\quad F(0)=1\;;\;n\in\mathbb N_0$$und wir sollen zeigen, dass$$F(n)\ge n^2+1\quad;\quad n\in\mathbb N_0$$Dazu nutzen wir das Beweisprinzip der vollständigen Induktion.
Verankerung bei \(n=0\):$$F(n)=F(0)=1=0^2+1=n^2+1\quad\checkmark$$
Induktionsschritt von \(n\) auf \((n+1)\)
Wir haben die Behauptung bis zu einem bestimmten \(n\) bereits bewiesen und zeigen nun, dass sie dann auch für \((n+1)\) gilt:
$$F(n+1)=2(n+1)\cdot \underbrace{F(n)}_{\ge n^2+1}\stackrel{\text{(Ind.Ann.)}}{\ge}2(n+1)\cdot(n^2+1)=2n^3+2n^2+2n+2$$$$\phantom{F(n+1)}=(2n^3+\,\underbrace{n^2)+(n^2}_{=2n^2}\,+2n+2)\ge n^2+2n+2=(n^2+2n+1)+1$$$$\phantom{F(n+1)}=(n+1)^2+1\quad\checkmark$$
Nach der Verankerung gilt die Behauptung für \(n=0\), nach dem Induktionsschritt gilt sie dann auch für \(n=1\), nach dem Induktionsschritt gilt sie dann auch für \(n=2\), nach dem Induktionsschritt gilt sie dann auch für \(n=3\)... Die Behauptung gilt also für alle \(n\in\mathbb N_0\).
