Proof by induction of inequality. For $n \geq 2, 3^n \gt 2^n+n^2$ I'm trying to understand proof by induction on inequalities.
One problem I have is:

Prove that for $n \geq 2$  $3^n \gt 2^n+n^2$

I can prove the base case as $n=2$:

$3^2 \gt 2^2+2^2$ 
$9 \gt 8$

What I don't understand is the inductive step. How do I show for some $k$ where $k \geq 2$, $3^{k+1} \gt 2^{k+1} + (k+1)^2$.
 A: Suppose $3^k > 2^k + k^2$ you have to show $3^{k+1} > 2^{k+1} + (k+1)^2$. From the inductive step, $3^{k+1} = 3\cdot 3^k > 3(2^k+k^2)= 2^{k+1}+2^k+k^2+2k^2>2^{k+1}+k^2+2k+1=2^{k+1}+(k+1)^2$. This is true because $2^k \ge 2k$, and $2k^2 > 1$. Thus by induction, we are done.
A: Having done the base step, you get to assume the statement is true for $k \in \Bbb N$, and you must prove, from this assumption, that it's also true for $k+1$.
Let's set up a little notation.  Define $a_k=3^k, b_k=2^k+k^2$.  Given that $a_k \gt b_k$, we need to prove that $a_{k+1} \gt b_{k+1}$.  We will accomplish this by showing that the sequence $(a_k)$ grows faster than the sequence $(b_k)$.
We know that $\dfrac{a_{k+1}}{a_k}=3$.  However, $\dfrac{2^{k+1}}{2^k}=2 \lt 3$, and $\dfrac{(k+1)^2}{k^2} =\left (1+ \dfrac 1k \right )^2 \lt 3$ for any $k \in \Bbb N$.  Thus, $\dfrac{b_{k+1}}{b_k} \lt 3$, so $a_k \gt b_k \Rightarrow a_{k+1} =3a_k \gt 3b_k \gt b_{k+1}$ and we have completed the inductive step, thus proving the result.
