# divergence of $(2^n-n)$

Can anyone give me a satisfactory proof that the real sequence $(x_n)$ defined by $x_n = 2^n - n$ diverges to $+\infty$?

The heuristic reason is that $$\lim_{n\to\infty} \frac{n}{2^n} = 0,$$ but I can't seem to turn this into a rigorous proof.

More generally is there a theorem which says that $(z_n-y_n)$ diverges to $+\infty$ if $(y_n)$ and $(z_n)$ both diverge to $+\infty$ and $\lim_{n\to\infty} y_n/z_n = 0$?

-
Hint: $z_n - y_n = z_n(1 - \frac{y_n}{z_n})$ –  Alexander Thumm Aug 3 '12 at 10:26

As you pointed out $$\frac{n}{2^n} \underset{n \rightarrow \infty}{\longrightarrow} 0$$ Thus you can find $n_0 \geq 0$ such that $\forall n \geq n_0$ $$\frac{n}{2^n} \leq \frac{1}{2}$$ Thus $\forall n \geq n_0$, $$x_n = 2^n - n = 2^n \left( 1 - \frac{n}{2^n}\right) \geq 2^n \left( 1 - \frac{1}{2} \right) \geq 2^{n-1} \underset{n \rightarrow \infty}{\longrightarrow}+\infty$$ Thus $x_n \underset{n \rightarrow \infty}{\longrightarrow}+\infty$. The same exact proof can be applied to the generalized case you mentionned.

-
This is great, thanks. –  Mark Grant Aug 3 '12 at 10:51
You're welcome. The $1/2$ argument above can save you some time when dealing with limits. –  vanna Aug 3 '12 at 10:54

I claim that $2^n \ge 2n$ for every $n \ge 1$. Indeed, this is true for $n=1,2$, and if I assume $2^k \ge 2k$ for every $k=1,2,\ldots,n$, then $2^{n+1}=2\cdot2^n \ge 4n=2n+2n \ge 2n+2$. Hence $2^n-n \ge 2n-n=n$, so $\lim_n(2^n-n) \ge \lim_nn=\infty$.

-
The inequality $2^n\ge 2n$ was also shown here. –  Martin Sleziak Aug 3 '12 at 15:18

Write $2^n-n=2^{n-1}+2^{n-1}-n$, and show by induction that for $n\geq 2$, $2^{n-1}\geq n$.

-

Let $a_n = 2^n-n$.

Then

$$a_{n+1}-a_n = 2^{n+1}-2^n-1=2^n-1 \geq 1 \,.$$

It is trivial now to conclude than $a_n$ diverges. You can see either than $a_n$ is an strictly increasing sequence of natural numbers, and prove that any such sequence is divergent, or prove by telescoping that $$a_{n}= a_1+ \sum_{i=2}^n (a_i-a_{i-1}) \geq a_1+n-1 \,.$$

-

Here's a proof that follows from the binomial theorem:

$$2^n - n = \left(\sum\limits_{i=0}^n {n \choose i}\right) - n = 1+\sum\limits_{i=1}^n \left({n \choose i}-1\right)$$

Now, we clearly have ${n\choose i}\geq 1$ for each $i$, and, in fact ${n \choose 1} - 1 = n-1$. Therefore, $$2^n - n = 1 + (n-1) + \sum\limits_{i=2}^n \left({n \choose i}-1\right) \geq n$$

yielding that $2^n - n \rightarrow \infty$ as $n\rightarrow \infty$.

-