# Checking for Validty (and a more elegant approach for: Proof by induction that $4n^2 \le 2^n$

To proof is $4n^2 \le2^n$ with induction for n $\ge$ 8

I have a solution but I'm not very happy with it.

As usual I started with the base case of P(8) which gives me:

256 $\le$ 256, which is correct.

So now I have my Induction hypothesis : $4n^2 \le2^n$

And my Induction assumption (I'm not sure what the correct English term for this one is):

$4(n+1)^2 \le2^{n+1}$

$2n^2 +4n + 2 \le 2^n$

Now my approach is to first proof that:

$4n < n^2$ and $2 < n^2$ (Well the second one doesn't really require a formal proof I think)

For $4n \le n^2$ I start another proof by induction:

$4(n+1) \le (n+1)^2$

$4n + 4 \le n^2 +2n + 1$

In the next step I insert $n^2$ for 4n because from my hypothesis I know 4n $\le$ $n^2$

$n^2 +4 \le n^2 + 2n + 1$
$3 \le 2n$

I can also show the last inequality to be true which makes me consider $4n \le n^2$ as true

Now going back to my initial inequality:

$2n^2 +4n + 2 \le 2^n$

I can now simply show that:

$2n^2 + 4n + 2 \le 2*n^2 + n^2 + n^2$

$2n^2 + 4n + 2 \le 4n^2$

and with my initial induction hypothesis im left with a true statement:

$4n^2 \le2^n$ Q.E.D

What I'm mainly not happy with is my proof for $4n < n^2$ I'm not sure if did that proof correctly, also it feels very unrefined. I'd be grateful, if someone could either point out a mistake or give me a hint on how to approach this entirely problem differently if necessary.

• $n^2>4n$ is simply, since we have $n\geq 8$, we can write $n^2=n\cdot n\geq 8\cdot n>4n$ Commented Oct 8, 2017 at 10:36
• $4n<n^2\Leftrightarrow 4<n$, which is true since $n\ge8$ Commented Oct 8, 2017 at 10:51

Why not $$4(n+1)^2=4n^2\left(1+\frac1n\right)^2\le 2^n\left(1+\frac1n\right)^2\le2^n\cdot2=2^{n+1},$$ since $\left(1+\frac1n\right)^2<2$ already for $n\ge3$?