For every integer $n \geq 1$, prove that $3^n \geq n^2$.

Question

It's been a while since I've done induction, and I feel like I'm missing something really simple. What I have is this:

Base Case: $n=1$ $$3^n \geq n^2 \implies 3 \geq 1$$

Inductive Hypothesis

For all integers $1 \leq n < n+1$: $$3^n \ge n^2$$

Inductive Step

$$3^{n+1} \geq \left( n+1\right) ^2 \implies 3\cdot 3^n \geq n^2+2n+2$$

This is as far as I got. Is it acceptable to say $2\cdot 3^n \geq 2n+2$ and then prove that? Or is there an easier way?

Answer 1

Sort of. I prefer to do it in a single chain of inequalities though.

---

Inductive Hypothesis: Assume that the desired inequality holds for all $n' \in \{1, \ldots, n\}$, where $n \geq 2$ (you'll need to do an extra base case for $n = 2$).

It remains to prove that the desired inequality holds for $n' = n + 1$. Indeed, observe that: \begin{align*} 3^{n+1} &= 3(3^n) \\ &\geq 3(n^2) &\text{by the inductive hypothesis}\\ &= n^2 + (n)n + (n)^2 \\ &\geq n^2 + (2)n + (n)^2 &\text{since }n \geq 2\\ &> n^2 + (2)n + (1)^2 &\text{since }n \geq 2 > 1\\ &= (n + 1)^2 \end{align*} as desired.

Answer 2

For $n>1$ we have $2n(n-1)\geq 1$, thus:

$3^n\geq n^2\rightarrow 3^{n+1}\geq 3n^2=n^2+2n^2$

According to the first line of the answer, $2n(n-1)\geq 1\rightarrow 2n^2\geq 2n+1$

So we can say:

$3^{n+1}\geq n^2+2n+1=(n+1)^2$

Hence the assumption is proved by induction

Answer 3

The claim is clear if $n=1$.

If $n\ge 2$, by the binomial theorem, we have $$ 3^n = (1+2)^n = 1 + 2\binom n1 + 2^2\binom n2 + \dots > 2\binom n1 + 2^2\binom n2 = 2n + 2n(n-1) = 2n^2 > n^2 $$