Examples for limits – "Math for Non-Geeks"

Some important limits

The following limits are fundamental building bricks, which you can use to find the limits for a lot of other sequences. You should know them by heart - and have a figure in mind of what they look like and how they converge:

• $\underset{n\to \mathrm{\infty }}{lim}c=c$ for all $c\in ℝ$
• $\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}=0$
• $\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n^k}=0$ for all $k\in \mathbb{N}$
• $\underset{n\to \mathrm{\infty }}{lim}\frac{1}{\sqrt[k]{n}}=0$ for all $k\in \mathbb{N}$
• $\underset{n\to \mathrm{\infty }}{lim}{q}^n=0$ for all $q\in ℝ$ with $|q|<1$
• $\underset{n\to \mathrm{\infty }}{lim}\sqrt[n]{c}=1$ for all $c>0$
• $\underset{n\to \mathrm{\infty }}{lim}\sqrt[n]{n}=1$
• $\underset{n\to \mathrm{\infty }}{lim}\frac{n^k}{z^n}=0$ for all $k\in \mathbb{N}$ and $z\in ℝ$ with $|z|>1$
• $\underset{n\to \mathrm{\infty }}{lim}{n}^k{q}^n=0$ for all $k\in \mathbb{N}$ and $q\in ℝ$ with $|q|<1$
• $\underset{n\to \mathrm{\infty }}{lim}\frac{z^n}{n!}=0$ for all $z\in ℝ$ with $|z|>1$
• $\underset{n\to \mathrm{\infty }}{lim}\frac{n!}{n^n}=0$
• $\underset{n\to \mathrm{\infty }}{lim}{(1+\frac{1}{n})}^n=e$

Hint

In real analysis, it is helpful to have an intuition about how fast sequences grow. For instance, there is $\underset{n\to \mathrm{\infty }}{lim}\frac{n^k}{z^n}=0$, because the exponentially increasing magnitude $(|z{|}^n{)}_{n\in \mathbb{N}}$, with $|z|>1$, grows faster than the polynomially increasing $(n^k{)}_{n\in \mathbb{N}}$. An experienced mathematician will not try to compute $\underset{n\to \mathrm{\infty }}{lim}\frac{n^k}{z^n}$ but instead use the intuitive picture "exponential beats polynomial". Both the numerator and the denominator grow infinitely large, but the "denominator wins" in this process and the quotient tends to $0$.

There is actually an entire hierarchy of growth speeds. We express "$b_n$ grows faster than $a_n$" by writing $a_n\ll b_n$ and mathematically meaning $\underset{n\to \mathrm{\infty }}{lim}\frac{a_n}{b_n}=0$. For fixed $k\in \mathbb{N}$ and real $z>1$, the list of limits above then implies:

$1\ll n^k\ll z^n\ll n!\ll n^n$

Or intuitively, polynomial beats constant, exponential beats polynomial, factorial beats exponential and $n^n$ beats them all.

Constant sequences

Theorem (Limit of a constant sequence)

Every constant sequence converges to

$\underset{n\to \mathrm{\infty }}{lim}c=c$

Example (Limit of a constant sequence)

• $\underset{n\to \mathrm{\infty }}{lim}42=42$
• $\underset{n\to \mathrm{\infty }}{lim}-1=-1$

How to get to the proof? (Limit of a constant sequence)

The formal proof requires showing that $|a_n-c|<ϵ$ for any $ϵ>0$ and all $n\in \mathbb{N}$ . But this is rather simple, as $a_n=c$ , so $|c-c|=0$ and

$\underset{=0}{\underbrace{|a_n-c|}}<ϵ$

always holds. We do not even have to care about how to choose $N$ . For simplicity, we may just use $N=1$ . The proof now reads:

"Choose $N=1$. Let $n\in \mathbb{N}$ with $n\ge N=1$ be arbitrary. Then…"

This formulation can be simplified, since $n\ge 1$ just means that $n$ is a natural number:

"For all $n\in \mathbb{N}$ there is…"

Proof (Limit of a constant sequence)

Let $a_n=c$ be a constant sequence and $ϵ>0$ arbitrary. For all $n\in \mathbb{N}$ (and hence, almost all $n\in \mathbb{N}$) there is

$|a_n-c|=|c-c|=0<ϵ$

Harmonic sequence

Theorem (Limit of the Harmonic sequence)

There is $\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}=0$.

How to get to the proof? (Limit of the Harmonic sequence)

We have to establish the inequality $|\frac{1}{n}-0|<ϵ$ . First, let us get rid of the absolute value in $|\frac{1}{n}-0|$:

$|\frac{1}{n}-0|=\left|\frac{1}{n}\right|=\frac{1}{n}$

So we need to find some $n$, such that $\frac{1}{n}<ϵ$. Which $n$ satisfy this? Let us resolve the inequality for $n$:

$\begin{array}{ccc}& \frac{1}{n}& <ϵ\\ \iff & 1& <ϵ\cdot n\\ \iff & \frac{1}{ϵ}& <n\end{array}$

