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