# Is my short induction proof correct?

1. Apr 3, 2017

### Eclair_de_XII

1. The problem statement, all variables and given/known data
"Prove: $∀n∈ℕ$, $3^n>n^2$

2. Relevant equations

3. The attempt at a solution
(1) We will prove that $3^n>n^2$ at $n=1$
$3=3^1>1=1^2$

(2) Now assume that $3^k>k^2$ for some $k>1$
(3) We will prove that $3^{k+1}>(k+1)^2$ or $3⋅3^k>k^2+2k+1$
Note that $k^2+2k^2+1=3k^2+1≥k^2+2k+1$, and as such, $3⋅3^k≥3k^2+3>3k^2+1≥k^2+2k+1$. So $3^{k+1}>3k^2+1≥(k+1)^2$.

I'm basically ambivalent as to whether to insert that extra term in the inequality: $3k^2+1$, not knowing whether it is equal to, less than, or greater than $3^{k+1}$. Can someone check my work, please? Thanks.

Last edited: Apr 3, 2017
2. Apr 3, 2017

### Staff: Mentor

The induction step boils down to showing that $3k^2 > (k + 1)^2$. It's easy enough to prove the equivalent statement $3k^2 - (k + 1)^2 > 0$.

3. Apr 3, 2017

### Eclair_de_XII

Let's see...

$3k^2-k^2-2k-1=2k^2-2k-1=2k(k-1)-1>0$ for $k>0$?

4. Apr 4, 2017

### Staff: Mentor

Almost. 2k(k - 1) - 1 > 0 for k > 1.
If k = 0, you have 0(-1) - 1 < 0, and if k = 1, you have 2(0) - 1 < 0.