So there must be $n>\frac{1}{ϵ}$ , in order to fulfill $\frac{1}{n}<ϵ$.

Question: Which threshold $N$ will we choose for the later proof?

Just choose any $N\in \mathbb{N}$ with $N>\frac{1}{ϵ}$. If we consider any bigger number $n\ge N$, then also $n>\frac{1}{ϵ}$.

How do we know that such an $N$ exists? This will be considered to be obvious in an exam or a textbook. Nevertheless, it is useful to think about the exact reasoning at least once:

Question: Why does such an $N$ exists?

This follows by the Archimedean axiom. For all real numbers, $M$ , there is a larger natural number $N$ , i.e. $N>M$. We choose $M=\frac{1}{ϵ}$.

Proof (Limit of the Harmonic sequence)

Let $ϵ>0$ be arbitrary. We choose an $N\in \mathbb{N}$ with $N>\frac{1}{ϵ}$. The existence is provided by the Archimedean axiom. Let $n\ge N$ be arbitrary. Then

$\begin{array}{cc}|\frac{1}{n}-0|& =\left|\frac{1}{n}\right|=\frac{1}{n}\le \frac{1}{N}<ϵ\end{array}$

Inverse power sequence

Theorem

For all $k\in \mathbb{N}$ there is $\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n^k}=0$.

How to get to the proof?

The proof is quite similar to the harmonic sequence above (which is in fact just a special case for $k=1$). We start by simplifying $|\frac{1}{n^k}-0|$:

$|\frac{1}{n^k}-0|=\left|\frac{1}{n^k}\right|=\frac{1}{n^k}$

Now, resolve $\frac{1}{n^k}<ϵ$ for $n$:

$\begin{array}{ccc}& \frac{1}{n^k}& <ϵ\\ \iff & 1& <ϵ\cdot n^k\\ \iff & \frac{1}{ϵ}& <n^k\\ \iff & \sqrt[k]{\frac{1}{ϵ}}& <n\\ \iff & \frac{1}{\sqrt[k]{ϵ}}& <n\end{array}$ So we need to find an $N$ with $N>\frac{1}{\sqrt[k]{ϵ}}$ . This can be done by the Archimedean axiom.

Proof

Let $ϵ>0$ be arbitrary. Choose $N\in \mathbb{N}$ such that $N>\frac{1}{\sqrt[k]{ϵ}}$ . Existence is guaranteed by the Archimedean axiom. Let $n\ge N$ be arbitrary. Then,

$\begin{array}{ccc}& n& \ge N\\ & & \downarrow N>\frac{1}{\sqrt[k]{ϵ}}\\ \Rightarrow & n& >\frac{1}{\sqrt[k]{ϵ}}\\ \Rightarrow & n\cdot \sqrt[k]{ϵ}& >1\\ \Rightarrow & \sqrt[k]{ϵ}& >\frac{1}{n}\\ \Rightarrow & ϵ& >\frac{1}{n^k}\\ \Rightarrow & ϵ& >|\frac{1}{n^k}-0|\\ \Rightarrow & |\frac{1}{n^k}-0|& <ϵ\end{array}$

Inverse root sequence

Theorem

For all $k\in \mathbb{N}$ there is $\underset{n\to \mathrm{\infty }}{lim}\frac{1}{\sqrt[k]{n}}=0$.

How to get to the proof?

The proof is almost as above. We start by simplifying $|\frac{1}{\sqrt[k]{n}}-0|$:

$|\frac{1}{\sqrt[k]{n}}-0|=\left|\frac{1}{\sqrt[k]{n}}\right|=\frac{1}{\sqrt[k]{n}}$

Now, we resolve $\frac{1}{\sqrt[k]{n}}<ϵ$ for $n$:

$\begin{array}{ccc}& \frac{1}{\sqrt[k]{n}}& <ϵ\\ \iff & 1& <ϵ\cdot \sqrt[k]{n}\\ \iff & \frac{1}{ϵ}& <\sqrt[k]{n}\\ \iff & {\left(\frac{1}{ϵ}\right)}^k& <n\\ \iff & \frac{1}{{ϵ}^k}& <n\end{array}$

So we need to find an $N$ with $N>\frac{1}{{ϵ}^k}$ . This can be done by the Archimedean axiom:

Proof

Let $ϵ>0$ be arbitrary. Choose $N\in \mathbb{N}$ such that $N>\frac{1}{{ϵ}^k}$ . Existence is guaranteed by the Archimedean axiom. Hence,

$\begin{array}{ccc}& N& >\frac{1}{{ϵ}^k}\\ \Rightarrow & N\cdot {ϵ}^k& >1\\ \Rightarrow & {ϵ}^k& >\frac{1}{N}\\ \Rightarrow & ϵ& >\frac{1}{\sqrt[k]{N}}\end{array}$

Let now $n\in \mathbb{N}$ with $n\ge N$ be arbitrary. There is:

