Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

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

5 Answers 5

up vote 3 down vote accepted

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.

share|improve this answer
    
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$.

share|improve this answer
    
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$.

share|improve this answer

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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