# What is the limit $\lim\limits_{n \to \infty} \frac{n^{\sqrt{n}}}{2^n}$?

The question is rather:

Prove the following: $$\lim_{x \to \infty} \frac{x ^ {\sqrt x} }{ 2 ^ x} = 0.$$

I was thinking of using the Squeeze Theorem (might not be the right way to go), but finding an upper-bound function proved to be quite tricky.

-
It will probably help to write $$\frac{x^{\sqrt{x}}}{2^x}=\frac{e^{\ln(x)\sqrt{x}}}{e^{\ln(2)x}}=e^{\ln(x){ \sqrt{x} }-\ln(2)x},$$ then you just need to show that $\lim_{x\to\infty}\ln(x)\sqrt{x}-\ln(2)x=-\infty$ to show that the limit is 0. –  Zev Chonoles Sep 12 '11 at 1:29
Hint: $x^\sqrt{x}$ = $e^{log(x) \sqrt{x}}$, and $2^x = e^{log(2) x}$. So their ratio is... –  Dan Brumleve Sep 12 '11 at 1:30
If you want to use the squeeze theorem, note that the denominator is $(2^\sqrt{x})^\sqrt{x}$, so the fraction is $\displaystyle\left(\frac{x}{2^\sqrt{x}}\right)^\sqrt{x}$. –  Brian M. Scott Sep 12 '11 at 1:55
Thanks for the help I ended going Zev and Dan's way and I will post my solution in a couple of hours. The other ways suggested are very interesting avenues of thought. –  William Sep 12 '11 at 2:12

For a 'more' elementary proof (which does not involve $e$ or $\log$),

Hint:

Prove using induction that for any $k \gt 7$, we have that

$$2^{k-1} \gt (k+1)^2$$

Try using this with your squeeze theorem idea.

For completeness:

Let $k = \lfloor \sqrt{n} \rfloor$. Using the above we have that, for all $n \gt 100$,

$$2^{\sqrt{n} - 1} \gt 2^{k-1} \gt (k+1)^2 \gt n$$

Raising to $\sqrt{n}^{th}$ power we get

$$2^{n - \sqrt{n}} \gt n^{\sqrt{n}}$$ and so

$$2^{-\sqrt{n}} \gt \frac{n^{\sqrt{n}}}{2^n}$$

-
+1 Nice hint in retrospect, but I could understand it only after seeing Brian's comment. :-) –  Srivatsan Sep 12 '11 at 2:01
Made it the answer even though it'a bit longer and complex since it's a refreshing perspective on the problem. –  William Sep 14 '11 at 13:07

Thanks Zev and Dan, I was on this trail. My answer goes like this:

I compare the rate of change of both functions (1) $\ln(x){ \sqrt{x} }$ and (2) ${\ln(2)}x$ by taking their derivatives and evaluating them as x goes to infinity :

(1) $$\lim_{x \to \infty} \frac{1}{\sqrt x} + {1/2}\frac{\ln {x}}{\sqrt x} = 0$$

Tip: use L'Hôpital's rule if you were unsure about the 2nd quotient.

(2) $$\lim_{x \to \infty} \ln {2} = \ln {2}$$

So (2) has a greater growth than (1) for x going to infinity so
$$\lim_{x \to \infty}\frac{x^{\sqrt{x}}}{2^x}=\frac{e^{\ln(x)\sqrt{x}}}{e^{\ln(2)x}}=e^{\ln(x){ \sqrt{x} }-\ln(2)x} = 0$$

-
Did you try it the way I suggested? It's easier, reducing it to the limit of $\rm\ X^2/{\it e}^{X}\$ as $\rm\:X\:\to\:\infty\:.$ –  Bill Dubuque Sep 13 '11 at 19:37

HINT $\rm\displaystyle\quad \dfrac{X^{\sqrt X}}{2^X}\ =\ \bigg(\dfrac{Z^2}{{\it e}^{\:c\:Z}}\bigg)^{\!\!Z} =:\ F(Z)^Z,\quad \begin{array}* Z\: =\: \sqrt{X}\\ \rm c\: =\: \ln\:2\end{array}\ \$ and $\displaystyle\rm\ \lim_{Z\:\to\:\infty}\ F(Z)\: = 0\$ by l'Hopital.

-

Let's take n= m^2 and get $\lim\limits_{m \to \infty} \frac{m^{2m}}{2^{m^2}}$. By ratio test we have that:

$$R=\lim\limits_{m \to \infty} \frac{(m+1)^{2m+2}}{2^{(m+1)^2}}\cdot\frac{2^{m^2}}{m^{2m}} =\lim\limits_{m \to \infty}\frac{e^2 (m+1)^2}{2^{2m+1}}=0.$$

Q.E.D.

-