# limit question: $\lim\limits_{n\to \infty } \frac{n}{2^n}=0$

$$\lim_{n\to\infty}\frac n{2^n}=0.$$

I know how to prove it by using the trick, $2^n=(1+1)^n=1+n+\frac{n(n-1)}{2}+\text{...}$

But how to prove it without using this?

-
–  lab bhattacharjee Jun 30 '13 at 15:19
@HhyperGroups I wrote an answer that does not uses basic facts about limits only. –  Amr Jun 30 '13 at 15:43
@Amr welcome---!, SE a good place to manage these questions/answers, I just wanna see many related maths, though some of them I'm not able to understand completely and respond quickly. But we can review whenever the time seems ripe. –  HyperGroups Jun 30 '13 at 15:47
It is nice that you have 12 answers (up till now) to your question. –  Amr Jun 30 '13 at 16:34
@Amr Thanks, so let me accept your answer, of course so many good answers, then I should take time to enjoy them_ :) –  HyperGroups Jul 2 '13 at 5:23

Let's do something different!!

Note that the sequence $\{\frac{n}{2^n}\}_{n\geq 1}$ is decreasing ( easy to prove) and bounded from below by $0$, thus $\lim_{n\rightarrow \infty}\frac{n}{2^n}$ exists. Call it $L$.

$$L=\lim_{n\rightarrow \infty}\frac{n}{2^n}=\lim_{n\rightarrow \infty}\frac{(2n)}{2^{(2n)}}=\lim_{n\rightarrow\infty}(\frac{1}{2^{n-1}}\frac{n}{2^n})=[\lim_{n\rightarrow\infty}\frac{1}{2^{n-1}}][\lim_{n\rightarrow \infty}\frac{n}{2^n}]=(0)(L)=0$$

-
Nice idea used! –  André Nicolas Jun 30 '13 at 16:25
also, note that it's bounded below –  enthdegree Jun 30 '13 at 19:41
@enthdegree sure. I will include this. ${}{}{}$ –  Amr Jun 30 '13 at 20:22

Put

$$a_n:=\frac{\sqrt[n]n}2\implies a_n\xrightarrow [n\to\infty]{}\frac12\implies$$

If we take say $\,\epsilon=0.1\;$ then

$$\exists\,N_\epsilon\in\Bbb N\;\;s.t.\;\;n>N_\epsilon\implies \left|a_n-\frac12\right|<0.1\iff \frac25<a_n<\frac35\implies$$

$$\implies \left(\frac25\right)^n<a_n^n=\frac n{2^n}<\left(\frac35\right)^n$$

Now apply the squeeze theorem and get what you want

-
Hi I think you might like my answer as well ! –  Amr Jun 30 '13 at 15:56
Is there a proof of $\lim_{n\to\infty}\sqrt[n]{n}=1$ that doesn't in some form use (or instantly adapt to) the questioner's limit? It is, after all, instantly equivalent by taking logs to $\lim \frac{\log n}{n}=0$ and a quick substitution gives the OP's result... –  Steven Stadnicki Jun 30 '13 at 16:38
@Steven, look at my answer here math.stackexchange.com/questions/154163/… –  DonAntonio Jun 30 '13 at 16:47

Let's be original. Let $$\frac 1{1-x} = \sum_{k \ge 0} x^k,$$ which means the derivative of this series is also convergent with the same radius of convergence (namely, $1$) by Taylor's theorem : $$x \left( \frac 1{(1-x)^2} \right) = x \left( \sum_{k \ge 0} k x^{k-1} \right) = \sum_{k \ge 0} k x^k.$$ Letting $x = 1/2$, we see that the series $$\sum_{k \ge 0} \frac{k}{2^k}$$ is convergent, hence $\lim_{k \to \infty} \frac{k}{2^k} = 0$.

Hope that helps,

