Prove $3^n > n^2$ by induction

Prove that $$3^n > n^2$$

I am using induction and I understand that when $n=1$ it is true. The induction hypothesis is when $n=k$ so $3^k>k^2$. So for the induction step we have $n=k+1$ so $3^{k+1} > (k+1)^2$ which is equal to $3\cdot3^k > k^2+2k+1$. I know you multiple both sides of the induction hypothesis by $3$ but I'm not sure what to do next.

Solution 1:

Let's leave aside the base step, for the moment.

Suppose the inequality holds for $n=k$; then $$ 3^{k+1}=3\cdot 3^k>3k^2=k^2+2k+1+2k^2-2k-1=(k+1)^2+(2k^2-2k-1) $$ The induction hypothesis has been applied at the first $>$ sign.

We have $2k^2-2k-1>0$ as soon as $k\ge2$. Indeed, $2x^2-2x-1<0$ if and only if $(1-\sqrt{3})/2<x<(1+\sqrt{3})/2$ and $1<(1+\sqrt{3})/2<2$.

Here the base step is $n=2$, not $n=1$, but of course the inequality holds also for $n=1$.

Solution 2:

$3^{n + 1} = 3 * 3^n > 3 n^2 > (n + 1)^2$ for sufficiently large $n$. The hypothesis that $3^n > n^2$ is used for the first inequality, and you can probably figure out what "sufficiently large $n$" is for the last step.

The $3n^2 > (n + 1)^2$ inequality might seem suspicious. One way to see that it will be valid for sufficiently large $n$ is to consider the order of growth of both sides of the inequality. Both sides are quadratic and in particular, for sufficiently large $n$, the $n^2$ term of $(n + 1)^2 = n^2 + 2n + 1$ will "dominate" the other terms. At that point we'll have $(n + 1)^2 = n^2 + 2n + 1\approx n^2 < 3n^2$, but maybe that's a little too hand wavy right now. Another way to see it is to note that $3n^2 > (n + 1)^2$ is equivalent to $n^2 - 2n - 1 > 0$:

\begin{align} 3n^2 &> (n + 1)^2\\ 3n^2 - (n + 1)^2 &> 0\\ 3n^2 - 2n^2 - 2n - 1 &> 0\\ n^2 - 2n - 1 &> 0 \end{align}

and you can solve $n^2 - 2n - 1 > 0$ using the quadratic equation. You'll find that $n > \frac{1}{2}(1+\sqrt{3})$ (or $n < \frac{1}{2}(1-\sqrt{3})$, but the negative solution isn't relevant here). Since $\frac{1}{2}(1+\sqrt{3})\approx 1.366<2$ the argument that uses $3n^2>(n+1)^2$ applies for $n = 2, 3,$ etc. If instead we had found that "sufficiently large $n$" meant $n > N \geq 2$ then we would have had to check additional base cases, $n = 2, 3, \ldots, N$ in order to complete the proof.

As an aside, I get the impression that you are thinking of proof by induction as a kind of mechanical process: "The induction hypothesis is when $n=k$", "I know you multiply both sides of the induction hypothesis by $3$", etc. It doesn't have to be so mechanical. For example, notice that "$k$" doesn't even appear in the steps above. This isn't meant as a criticism, just something to be aware of as you develop your skills.

Solution 3:

You start with knowing that $3^k > k^2$ and you prove that if you know that then you prove that $3^{k+1} > (k+1)^2$.

One straightforward and Doy! way is to note:

$3^k > k^2$

$3^k + 3^k + 3^k> k^2 + k^2+k^2$.

Since $k \ge 2$ then $k^2 \ge 2k$ and as $k \ge 2$ then $k^2 > 1$

So

$3^k + 3^k + 3^k > k^2 + 2k + 1$

$3^{k+1} = 3*3^k > (k+1)^2$.