Prove by induction for every integer$\; n\ge 5$, $2^n\gt n^2$.

Question

Prove by induction for every integer$ \;n\ge 5$, $2^n\gt n^2$.

My try:

$$p(n):\;2^n>n^2$$ verify $P(5)$ $$ p(5):\;2^5>5^2 = 32 > 25 $$

Of course the trick is in the induction step and that's where I always get stuck. Any tips to proceed ?

Answer 1

The induction hypothesis is $2^n>n^2$ and now you want to prove it for $n+1$. If you start from your hypothesis : $$2^n>n^2 \implies 2\cdot2^n>2n^2 \implies2^{n+1}>n^2+n^2$$ but $n^2>2n+1$ for $5\leq n$ (your can also prove it with new induction but its obvious). So you can replace one $n^2$ in the inequality: $$2^{n+1}>n^2+2n+1\implies 2^{n+1}>(n+1)^2$$ And you prove it for $n+1$.

Answer 2

1. check for initial case :

n = 5

2^5 > 5^2 (32 > 25) great, that holds

2. assume P(n) and prov P(n+1) : 2^n > n^2 ==> 2^(n+1) > (n+1)^2

let's start with :

2^n > n^2 ==> 2*2^n > 2*n^2 (multiplying by 2)
          ==> 2^(n+1) > 2*n^2 great

Now we use the rule of A>B and B>C ==> A>C

A: 2^(n+1) B: 2*n^2 C: (n+1)^2

So we are left to only prove B>C to finish, let's do that :

lets assume:

2*n^2 > (n+1)^2 ==>  2*n^2 > n^2 + 2n + 1

            ==>  n^2 - 2n > 1

            ==> which can be easily proved for n>=5

And you're done

Answer 3

$2^n>n^2$

---

Prove for $n=5$, you have done this

---

Assume true for $n=k$

$2^k>k^2$

---

Then for $n=k+1$

$2^{k+1}>(k+1)^2$

$2(2^k)>k^2+2k+1$

Since you know $2^k>k^2\implies2(2^k)>2(k^2)$

It is sufficient for us to show that:

$2(k^2)>k^2+2k+1$

Because if we can prove this^^ We know that since $2(2^k)>2(k^2)$ Then definitely $2(2^k)>k^2+2k+1$

Ok now:

$2(k^2)>k^2+2k+1$

$k^2>2k+1$ Which is true for $n\geq5$

Therefore it's true for $n=k+1$

Proof Completed