3
$\begingroup$

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

  • 4
    Hint: $z_n - y_n = z_n(1 - \frac{y_n}{z_n})$2012-08-03

5 Answers 5

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

9

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

  • 0
    The inequality $2^n\ge 2n$ was also shown [here](http://math.stackexchange.com/questions/169859/prove-by-mathematical-induction-that-2n-2n-for-all-integer-n1).2012-08-03
5

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

3

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.

  • 0
    You're welcome. The $1/2$ argument above can save you some time when dealing with limits.2012-08-03
2

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