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