# Proving $0$ is the limit of $\frac{n}{2^n-1}$ from definition alone

The question was:

Guess the limit of the series, and prove your guess from the definition of limits (without any of the theorems thought in class).

I guessed that the limit is $0$, and then looking at the definition of a limit I have: $\forall\epsilon>0\:\exists n_{0}>0\:\forall n>n_{0},\left|a_{n}-0\right|<\epsilon$

This means that I need to find $n_0$ such that for all $n>n_0$, $\frac{n_0}{2^{n_0}-1}<\epsilon$. But since I already prove that the sequence is decreasing, it's enough to find such $n_0$. But... that's where I'm stuck...

-

$$2^n = e^{n\log2 } = 1 + n \log 2 + \dfrac{n^2 \log^2(2)}2 + \cdots \geq 1 + \dfrac{n^2 \log^2(2)}2$$ Hence, we get that $$2^n - 1 \geq \dfrac{n^2 \log^2(2)}2$$ Hence, $$\dfrac{n}{2^n-1} \leq \dfrac{2n}{n^2 (\log 2)^2} = \dfrac{2}{n (\log 2)^2}$$ Now choose $N = \left \lceil \dfrac{2}{\epsilon (\log 2)^2} \right \rceil$. Then we have that for $n \geq N$ $$\dfrac{n}{2^n-1} \leq \dfrac{2}{n (\log 2)^2} < \epsilon$$

EDIT

If you are not comfortable with $\log$, then here is another way out. Prove that $$2^n \geq 1 + \dfrac{n^2}3$$ using induction. Hence, we now have that $$\dfrac{n}{2^n-1} \leq \dfrac3n$$ Now given $\epsilon > 0$ choose $N = \left \lceil \dfrac3 \epsilon\right \rceil$. Hence, for all $n > N$, we have that $$\dfrac{n}{2^n-1} \leq \dfrac3n < \epsilon$$

-
Both answers say to use logs, but as of now we never had to use stuff that wasn't thought (or at least shown) in the course apart from basic algebra. Do you think logs enter this definition? Since I most definitly remeber nothing about them from high school... – Nescio Nov 20 '12 at 23:22
A logarithm is (probably) required if you intend to express $n_0$ in terms of $\epsilon$. – alex.jordan Nov 20 '12 at 23:23
Well, the second way is pretty similar to Pambos's idea, but I really don't feel comfortable with logs. Is it something you expect I'd be introduced to or should I make an effort learn it on my own? – Nescio Nov 21 '12 at 11:31

Hint:

Use induction to prove that $2^n-1>n^2 \ \forall n \geq 5$.

Conclude that $\dfrac{n}{2^n-1}<\dfrac{1}{n} \ \forall n \geq5$.

Now it should be easy. For $\epsilon>0$ if $n_0=\max{\{5,\lceil\frac{1}{\epsilon}\rceil+1\}}$ then $\dfrac{n}{2^n-1}<\epsilon \ \ \forall n \geq n_0$.

-

It all comes down to showing that $2^n-1$ is "big" compared to $n$. This is the intuition that led you to decide that the limit is $0$. But we need to fill in some details.

We can do it by using the Binomial Theorem. Imagine expanding $(1+1)^n$, where $n\ge 2$. The first three terms in the expansion are $1$, $n$, and $\dfrac{n(n-1)}{2}$. It follows that if $n\ge 2$, $$2^n \gt \frac{n(n-1)}{2}.$$ Thus for $n\ge 2$, the $n$-th term of your sequence is $\le \dfrac{2}{n-1}$. Now it should not be difficult, given $\epsilon$, to find an $n_0$ that works.

-

Hints:

• $n<1.5^{n}$
• $2^{n}-1>2^{n-1}$
• Use $\log_{\text{something}}(\phantom{x})$
-