$\begin{array}{ccc}& N& \le n\\ \Rightarrow & \frac{1}{n}& \le \frac{1}{N}\\ \Rightarrow & \frac{1}{\sqrt[k]{n}}& \le \frac{1}{\sqrt[k]{N}}<ϵ\end{array}$

Geometric sequence

Theorem

For all $q\in ℝ$ with $|q|<1$ there is $\underset{n\to \mathrm{\infty }}{lim}{q}^n=0$ .

For $0<|q|<1$, the absolute values decrease exponentially to $0$, faster than any fixed inverse power of $n$. For $q=0$, all terms are $0$.

Example

• $\underset{n\to \mathrm{\infty }}{lim}{(-\frac{1}{2})}^n=0$
• $\underset{n\to \mathrm{\infty }}{lim}{\left(\frac{1}{\pi }\right)}^n=0$

How to get to the proof?

If $q=0$, all terms are $0$ and convergence is immediate. Otherwise, assume $0<|q|<1$. We start again by simplifying the absolute value in $|q^n-0|$:

$|q^n-0|=\left|q^n\right|=|q{|}^n$

Using the Bernoulli's inequality we can show:

"For each $0\le a<1$ and $ϵ>0$ there is an $N\in \mathbb{N}$ with $a^N<ϵ$."

We set $a=|q|$. Then, there must be an $N\in \mathbb{N}$ with $|q{|}^N<ϵ$, which is exactly what we need. For all greater $n\ge N$ there is also:

$|q{|}^n=\underset{\le 1}{\underbrace{|q{|}^{n-N}}}\cdot \underset{<ϵ}{\underbrace{|q{|}^N}}<ϵ$

Proof

Let $ϵ>0$ and $q\in ℝ$ with $|q|<1$ be arbitrary. If $q=0$, the claim is immediate. Otherwise, $0<|q|<1$. By Bernoulli's inequality, we obtain an $N\in \mathbb{N}$ with $|q{|}^N<ϵ$ . For all $n\ge N$, there is:

$\begin{array}{cc}|q^n-0|& =\left|q^n\right|=|q{|}^n=\underset{\le 1}{\underbrace{|q{|}^{n-N}}}\cdot \underset{<ϵ}{\underbrace{|q{|}^N}}<ϵ\end{array}$

Hint

We can also investigate convergence for $|q|\ge 1$ . This requires distinguishing 3 cases:

• $q=1:$ This is just a constant sequence $(q^n{)}_{n\in \mathbb{N}}=(1^n{)}_{n\in \mathbb{N}}=(1{)}_{n\in \mathbb{N}}$. Above, we have shown that $\underset{n\to \mathrm{\infty }}{lim}{q}^n=\underset{n\to \mathrm{\infty }}{lim}1=1$.
• $q=-1:$ Here, we get the alternating sequence $(q^n{)}_{n\in \mathbb{N}}={((-1{)}^n)}_{n\in \mathbb{N}}$. It "jumps" between $-1$ and $1$ and hence diverges. The mathematical proof is an exercise in the article "Exercises for convergence and divergence".
• $|q|>1:$ The sequence $(q^n{)}_{n\in \mathbb{N}}$ diverges, since it is unbounded. In the article „Unbounded sequences diverge“ we will show that even all unbounded sequences must diverge.

n-th root

Theorem (Limit of a sequence with the n-th root)

For all $c>0$ there is $\underset{n\to \mathrm{\infty }}{lim}\sqrt[n]{c}=1$.

How to get to the proof? (Limit of a sequence with the n-th root)

We need to establish an inequality like $|\sqrt[n]{c}-1|<ϵ$ . First, let us focus on the proof for $c\ge 1$. Then, $\sqrt[n]{c}\ge 1$ and we can leave out the absolute value:

Case 1: $c\ge 1$

In this case, $|\sqrt[n]{c}-1|=\sqrt[n]{c}-1$, and we need to show $\sqrt[n]{c}-1<ϵ$ for almost all $n\in \mathbb{N}$ . We resolve for $n$ :

$\begin{array}{ccc}& \sqrt[n]{c}-1& <ϵ\\ \iff & \sqrt[n]{c}& <1+ϵ\\ \iff & c& <(1+ϵ{)}^n\end{array}$

Does this inequality make sense? Since $ϵ>0$ there is $1+ϵ>1$. So ${((1+ϵ{)}^n)}_{n\in \mathbb{N}}$ is a geometric sequence getting arbitrarily large for increasing $n$. Hence, there must be an $n$, for which $(1+ϵ{)}^n$ is bigger than $c$ , which is equivalent to $\sqrt[n]{c}-1<ϵ$. More precisely, by an implication of Bernoulli's inequality, there is:

For each $p>1$ and $M\in ℝ$ there is an $n\in \mathbb{N}$, such that $p^n>M$ .

If we now set $p=1+ϵ$ and $M=c$ , we get the desired $N\in \mathbb{N}$ with $(1+ϵ{)}^N>c$. We only need to show $(1+ϵ{)}^n>c$ for all natural numbers $n\ge N$, which is done via

