How to Prove with Mathematical Induction $3^n > n^2$

Question

How do I prove that $3^n > n^2$ with mathematical induction? I thought I had the correct answer but my teacher says its wrong.

I let $n=1$ for the initial case and it works. I then assumed $n=k$ works and went onto the $n=k+1$ case, but after that it goes a little awry. Thanks in advance!

Answer 1

The base case is just noticing $3^1>1^2$.

The inductive step:

Suppose $3^n>n^2$ we want to prove $3^{n+1}=3^n+3^n+3^n>1+2n+n^2=(n+1)^2$

This follows from the following:

$3^n\geq 1$

$3^n\geq 2n$ (you may have a go at this with another induction)

$3^n> n^2$ (inductive step)

Answer 2

We can show the inequality directly for $n=1$ and $n=2$.

Suppose $3^n>n^2$ as the inductive hypothesis.

For $n \geq 2$, $2.n^2 > 2n + 1$. Can you see why?

Then $3^{n+1} = 3.3^n > 3.n^2 = n^2 + 2.n^2 > n^2+2n+1 = (n+1)^2$.

The first inequality is via the inductive hypothesis, and the second inequality is via the inequality above.

Answer 3

You seem to have the principle correct, so the issue is one of application. There are probably simpler methods than this, but here is one way.

Show that it works for $n \in \{1, 2, 3\}$: $$ \begin{align} 3^1 = 3 &> 1^2 = 1\quad \checkmark\\ 3^2 = 9 &> 2^2 = 4\quad \checkmark\\ 3^3 = 27 &> 3^2 = 9\quad \checkmark \end{align} $$

Now, let's assume $3^n > n^2$. We need to prove that $3^{n+1} > \left(n+1\right)^2$. $$ \begin{align} 3^{n+1} = 3 \times 3^n &= 3^n + 3^n + 3^n\quad&(1)\\ (n+1)^2 &= n^2 + 2n + 1\quad&(2)\\ \end{align} $$

Looking at how the columns line up on the right side of (1) and (2), we can show that all corresponding elements of the top row are greater than those in the bottom row. In the first column, the top row is larger than the bottom row, we assumed it as part of the inductive step. The second column is true as $n^2 > 2n$ for all $n > 2$. So if $3^n > n^2$ via the induction step, it is certainly greater than $2n$. This is why we proved the individual cases up to 3 above. If your teacher is strict, you may have to prove this as a lemma using induction as well. The last column is true for all $n > 0$, and we started our induction step at 3. QED.

Just to be complete, we can show $n^2 > 2n$ for $n \geq 3$. $$ 3^2 = 9 > 2\times 3 = 6\quad \checkmark $$ Assume $n^2 > 2n$. Show $(n+1)^2 > 2(n+1)$. $$ \begin{align} (n+1)^2 = &n^2 +& 2n + &1\\ 2(n+1) = &&2n + &2 \end{align} $$

The $2n$ cancels, and we have to show that $n^2 + 1 > 2$, or $n^2 > 1$, which is trivial for $n > 3$.

Answer 4

To get from $3^n$ to $3^{n+1}$ you multiply by $3$. To get from $n^2$ to $(n+1)^2$, you multiply by $(\frac {n+1} n)^2$. Clearly $(\frac {n+1} n)^2$ will eventually by strictly smaller than $3$, and therefore past that point, the inequality $3^n>n^2$, if it's ever true, will be true forever afterwards.

Now, $(\frac {n+1} n)^2=(1+\frac 1 n)^2$ is a decreasing sequence which tends towards $1$, and some computation shows that for $n=2$ it is already below $3$. So we just have to check $3^2>2^2$, which is indeed true.

Answer 5

I'll outline a more or less self-contained proof. However, it may be worth observing that your own problem follows as a trivial conclusion of proving that $3^n\geq n^3$ for all $n\geq 1$. Here is an answer to that problem if you want to check it out.

---

To prove that $3^n>n^2$ for all $n\geq 1$ using induction, it will be useful to use two base cases at the beginning (this has already been referenced in one or two previous comments). The reason for this will become clear at the end.

---

Let $S(n)$ denote the following for $n\geq 1$ where $n\in\mathbb{N}$: $$ S(n) : 3^n>n^2. $$

Base step ($n=1,2$): $S(1)$ says that $3^1=3>1=1^2$, and this is true. Now, $S(2)$ says that $3^2=9>4=2^2$, and this is also true.

Inductive step: Fix some $k\geq 2$ and assume that $S(k)$ is true where $$ S(k) : 3^k>k^2. $$ To be shown is that $S(k+1)$ follows where $$ S(k+1) : 3^{k+1} > (k+1)^2. $$ Beginning with the left-hand side of $S(k+1)$, \begin{align} 3^{k+1} &= 3\cdot 3^k\tag{by definition}\\[0.5em] &> 3\cdot k^2\tag{by $S(k)$, the ind. hyp.}\\[0.5em] &> k^2+2k+1\tag{since $k\geq 2$; see $(\dagger)$}\\[0.5em] &= (k+1)^2, \end{align} we end up at the right-hand of $S(k+1)$, completing the inductive step.

By mathematical induction, the statement $S(n)$ is true for all $n\geq 1$. $\blacksquare$

---

$(\dagger)$: When $k\geq 2$, how can we claim that $3k^2>k^2+2k+1$? Notice that $$ 3k^2>k^2+2k+1 \Longleftrightarrow 2k^2-2k-1 > 0 \Longleftrightarrow k(2k-2)-1>0, $$ and this is obviously true for $k\geq 2$, but it is not true when $k=1$, and this explains why we needed two base cases at the beginning.