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

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

Answer 4

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

Answer 5

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,

Answer 6

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

Answer 7

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

Answer 8

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

Answer 9

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

Answer 10

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

Answer 11

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