-
:nice approach .excellent $\large{+1}$ –  Maisam Hedyelloo Jun 30 '13 at 16:00
Yes. I had that in mind, too. But isn't it not sufficient to check $\lim_{n \rightarrow \infty} |a_{n+1} / a_n| = \frac 12$. That means $\sum_n a_n$ converges. –  André Jun 30 '13 at 16:05
@André : Of course, you can prove that the series converges in many different ways. You used D'Alembert's criterion, I used the fact that the geometric series converges (which can be proved by just computing the limit of partial sums for instance) and then Taylor's theorem. It's as you wish –  Patrick Da Silva Jun 30 '13 at 16:19

Here is a useful result

If $\lim_{n \to \infty}\frac{a_{n+1}}{a_n}=a$ and $|a|<1$, then $\lim_{n\to \infty} a_n = 0.$

-
+1 It looks like I popularized this question !!! –  Amr Jun 30 '13 at 16:13
It is nice to have different approaches to the solution. –  Mhenni Benghorbal Jun 30 '13 at 16:26
@Amr : This question is old, very old. –  Patrick Da Silva Jun 30 '13 at 16:49
@Amr : I mean that this question (and its variations) have been asked many times on this website. –  Patrick Da Silva Jun 30 '13 at 17:05
@Amr : I often don't, because the reason I'm on this website is to help people, and if you don't help people at the beginning of their math journey then you certainly won't do it at the end. –  Patrick Da Silva Jun 30 '13 at 17:15

For $n$ large, we have $2^n\ge n^2$. This can be easily proved by induction for $n\ge 4$. I would like to say then that $$\frac n{2^n}=\frac n{2^{\sqrt n}}\frac1{2^{n-\sqrt n}},$$ and the first fraction is bounded above by $1$, while the second approaches $0$.

Now, since we used induction, we cannot quite do this as $\sqrt n$ is not an integer. So we adjust, letting $t_n=\lfloor \sqrt n\rfloor$, and $s_n=t_n^2$, then $$\frac n{2^n}=\frac{s_n}{2^{t_n}}\frac{n/s_n}{2^{n-t_n}},$$ and the rest is clear, because $n/s_n<2$ and $n-t_n \to\infty$.

Just for fun, my favorite proof of $2^n\ge n^2$ for $n\ge4$, using the binomial theorem (which you have said you prefer to avoid): For $n=4$ we have equality, and if $n>4$ then $n-2>2$, so $$2^n=(1+1)^n> n+\binom n2+\binom n{n-2}=n^2.$$

(Note that similar arguments give that for any fixed $k$, we have $2^n>n^k$ for $n$ large enough.)

-
Hi I also gave another answer which avoids inequalities –  Amr Jun 30 '13 at 15:42

Here is the argument you did not want to see, in different language.

A set of $n$ elements has $2^n$ subsets. If $n\ge 2$, then it has $\binom{n}{2}$ two-element subsets.

It follows that for $n\ge 2$ we have $$2^n\ge \binom{n}{2}=\frac{n(n-1)}{2}.$$

Thus for $n\ge 2$ we have $$0\le \frac{n}{2^n}\le \frac{2}{n-1}.$$

-
+1 Ah This is one is nice as well. I like combinatorial arguments –  Amr Jun 30 '13 at 16:11
The question is easy , but its getting elegant answers which is a good thing for people who know the answer already. –  Amr Jun 30 '13 at 16:11

$2^n \geq n^2,\,n \geq 2$. Hence, $0 \leq \frac{n}{2^n} \leq \frac{n}{n^2} = \frac{1}{n}$. Apply the Cheeseburger (Sandwich, Squeeze) theorem.

-
I think the most common name for that theorem around here is "Squeeze Theorem" . In my university though we used to call it "the Sandwich theorem" –  DonAntonio Jun 30 '13 at 16:29
@DonAntonio Believe it or not, in France this is often called "théorème des gendarmes", which can approximately be translated by "cops theorem". –  1015 Jun 30 '13 at 23:42

As $\lim_{n\to\infty}\frac n{2^n}$ is of the form $\frac\infty\infty$

we can apply L'Hospital's Rule to get $$\lim_{n\to\infty}\frac n{2^n}=\lim_{n\to\infty}\frac1{2^n\ln 2}=0$$

