Hallo,
Induktionsbeweis für \(n^2 \le 3^n\) für \(n \ge 4\). Es beginnt mit der Induktionsvoraussetzung. Hier für \(n=4\). Es ist $$\begin{aligned}4^2 &\le 3^4 \\ 16 &\le 81 \quad \checkmark \end{aligned}$$Damit ist die Induktionsvoraussetzung erfüllt. Dann folgt der Induktionsschritt, d.h. der Übergang von \(n\) nach \(n+1\). Man beginnt mit einer der beiden Seiten der Ungleichung, setzt dort statt \(n\) das \(n+1\) ein, und versucht sie unter Annahme der Induktionsvoraussetzung in die andere Seite zu überführen. Ebenfalls mit dem Ausdruck \(n+1\) an Stelle von \(n\)$$\begin{aligned} (n+1)^2&= n^2 + 2n + 1 &&\left|\, n^2 \le 3^n \space \text{lt. Vorauss.} \right.\\ &\le 3^n + 2n + 1 && \left|\, 2n + 1 \lt n^2\right. \\&\lt 3^n + n^2 \\&\le 3^n + 3^n \\&\lt 3 \cdot 3^n \\ &= 3^{n+1} \quad\checkmark \end{aligned}$$Dass der Ausdruck \(2n+1 \lt n^2\) für \(n \ge 4\) ist, kannst Du noch mal per Induktion zeigen; ergibt sich aber auch schon rein anschaulich.
Oder Du beginnst beim Induktionsschritt mit dem größeren Ausdruck - also hier das \(3^{n+1}\) und formst es nach \((n+1)^2\) um:$$\begin{aligned} 3^{n+1} &= 3 \cdot 3^n &&\left|\, 3^n \ge n^2 \space \text{lt. Vorauss.} \right.\\ &\ge 3 \cdot n^2 \\&= n^2 + n^2 + n^2 &&\left|\, (n^2 \gt 2n) \land (n^2 \gt 1) \right. \\ &\gt n^2 + 2n + 1 \\&= (n+1)^2 \quad \checkmark\end{aligned}$$Beide Vorgehensweisen sind völlig gleichwertig. Falls Du bei einer nicht weiter kommst, so versuche die andere.
