Proof that $n^2 < 2^n$

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$.

$$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!

If you want to use induction, I assume you have checked the base case $n = 5$. To do the inductive step, assume that the statement holds for some $k$: $k^2 < 2^k$, and then under this assumption, you want to check that the statement holds for $k+1$: $(k+1)^2 < 2^{k+1}$. Well,

$$ (k+1)^2 = k^2 + 2k + 1 < 2^k + 2k + 1 $$

by the inductive hypothesis. When is $2^k + k + 1 < 2^{k+1}$. Well,

$$\begin{align} 2^k + k + 1 < 2^{k+1} &\iff k+1 < 2^{k+1} - 2^k \\ &\iff k+1 < 2^k. \end{align}$$

It is sufficient to show that $k+1 < 2^k$ for all $k \geq 5$. One way to do this is by induction. You can easily show the base case $5 + 1 < 2^5$. Now, assume that it holds for some $j \geq 5$, and we want to show that it also holds for $j+1$. Thus, we want to show that if $j+1 < 2^j$, then $(j+1) + 1 < 2^{j+1}$. This follows almost immediately since

$$ (j+1) + 1 < 2^j + 1 < 2^j + 2^j = 2^{j+1} $$ You should note that the inequality $1 < 2^j$ is not true in general, but it is true for $j > 1$ (and in particular for $j \geq 5$). Thus, we have shown that $k+1 < 2^k$ for all $k \geq 5$, and this was precisely what we needed for the inductive step of the original proof.

This idea of breaking a problem down into subsequent steps (if we need to show this, it suffices to show that, etc) is very much like how mathematicians solve problems.

It should be noted that induction is probably not the easiest way to derive this inequality, but if we want to strictly use induction, then something like this proof (and the consequent proof of the statement $k+1 < 2^{k}$ for $k \geq 5$) is one way to go.

What I mean about the easiest proof: As it was noted above, we have $n^2 < 2^n$ if and only if $\frac{\log n}{n} < \frac{\log 2}{2}$. Now, $f(x) = \frac{\log(x)}{x} \implies f'(x) = \frac{1 - \log x}{x^2} < 0$ when $x > e$. Thus, the function is strictly decreasing for $x > e$. Coupled with the fact that $f(x) \to 0$ as $x \to \infty$, it then suffices to find the first integer $t$ such that $\frac{\log t}{t} < \frac{\log 2}{2}$. This happens to be $t = 5$.

Added: Thomas' hint is a much nicer than my own answer, as it requires only check the values for which $n^2 > 2n +1$ which can be done with basic algebra.