-
ah, fine, a little advanced for this section of the text. So I haven't thought that. –  HyperGroups Jun 30 '13 at 15:17
Hi I gave an answer which avoids l'Hospital's rule –  Amr Jun 30 '13 at 15:42
Please disclose the mistake here –  lab bhattacharjee Jun 30 '13 at 15:58
Even though it is mentioned nowwhere, but I always have the feeling that $n$ stands for a discrete variable e.g. $n\in \mathbb{N}$. For a discrete variable differentiating doesn't makes sense so maybe you could add some details when this works or what happens when it doesn't work. –  Dominic Michaelis Jul 1 '13 at 5:12
@DominicMichaelis, why do you assume something not mentioned in the question? Why are you restricting the values of $n$ when the problem is valid for any real $n>0$ –  lab bhattacharjee Jul 1 '13 at 5:36

By AM/GM: $$\frac{2^{n}-1}{n}=\frac{2^0+2^1+\ldots +2^{n-1}}{n}\geq \left(2^{0+1+\ldots+(n-1)}\right)^{\frac1n}=2^{\frac{n-1}{2}}$$ Therefore, $$0<\frac{n}{2^n}<\frac{n}{2^n-1}\leq 2^{-\frac{n-1}{2}}\rightarrow 0\quad\text{as}\quad n\rightarrow\infty.$$

-
+1 ${}{}{}{}{}$ nice answer –  Amr Jun 30 '13 at 16:39

One more answer with another approach I've used several times in this site and I'm surprised nobody's yet used. Put

$$a_n:=\frac n{2^n}\implies \frac{a_{n+1}}{a_n}=\frac{n+1}{2^{n+1}}\frac{2^n}n=\frac12\frac{n+1}n\xrightarrow [n\to\infty]{}\frac12$$

and thus the quotient (D'Alembert's) test gives us that the positive series

$$\sum_{n=1}^\infty\frac n{2^n}\;\;\text{converges}\implies \lim_{n\to\infty}\frac n{2^n}=0$$

-
Essentially, isn't the same answer given by Mhenni Benghorbal? –  Seirios Jun 30 '13 at 16:38
Without mentioning series there, yes...but also pretty similar to some others, among them my first answer itself. –  DonAntonio Jun 30 '13 at 16:43

Using exponential and logarithm: $$\frac{n}{2^n}= \exp \underset{\to - \infty}{\underbrace{\left( n \left( \underset{\to 0}{\underbrace{\frac{\ln(n)}{n}}} - \ln(2) \right) \right)}} \underset{n \to + \infty}{\longrightarrow} 0$$

-
Excuse me, how could you show that the inner expression $\lim_{n\to\infty}n(\frac{\ln(n)}{n}-\ln2)=-\infty$? Is there a way of doing so without using the original statement? If so, would you like to show it? Thanks in advance. –  awllower Jul 2 '13 at 4:51
It follows from the classical limit $\frac{\ln(n)}{n} \to 0$, as I mentionned. Do you want more details about this limit? –  Seirios Jul 2 '13 at 7:09
Yes, if you mind not. Thanks. –  awllower Jul 2 '13 at 9:02
More generally, you have $\lim\limits_{x \to + \infty} \frac{\ln(x)}{x}=0$; taking $x=e^y$, the previous limit is equivalent to $\lim\limits_{y \to + \infty} ye^{-y}=0$ or $\lim\limits_{y \to + \infty} \frac{e^y}{y}=+ \infty$. To conclude, it is sufficient to notice that $e^y \geq \frac{y^2}{2}$ for $y \geq 0$; for an elementary proof, show that $f(y)=e^y- \frac{y^2}{2}$ is non-negative on $[0,+ \infty)$ by computing $f'$ and $f''$. –  Seirios Jul 2 '13 at 9:21
So you have to show that $f'\ge 0$ to conclude that the minimal point occurs at $y=0$, right? And this is equivalent with showing that $g(y)=e^y-y$ is non-negative. Since $g$ is convex, the maximum principle implies that the extreme values occur at boundary points, hence its non-negativity. Is this argument right? Or is there some more elementary method? Thanks. –  awllower Jul 2 '13 at 9:31