Proof by induction of inequality. For $n \geq 2, 3^n \gt 2^n+n^2$

Question

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

Answer 1

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.

Answer 2

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.