$(1+ϵ{)}^n=\underset{\ge 1}{\underbrace{(1+ϵ{)}^{n-N}}}\underset{>c}{\underbrace{(1+ϵ{)}^N}}>c$

Case 2: $c<1$

This is similar to the above case. We set $a=\frac{1}{c}$, such that $a>1$ . Then:

$\begin{array}{cc}|\sqrt[n]{c}-1|& =|\sqrt[n]{\frac{1}{a}}-1|\\ & =|\frac{1}{\sqrt[n]{a}}-1|\\ & =\left|\frac{1-\sqrt[n]{a}}{\sqrt[n]{a}}\right|\\ & =\left|\frac{1}{\sqrt[n]{a}}\right|\cdot |1-\sqrt[n]{a}|\\ & =\frac{1}{\sqrt[n]{a}}\cdot |\sqrt[n]{a}-1|\\ \end{array}$

This makes sense, because $|\sqrt[n]{a}-1|$ gets arbitrarily small ($a>1$). So we just need to estimate the term $\frac{1}{\sqrt[n]{a}}$ from above. There is $\begin{array}{ccc}& a& >1\\ \Rightarrow & \sqrt[n]{a}& >1\\ \Rightarrow & \frac{1}{\sqrt[n]{a}}& <1\end{array}$

So

$\frac{1}{\sqrt[n]{a}}\cdot |\sqrt[n]{a}-1|<|\sqrt[n]{a}-1|$

and by case 1, we already know that $|\sqrt[n]{a}-1|$ gets arbitrarily small.

Proof (Limit of a sequence with the n-th root)

Case 1: $c\ge 1$

Let $ϵ>0$ be arbitrary. We know that:

For all $p>1$ and all $M\in ℝ$ there is $n\in \mathbb{N}$, such that $p^n>M$ .

So there must be a natural number $N\in \mathbb{N}$ with $(1+ϵ{)}^N>c$. Let $n\ge N$ be arbitrary. Then,

$(1+ϵ{)}^n=\underset{\ge 1}{\underbrace{(1+ϵ{)}^{n-N}}}\underset{>c}{\underbrace{(1+ϵ{)}^N}}>c$

So

$\begin{array}{ccc}& c& <(1+ϵ{)}^n\\ \Rightarrow & \sqrt[n]{c}& <1+ϵ\\ \Rightarrow & \sqrt[n]{c}-1& <ϵ\\ \Rightarrow & |\sqrt[n]{c}-1|& <ϵ\end{array}$

Case 2: $c<1$

Let $ϵ>0$ be arbitrary. First, set $a=\frac{1}{c}$. Then, $a>1$ and by case 1, we know that there must be an $N\in \mathbb{N}$ with $|\sqrt[n]{a}-1|<ϵ$ for all $n\ge N$ . Let $n\ge N$ be arbitrary. Then,

$\begin{array}{ccc}& a& >1\\ \Rightarrow & \sqrt[n]{a}& >1\\ \Rightarrow & \frac{1}{\sqrt[n]{a}}& <1\end{array}$

So

$\begin{array}{cc}|\sqrt[n]{c}-1|& =|\sqrt[n]{\frac{1}{a}}-1|\\ & =|\frac{1}{\sqrt[n]{a}}-1|\\ & =\left|\frac{1-\sqrt[n]{a}}{\sqrt[n]{a}}\right|\\ & =\left|\frac{1}{\sqrt[n]{a}}\right|\cdot |1-\sqrt[n]{a}|\\ & =\frac{1}{\sqrt[n]{a}}\cdot |\sqrt[n]{a}-1|\\ & <|\sqrt[n]{a}-1|\\ & <ϵ\\ \end{array}$

n-th root of n

Theorem (Limit n-th root of n)

There is $\underset{n\to \mathrm{\infty }}{lim}\sqrt[n]{n}=1$.

How to get to the proof? (Limit n-th root of n)

We need to establish $|\sqrt[n]{n}-1|<ϵ$. Let us try to resolve for $n$ :

$\begin{array}{ccc}& |\sqrt[n]{n}-1|& <ϵ\\ & & \downarrow \sqrt[n]{n}\ge 1\\ \iff & \sqrt[n]{n}-1& <ϵ\\ \iff & \sqrt[n]{n}& <1+ϵ\\ \iff & n& <(1+ϵ{)}^n\end{array}$

$(1+ϵ{)}^n$ and $n$ both grow to $\mathrm{\infty }$. So, the only way to success is to show that $(1+ϵ{)}^n$ eventually gets bigger than $n$. Intuitively, the reason is that "exponentials beat polynomials". Mathematically, we can show this by expanding $(1+ϵ{)}^n$ using the binomial theorem:

$(1+ϵ{)}^n=\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){ϵ}^k=1+nϵ+\sum _{k=2}^n(\genfrac{}{}{0ex}{}{n}{k}){ϵ}^k(n\ge 2)$

