Proof that $n^2 < 2^n$

Solution 1:

Hint only: For $n \geq 3$ you have $n^2 > 2n + 1$ (this should not be hard to see) so if $n^2 < 2^n$ then consider $$ 2^{n+1} = 2\cdot2^n > 2n^2 > n^2 + 2n+1 = (n+1)^2. $$ Now this means that the induction step "works" when ever $n\geq 3$. However to start the induction you need something greater than three. By trial an error you can find the smallest $n(\geq0)$ such that $n^2 < 2^n$.

Solution 2:

$$n^2<2^n\Longleftrightarrow 2\log n<n\log 2\Longleftrightarrow\frac{\log n}{n}<\frac{\log 2}{2}$$

But we know that $\,\displaystyle{\frac{\log n}{n}\xrightarrow[n\to\infty]{}0}\,$ , so the above inequality's definitely true from one definite index $\,n\,$ and on...but not for all the naturals!