Finding $n_0$ such that $2^{cn}>n^{2}\, \forall n\geq n_0$

38 Views Asked by At

Let $h(n) = n^{2}$, $c=1$ and $f(n)=2^{cn}$. find an integer $n_0$ such that $f(n) > h(n)\, \forall\,n\geq n_0$.

I know that $n_0=4$ and I can prove it using induction, but is there a method to find such $n_0$? I tried doing inequalities such as $2^n>n$ but I don't get the final inequality.

1

There are 1 best solutions below

0
On BEST ANSWER

Let $g(x)=f(x)-h(x)=2^{x}-x^2$. Then $g'(x)=\log(2) 2^{x}-2x$ and $g''(x)=\log(2)^2 2^{x}-2$. Hence $g''(x)=0$ iff $x=1-\frac{2\log(\log(2))}{\log(2)}$. Since $g''(x)$ vanishes at just one point then it is easy to check that $g''(x)>0$ iff $x>1-\frac{2\log(\log(2))}{\log(2)}$ and $g''(x)<0$ iff $x<1-\frac{2\log(\log(2))}{\log(2)}$. This proves that $g'(x)$ is increasing in $(1-\frac{2\log(\log(2))}{\log(2)},+\infty)$. Now, notice that $1-\frac{2\log(\log(2))}{\log(2)}=2.057\dots$, so, since $g'(4)>0$ and $g'(3)<0$ we have that $g$ is increasing in $(4,+\infty)$, but no in $(3,+\infty)$. This is the reason for choosing $n_0=4$. To finish the exercise notice that $g(4)=0$ and then $g(x)> 0$ for every $x\in(4,+\infty)$, so $f(x)>h(x)$ for every $x\in (4,+\infty)$.

A nice exercise is to see that $n_0$ is not only the smallest integer satisfying this, but the smallest real number.

Remark: I've just realized that your problem asks $f(n)>h(n)$ for $n\geq n_0$, in that case $n_0=5$. What I have done is $f(n)>h(n)$ for $n> n_0$. I guess that this is how your problem should be, otherwise $n_0$ wouldn't be equal $4$.