Each term in this sum is $\ge 0$. So, if we can show that $n$ gets smaller than any part of the sum $\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){ϵ}^k$ , we know that $n$ is smaller than the entire sum $\sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){ϵ}^k=(1+ϵ{)}^n$ . For $n\ge 2$, we choose the terms $1$ and $\frac{n(n-1)}{2}{ϵ}^2$. Together they suffice to establish

$n<1+\frac{n(n-1)}{2}{ϵ}^2$

which in turn is smaller than

$1+\frac{n(n-1)}{2}{ϵ}^2\le \sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){ϵ}^k=(1+ϵ{)}^n$

so

$n<(1+ϵ{)}^n$

What is a suitable $n$ to get $n<1+\frac{n(n-1)}{2}{ϵ}^2$? For $n\ge 2$, let us resolve for $n$:

$\begin{array}{ccc}& n& <1+\frac{n(n-1)}{2}{ϵ}^2\\ \iff & n-1& <\frac{n(n-1)}{2}{ϵ}^2\\ \iff & 1& <\frac{n}{2}{ϵ}^2\\ \iff & 2& <n{ϵ}^2\\ \iff & \frac{2}{{ϵ}^2}& <n\end{array}$

By the Archimedean axiom, there is an $N\in \mathbb{N}$ with $N>max\{1,\frac{2}{{ϵ}^2}\}$, so that $n\ge 2$ and $\frac{2}{{ϵ}^2}<n$ for all $n\ge N$ .

Proof (Limit n-th root of n)

Let $ϵ>0$ be arbitrary. We choose $N\in \mathbb{N}$ by the Archimedean axiom, such that $N>max\{1,\frac{2}{{ϵ}^2}\}$ . Let $n\ge N$ be arbitrary. Then,

$\begin{array}{ccc}& \frac{2}{{ϵ}^2}& <n\\ \Rightarrow & 2& <n{ϵ}^2\\ \Rightarrow & 1& <\frac{n}{2}{ϵ}^2\\ \Rightarrow & n-1& <\frac{n(n-1)}{2}{ϵ}^2\\ \Rightarrow & n& <1+\frac{n(n-1)}{2}{ϵ}^2\\ & & \downarrow 1+\frac{n(n-1)}{2}{ϵ}^2\le \sum _{k=0}^n(\genfrac{}{}{0ex}{}{n}{k}){ϵ}^k=(1+ϵ{)}^n\\ \Rightarrow & n& <(1+ϵ{)}^n\\ \Rightarrow & \sqrt[n]{n}& <1+ϵ\\ \Rightarrow & \sqrt[n]{n}-1& <ϵ\\ & & \downarrow \sqrt[n]{n}\ge 1\\ \Rightarrow & |\sqrt[n]{n}-1|& <ϵ\end{array}$

Ratio - power sequence / geometric sequence

In simple words: "exponential beats polynomial":

Theorem

Let $k\in \mathbb{N}$ be arbitrary and $z$ a real number with $|z|>1$. Then, $\underset{n\to \mathrm{\infty }}{lim}\frac{n^k}{z^n}=0$.

How to get to the proof?

This proof will be quite complicated. But it includes some useful tricks, which may help you with other proofs as well. One of those tricks is writing $|z|>1$ as $1+x$ with $x=|z|-1>0$ . The term $(1+x{)}^n$ can be multiplied out using the binomial theorem:

$\begin{array}{cc}\left|\frac{n^k}{z^n}\right|& =\frac{\left|n^k\right|}{\left|z^n\right|}\\ & =\frac{n^k}{|z{|}^n}\\ & =\frac{n^k}{(1+x{)}^n}\\ & \downarrow \text{binomial theorem}\\ & =\frac{n^k}{\sum _{l=0}^n(\genfrac{}{}{0ex}{}{n}{l})x^l}\end{array}$

The sum in the denominator is what makes this fraction complicated. It would be nice to have a more simple expression. We can achieve this by making the denominator smaller: all terms in $(\genfrac{}{}{0ex}{}{n}{l})x^l$ are positive. So if we leave summands out, we simplify the denominator and make it smaller. The entire fraction then grows. And if an enlarged fraction still converges to 0, the original one will do so, as well. The interesting question is, which terms to leave out.

Since the numerator includes $n^k$ , it may be useful to replace the denominator by some term $c_k\cdot n^{k+1}$ with $c_k\in {ℝ}^{+}$ not depending on $n$ . This way, we can make sure that the fraction still converges to 0 after the simplification. We will only keep this one term with $l=k+1$ , so $(\genfrac{}{}{0ex}{}{n}{k+1})x^{k+1}$. All other terms are left out for simplicity. Multiplying out yields $(\genfrac{}{}{0ex}{}{n}{k+1})=\frac{n(n-1)\cdot \dots \cdot (n-k)}{(k+1)!}$ as pre-factor of the term with $n^{k+1}$ , whenever there is $n\ge k+1$ . In that case,

