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
1  
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
add comment

3 Answers

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
add comment

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
1  
@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
add comment

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
add comment

Your Answer

 
discard

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.