8
$\begingroup$

$$ \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?

$\endgroup$
5
  • $\begingroup$ Related : math.stackexchange.com/questions/197522/… and math.stackexchange.com/questions/173061/… $\endgroup$ Jun 30, 2013 at 15:19
  • $\begingroup$ @HhyperGroups I wrote an answer that does not uses basic facts about limits only. $\endgroup$
    – Amr
    Jun 30, 2013 at 15:43
  • $\begingroup$ @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. $\endgroup$ Jun 30, 2013 at 15:47
  • 1
    $\begingroup$ It is nice that you have 12 answers (up till now) to your question. $\endgroup$
    – Amr
    Jun 30, 2013 at 16:34
  • $\begingroup$ @Amr Thanks, so let me accept your answer, of course so many good answers, then I should take time to enjoy them_ :) $\endgroup$ Jul 2, 2013 at 5:23

11 Answers 11

32
$\begingroup$

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

$\endgroup$
3
  • 1
    $\begingroup$ Nice idea used! $\endgroup$ Jun 30, 2013 at 16:25
  • $\begingroup$ also, note that it's bounded below $\endgroup$ Jun 30, 2013 at 19:41
  • $\begingroup$ @enthdegree sure. I will include this. ${}{}{}$ $\endgroup$
    – Amr
    Jun 30, 2013 at 20:22
13
$\begingroup$

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

$\endgroup$
5
  • $\begingroup$ Hi I think you might like my answer as well ! $\endgroup$
    – Amr
    Jun 30, 2013 at 15:56
  • $\begingroup$ 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... $\endgroup$ Jun 30, 2013 at 16:38
  • 1
    $\begingroup$ @Steven, look at my answer here math.stackexchange.com/questions/154163/… $\endgroup$
    – DonAntonio
    Jun 30, 2013 at 16:47
  • $\begingroup$ @DonAntonio Why didn't you use your very nice trick which I've learned from you of defining $a_n=\frac{n}{2^n}$ then, $\lim_{n \rightarrow \infty} \frac{a_{n+1}}{a_n}=\frac{1}{2} < 1$ so by ratio test the series converges, i.e $a_n \rightarrow 0$ $\endgroup$
    – harlem
    Mar 31, 2018 at 22:16
  • 1
    $\begingroup$ @harlem This was almost 5 years ago...yet there is another answer by me in then ext answers...maybe there. $\endgroup$
    – DonAntonio
    Mar 31, 2018 at 22:28
10
$\begingroup$

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,

$\endgroup$
3
  • $\begingroup$ :nice approach .excellent $\large{+1}$ $\endgroup$
    – M.H
    Jun 30, 2013 at 16:00
  • 2
    $\begingroup$ 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. $\endgroup$
    – user42761
    Jun 30, 2013 at 16:05
  • $\begingroup$ @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 $\endgroup$ Jun 30, 2013 at 16:19
8
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ It is nice to have different approaches to the solution. $\endgroup$ Jun 30, 2013 at 16:26
  • $\begingroup$ I agree ${}{}{}$ $\endgroup$
    – Amr
    Jun 30, 2013 at 16:28
  • 1
    $\begingroup$ @Amr : This question is old, very old. $\endgroup$ Jun 30, 2013 at 16:49
  • 1
    $\begingroup$ @Amr : I mean that this question (and its variations) have been asked many times on this website. $\endgroup$ Jun 30, 2013 at 17:05
  • 2
    $\begingroup$ @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. $\endgroup$ Jun 30, 2013 at 17:15
6
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ +1 Ah This is one is nice as well. I like combinatorial arguments $\endgroup$
    – Amr
    Jun 30, 2013 at 16:11
  • $\begingroup$ The question is easy , but its getting elegant answers which is a good thing for people who know the answer already. $\endgroup$
    – Amr
    Jun 30, 2013 at 16:11
5
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Hi I also gave another answer which avoids inequalities $\endgroup$
    – Amr
    Jun 30, 2013 at 15:42
5
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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" $\endgroup$
    – DonAntonio
    Jun 30, 2013 at 16:29
  • 3
    $\begingroup$ @DonAntonio Believe it or not, in France this is often called "théorème des gendarmes", which can approximately be translated by "cops theorem". $\endgroup$
    – Julien
    Jun 30, 2013 at 23:42
3
$\begingroup$

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

$\endgroup$
9
  • $\begingroup$ ah, fine, a little advanced for this section of the text. So I haven't thought that. $\endgroup$ Jun 30, 2013 at 15:17
  • $\begingroup$ Hi I gave an answer which avoids l'Hospital's rule $\endgroup$
    – Amr
    Jun 30, 2013 at 15:42
  • $\begingroup$ Please disclose the mistake here $\endgroup$ Jun 30, 2013 at 15:58
  • $\begingroup$ 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. $\endgroup$ Jul 1, 2013 at 5:12
  • $\begingroup$ @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$ $\endgroup$ Jul 1, 2013 at 5:36
3
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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

$\endgroup$
2
  • 3
    $\begingroup$ Essentially, isn't the same answer given by Mhenni Benghorbal? $\endgroup$
    – Seirios
    Jun 30, 2013 at 16:38
  • 1
    $\begingroup$ Without mentioning series there, yes...but also pretty similar to some others, among them my first answer itself. $\endgroup$
    – DonAntonio
    Jun 30, 2013 at 16:43
2
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$
    – awllower
    Jul 2, 2013 at 4:51
  • $\begingroup$ It follows from the classical limit $\frac{\ln(n)}{n} \to 0$, as I mentionned. Do you want more details about this limit? $\endgroup$
    – Seirios
    Jul 2, 2013 at 7:09
  • $\begingroup$ Yes, if you mind not. Thanks. $\endgroup$
    – awllower
    Jul 2, 2013 at 9:02
  • $\begingroup$ 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''$. $\endgroup$
    – Seirios
    Jul 2, 2013 at 9:21
  • $\begingroup$ 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. $\endgroup$
    – awllower
    Jul 2, 2013 at 9:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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