$\begin{array}{cc}\frac{n^k}{\sum _{l=0}^n(\genfrac{}{}{0ex}{}{n}{l})x^l}& \le \frac{n^k}{(\genfrac{}{}{0ex}{}{n}{k+1})x^{k+1}}\\ & =\frac{n^k}{\frac{n\cdot (n-1)\cdot (n-2)\dots (n-k)}{(k+1)!}{x}^{k+1}}\\ & =\frac{(k+1)!}{x^{k+1}}\cdot \frac{\stackrel{k\text{ factors}}{\overbrace{n\cdot n\cdot n\dots n}}}{\underset{(k+1)\text{ factors}}{\underbrace{n\cdot (n-1)\cdot (n-2)\dots (n-k)}}}\\ & =\frac{(k+1)!}{x^{k+1}}\cdot \frac{\stackrel{k\text{ factors}}{\overbrace{n\cdot n\cdot n\dots n}}}{\underset{k\text{ factors}}{\underbrace{(n-1)\cdot (n-2)\dots (n-k)}}}\cdot \frac{1}{n}\end{array}$

If we can now estimate the expression $\frac{n\cdot n\cdot n\dots n}{(n-1)\cdot (n-2)\dots (n-k)}$ from above by something independent of $n$ , we finally have made it! The pre-factor $\frac{(k+1)!}{x^{k+1}}$ remains constant in the limit process $n\to \mathrm{\infty }$ and cannot prevent convergence to 0. However, we will need to additionally require $n\ge 2k⟺\frac{n}{2}\ge k$. Hence,

For each $j\in \{1,\dots ,k\}$, we have $n-j=\frac{n}{2}+\underset{\ge 0}{\underbrace{(\frac{n}{2}-j)}}\ge \frac{n}{2}.$

This in turn implies

$\begin{array}{cc}\frac{n\cdot n\cdot n\dots n}{(n-1)\cdot (n-2)\dots (n-k)}& \le \frac{\stackrel{k\text{ times}}{\overbrace{n\cdot n\cdot n\dots n}}}{\underset{k\text{ times}}{\underbrace{(\frac{n}{2})\cdot (\frac{n}{2})\dots (\frac{n}{2})}}}\\ & =\frac{n^k}{\frac{n^k}{2^k}}\\ & =2^k\end{array}$

So all together,

$\begin{array}{cc}\frac{n^k}{\sum _{l=0}^n(\genfrac{}{}{0ex}{}{n}{l})x^l}& \le \frac{n^k}{(\genfrac{}{}{0ex}{}{n}{k+1})x^{k+1}}\\ & \le \frac{(k+1)!}{x^{k+1}}\cdot \frac{n^k}{(n-1)\cdot (n-2)\dots (n-k)}\cdot \frac{1}{n}\\ & \le \frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{n}\end{array}$

Since the expression $\frac{2^k(k+1)!}{x^{k+1}}$ does not depend on $n$ and $(\frac{1}{n})$ is a null sequence, the last expression must also be a null sequence.

For a mathematically exact proof, we need to find some $N\in \mathbb{N}$ for every $ϵ>0$ such that for all $n\ge N$ there is:

$|\frac{n^k}{z^n}-0|=\frac{n^k}{|z{|}^n}<ϵ$

For the above estimates, we need that $n>k+1$ and $n>2k$. Since $2k\ge k+1$ for all $k\in \mathbb{N}$ , we can restrict to $n>2k$. Further

$\begin{array}{ccc}& \frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{n}& <ϵ\\ ⟺& \frac{2^k(k+1)!}{x^{k+1}}& <ϵn\\ ⟺& \frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{ϵ}& <n\end{array}$

So we need to satisfy a second condition $n>\frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{ϵ}$. Both conditions can be made sure to be satisfied by setting $N>max\{2k,\frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{ϵ}\}$. Then, we get the desired result

$\left|\frac{n^k}{z^n}\right|\le \frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{n}<ϵ$

So, let's write this into a concise proof:

Proof

Let $z\in ℝ$ with $|z|>1$ be arbitrary. Set $x=|z|-1$. Then, $|z|=1+x$ with $x>0$.

Let $ϵ>0$ be arbitrary. Choose a natural number $N$ with $N>max\{2k,\frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{ϵ}\}$. Let $n\ge N$ be arbitrary. Then,

