# Prove or disprove: $\exists N_0 \in \mathbb N s.t. \forall n \geq N_0, 2^n > n^2$

This statement is true, for any $N_0 \geq 5$. My question lies in how to formally prove this. My professor is very strict about proof structure. This week, the homework mainly had to do with mathematical induction. Can this be proven using mathematical induction? If not, can someone lead me in the right direction on how to format this proof?

-
Here is an argument I find cute: $2^n=\sum_{i=0}^n\binom{n}i>\binom{n}1+\binom{n}2+\binom{n}{n-2}=n^2$, where the inequality follows from the fact that $2<n-2$, which is true for $n\ge 5$. – Andrés E. Caicedo Oct 9 '12 at 4:41

== For $\,n=5:\;\;\;2^5=32>25=5^2\,$

== Assume the claim's true (this is the inductive hypotheses =I.H.) for $\,n\geq 5\,$ ,then:

$$2^{n+1}=2\cdot 2^n\stackrel{\text{I.H.}}>2n^2>(n+1)^2$$

The last inequality on the right being true since

$$2n^2>(n+1)^2=n^2+2n+1\Longleftrightarrow n^2-2n-1>0\Longleftrightarrow$$

$$\Longleftrightarrow \left(n+(1+\sqrt 2)\right)\left(n+(1-\sqrt 2)\right)>0$$

-

Well, you concluded that $2^n > n^2$ holds for all $n \geq 5$.

Doesn't this really look like a standard mathematical induction statement?

$P(5)$ is trivial, and $P(n) \Rightarrow P(n+1)$ reduces to showing that $2n^2 >(n+1)^2$...

-
@Jean-Sébastien Nope, $2n^2$ is correct... That is what $P(n+1)$ reduces to once you use $P(n)$. – N. S. Oct 9 '12 at 3:27
yeah right, once using $P(n)$! time to sleep – Jean-Sébastien Oct 9 '12 at 4:38

Several inductive proofs have been given, so I will give a non-inductive one, just for fun. Perhaps your prof prefers a calculus based proof. $\log$ is order preserving, so $$2^n > n^2 \iff n\log(2) > 2\log(n) \iff \frac{\log(2)}{2} > \frac{\log(n)}{n}$$ Differentiating $f(x) = \frac{\log(x)}{x}$ gives $$f^{\prime}(x) = \frac{1-\log(x)}{x^2}$$ which is easily seen to have a maximum at $x = e$. Therefore it is strictly decreasing for $x\ge 3$. So as soon as you find some $N\ge 3$ which satisfies the inequality, then all $n>N$ will automatically satisfy the inequality as well. $N=5$ will work.

-