Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
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$. –  Andres Caicedo Oct 9 '12 at 4:41

3 Answers 3

up vote 0 down vote accepted

== 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$$

share|improve this answer

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$...

share|improve this answer
@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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.