$\begin{array}{cc}\left|\frac{n^k}{z^n}\right|& =\frac{\left|n^k\right|}{\left|z^n\right|}\\ & =\frac{n^k}{|z{|}^n}\\ & =\frac{n^k}{(1+x{)}^n}\\ & \downarrow \text{binomial theorem}\\ & =\frac{n^k}{\sum _{l=0}^n(\genfrac{}{}{0ex}{}{n}{l})x^l}\\ & \le \frac{n^k}{(\genfrac{}{}{0ex}{}{n}{k+1})x^{k+1}}\\ & =\frac{(k+1)!\cdot \stackrel{k\text{ times}}{\overbrace{n\cdot n\cdot n\dots n}}}{n\cdot (n-1)\cdot (n-2)\dots (n-k)\cdot x^{k+1}}\\ & =\frac{(k+1)!\cdot \stackrel{k\text{ times}}{\overbrace{n\cdot n\cdot n\dots n}}}{\underset{k\text{ times}}{\underbrace{(n-1)\cdot (n-2)\dots (n-k)}}\cdot x^{k+1}}\cdot \frac{1}{n}\\ & \downarrow n>2k⟹n-1\ge \frac{n}{2},\dots ,n-k\ge \frac{n}{2}\\ & \le \frac{(k+1)!\cdot \stackrel{k\text{ times}}{\overbrace{n\cdot n\cdot n\dots n}}}{\underset{k\text{ times}}{\underbrace{\frac{n}{2}\cdot \frac{n}{2}\dots \frac{n}{2}}}\cdot x^{k+1}}\cdot \frac{1}{n}\\ & =\frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{n}\\ & \downarrow n\ge N>\frac{2^k(k+1)!}{x^{k+1}}\frac{1}{ϵ}\\ & <\frac{2^k(k+1)!}{x^{k+1}}\cdot \frac{1}{\frac{2^k(k+1)!}{x^{k+1}}\frac{1}{ϵ}}\\ & =\frac{1}{\frac{1}{ϵ}}\\ & =ϵ\end{array}$

Hint

Sometimes, you may encounter the limit $\underset{n\to \mathrm{\infty }}{lim}{n}^k{q}^n=0$ for all $k\in \mathbb{N}$ and $q\in ℝ$ with $|q|<1$. For $q=0$, every term is $0$. For $q\ne 0$, we can reduce this to the above case by setting $z=\frac{1}{q}$. Obviously $|z|=\frac{1}{|q|}>1$, so

$\underset{n\to \mathrm{\infty }}{lim}{n}^k{q}^n\stackrel{z=\frac{1}{q}}{=}\underset{n\to \mathrm{\infty }}{lim}\frac{n^k}{z^n}=0$

Ratio - geometric sequence / factorial sequence

In simple words: "factorial beats exponential":

Theorem

Let $z$ be a real number with $|z|>1$. Then, $\underset{n\to \mathrm{\infty }}{lim}\frac{z^n}{n!}=0$.

How to get to the proof?

We need to show that $\left|\frac{z^n}{n!}\right|=\frac{|z{|}^n}{n!}=\frac{|z|\cdot |z|\cdot \dots \cdot |z|}{1\cdot 2\cdot \dots \cdot n}$ approaches 0, as $n$ goes to infinity. This will be done, by bounding it from above by a more simple expression, of which we already know that it converges to 0.

Let's take a closer look at the ratio we have to bound: Numerator and denominator consist of an equal number of factors ($n$ of them). But those in the denominator are gradually increasing, whereas those in the numerator stay constant at $|z|$ . So at some $k>|z|\iff \frac{|z|}{k}<1$ we expect the denominator to "overtake" the numerator and finally "win against it". For making the actual bounding, we will split the sequence elements in two parts: That one, where $k$ has not yet overtaken $|z|$ will contain only a fixed number of factors. By contrast, the part with $k>|z|$ will continue to grow with increasing $n$. We choose $M\in \mathbb{N}$ with $M\ge |z|$ as a threshold, after which "$k$ has overtaken $|z|$" and consider $n\ge M+1$. Then $\begin{array}{cc}\frac{|z{|}^n}{n!}& =\frac{|z|\cdot |z|\cdot \dots \cdot |z|}{1\cdot 2\cdot \dots \cdot n}\\ & =\underset{=\frac{|z{|}^M}{M!}}{\underbrace{\frac{|z|\cdot |z|\cdot \dots \cdot |z|}{1\cdot 2\cdot \dots \cdot M}}}\cdot \stackrel{n-M\text{ factors, each}}{\overbrace{\frac{|z|\cdot |z|\cdot \dots \cdot |z|}{(M+1)\cdot (M+2)\cdot \dots \cdot n}}}\\ & \downarrow \frac{|z|}{M+1},\frac{|z|}{M+2},\dots ,\frac{|z|}{n}\le \frac{|z|}{M+1}\\ & \le \frac{|z{|}^M}{M!}\cdot \frac{|z{|}^{n-M}}{(M+1{)}^{n-M}}\\ & =\frac{|z{|}^M}{M!}\cdot \frac{|z{|}^n}{(M+1{)}^n}\cdot \frac{(M+1{)}^M}{|z{|}^M}\\ & =\underset{\text{constant w.r. to }n}{\underbrace{\frac{(M+1{)}^M}{M!}}}\cdot {\left(\frac{|z|}{M+1}\right)}^n\end{array}$

Since $\frac{|z|}{M+1}<1$ , the sequence ${\left(\frac{|z|}{M+1}\right)}^n$ is a geometric one and goes to 0. The factor $\frac{(M+1{)}^M}{M!}$ is constant for increasing $n$ and does not destroy the convergence to 0. Therefore, we should be able to show $\underset{n\to \mathrm{\infty }}{lim}\frac{z^n}{n!}=0$:

