1
$\begingroup$

I want to show the below statement:

$\lim_{n\rightarrow \infty} \dfrac{n+1}{2^{n\cdot n!}} = 0$

I can see that it is true, because the part $2^{n\cdot n!}$ will be greater than $n+1$, when $n\rightarrow \infty$. However I cannot accept this argument, because it isn't formal.

How can I argue for this in a formal way?

3 Answers 3

2

You want to show that for any $\epsilon>0$, there is some $N$ such that $n\geq N\implies \left|\frac{n+1}{2^{n\cdot n!}}\right|<\epsilon.$ In order to do so, we can use the fact that the real numbers are Archimendian, meaning that for any $\epsilon>0$ we have some natural number $m$ such that $m>1/\epsilon$, which implies $\epsilon>1/m$. Thus we need only show that for any natural number $m$, there is some $N$ such that $n\geq N\implies \left|\frac{n+1}{2^{n\cdot n!}}\right|<\frac1m$ which is equivalent to showing that for any natural number $m$, there is some $N$ such that $n\geq N\implies n+1<\frac{2^{n\cdot n!}}m.$ What if we try $N=m+2$? Well, we can use the fact that $n!> n$ and $2^n> n+1$ when $n>2$ to get that $n\geq m+2\implies \frac{2^{n\cdot n!}}m\geq 2^n>n+1$ thus we are done.

1

Note that your informal argument is wrong too. $(2n+1)$ is greater than $(n+1)$, but

$ \lim_{n \to +\infty} \frac{n+1}{2n+1} = \frac{1}{2} \neq 0 $

What you mean was not that $2^{n \cdot n!}$ is merely greater, but some superlative statement about how much greater it is.

Formally, you're trying to say that $2^{n \cdot n!} \in \omega(n+1)$, or conversely, $n+1 \in o(2^{n \cdot n!})$. These facts immediately imply the limit you seek. See wikipedia for what this means.

If you're familiar with asymptotics, then starting from the basic fact $n \in o(2^n)$, each step in the chain

$ n+1 \in o(2^{n+1}) = o(2^n) \subseteq o(2^{n \cdot n!}) $

is an easy argument to make.

If you're not familiar with asymptotics, you'll have to reproduce the theory to some extent. e.g. an inductive argument that $(2n+1) / 2^{2n+1} < 1/2^{n+1}$, by noting the numerator doesn't double when you increment $n$.

1

Further more, \[ \lim_{n \to \infty} \frac {n+1} {2^n} = 0 \] because when $n \ge 2$, \[ 2^n = (1+1)^n \ge \binom n 1 + \binom n 2 = \frac {n(n+1)} 2 \] and \[ \frac {n+1} {2^n} \le \frac{2}{n} \to 0 \] when $n \to \infty$.