$\frac{|z{|}^n}{n!}\le \underset{\to 0}{\underbrace{\underset{\text{constant w.r. to }n}{\underbrace{\frac{(M+1{)}^M}{M!}}}\cdot \underset{\to 0}{\underbrace{{\left(\frac{|z|}{M+1}\right)}^n}}}}$

The proof can be done explicitly, using the Epsilon-definition. Let $ϵ>0$ be given. We need to find an $N\in \mathbb{N}$ , such that for all $n\ge N$ the inequality $\frac{|z{|}^n}{n!}<ϵ$ holds. The elements $\frac{|z{|}^n}{n!}$ have already been bounded from above (see the inequality above). Will the right-hand side of this inequality get smaller than $ϵ$ for certain $n\ge N$? We have

$\begin{array}{cccc}& & \frac{(M+1{)}^M}{M!}\cdot {\left(\frac{|z|}{M+1}\right)}^n& <ϵ\\ & ⟺& {\left(\frac{|z|}{M+1}\right)}^n& <ϵ\cdot \frac{M!}{(M+1{)}^M}\end{array}$

The right-hand side does not depend on $n$. Since $\frac{|z|}{M+1}<1$ , the Archimedean axiom implies that there is an $L\in \mathbb{N}$, such that

${\left(\frac{|z|}{M+1}\right)}^L<ϵ\cdot \frac{M!}{(M+1{)}^M}$

And for all greater $n\ge L$, there is also

${\left(\frac{|z|}{M+1}\right)}^n\le {\left(\frac{|z|}{M+1}\right)}^L<ϵ\cdot \frac{M!}{(M+1{)}^M}$

Now, we have all parts together for constructing the proof. Throughout our considerations, we posed the conditions $n\ge L$ and $n\ge M+1$ . Both are satisfied by setting $N=max\{M+1,L\}$.

Proof

Let $ϵ>0$. By the Archimedean axiom there is an $M\in \mathbb{N}$ with $M\ge |z|$. Now, for all $n\ge M+1$:

$\begin{array}{cc}\frac{|z{|}^n}{n!}& =\frac{|z|\cdot |z|\cdot \dots \cdot |z|}{1\cdot 2\cdot \dots \cdot n}\\ & =\frac{|z{|}^M}{M!}\cdot \frac{|z{|}^{n-M}}{(M+1)\cdot (M+2)\cdot \dots \cdot n}\\ & \downarrow \frac{|z|}{M+1},\frac{|z|}{M+2},\dots ,\frac{|z|}{n}\le \frac{|z|}{M+1}\\ & \le \frac{|z{|}^M}{M!}\cdot \frac{|z{|}^{n-M}}{(M+1{)}^{n-M}}\\ & =\underset{\text{constant}}{\underbrace{\frac{(M+1{)}^M}{M!}}}\cdot {\left(\frac{|z|}{M+1}\right)}^n\end{array}$

Since $\frac{|z|}{M+1}<1$ there is an $L\in \mathbb{N}$ such that ${\left(\frac{|z|}{M+1}\right)}^L<ϵ\cdot \frac{M!}{(M+1{)}^M}$. For all $n\ge N=max\{M+1,L\}$ there is then

$\begin{array}{cc}\left|\frac{z^n}{n!}\right|& =\frac{|z{|}^n}{n!}\\ & \le \frac{|z{|}^M}{M!}\cdot \frac{|z{|}^{n-M}}{(M+1{)}^{n-M}}\\ & =\frac{(M+1{)}^M}{M!}\cdot {\left(\frac{|z|}{M+1}\right)}^n\\ & \le \frac{(M+1{)}^M}{M!}\cdot {\left(\frac{|z|}{M+1}\right)}^L\\ & <\frac{(M+1{)}^M}{M!}\cdot ϵ\cdot \frac{M!}{(M+1{)}^M}\\ & =ϵ\end{array}$

Ratio - factorial / $n^n$

In simple words: "$n^n$ beats factorial":

Theorem

There is $\underset{n\to \mathrm{\infty }}{lim}\frac{n!}{n^n}=0$.

Proof

Let $ϵ>0$. Choose $N\in \mathbb{N}$ such that $N\ge \frac{1}{ϵ}+1$. For all $n\ge N$ there is

$\begin{array}{cc}|\frac{n!}{n^n}-0|& =\frac{n!}{n^n}=\frac{1}{n}\cdot \frac{2\cdot 3\cdot \dots \cdot n}{n\cdot n\cdot \dots \cdot n}\\ & =\frac{1}{n}\cdot \prod _{k=2}^n\frac{k}{n}\\ & \downarrow \frac{k}{n}\le 1\text{ for all }k\in \{2,\dots ,n\}\text{ and hence }\prod _{k=2}^n\frac{k}{n}\le 1\\ & \le \frac{1}{n}\le \frac{1}{\frac{1}{ϵ}+1}<ϵ\end{array}$