Examples for limits – Serlo

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 what they look like and how they converge:

• $\lim _{n\rightarrow \infty }c=c$ for all $c\in \mathbb {R}$
• $\lim _{n\rightarrow \infty }{\tfrac {1}{n}}=0$
• $\lim _{n\rightarrow \infty }{\tfrac {1}{n^{k}}}=0$ for all $k\in \mathbb {N}$
• $\lim _{n\rightarrow \infty }{\tfrac {1}{\sqrt[{k}]{n}}}=0$ for all $k\in \mathbb {N}$
• $\lim _{n\rightarrow \infty }q^{n}=0$ for all $q\in \mathbb {R}$ with $|q|<1$
• $\lim _{n\rightarrow \infty }{\sqrt[{n}]{c}}=1$ for all $c>0$
• $\lim _{n\rightarrow \infty }{\sqrt[{n}]{n}}=1$
• $\lim _{n\rightarrow \infty }{\tfrac {n^{k}}{z^{n}}}=0$ for all $k\in \mathbb {N}$ and $z\in \mathbb {R}$ with $|z|>1$
• $\lim _{n\rightarrow \infty }n^{k}q^{n}=0$ for all $k\in \mathbb {N}$ and $q\in \mathbb {R}$ with $|q|<1$
• $\lim _{n\rightarrow \infty }{\tfrac {z^{n}}{n!}}=0$ for all $z\in \mathbb {R}$ with $|z|>1$
• $\lim _{n\rightarrow \infty }{\tfrac {n!}{n^{n}}}=0$
• $\lim _{n\rightarrow \infty }\left(1+{\tfrac {1}{n}}\right)^{n}=e$

Hint

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

There is actually an entire hierarchy of growth speeds. We express "$a_{n}$ wins against $b_{n}$" by writing $a_{n}\ll b_{n}$ and mathematically meaning $\lim _{n\to \infty }{\tfrac {a_{n}}{b_{n}}}=0$. 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

$\lim _{n\rightarrow \infty }c=c$

Example (Limit of a constant sequence)

• $\lim _{n\rightarrow \infty }42=42$
• $\lim _{n\rightarrow \infty }-1=-1$

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

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

$\underbrace {|a_{n}-c|} _{=\ 0}<\epsilon$

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\geq N=1$ be arbitrary. Then…

This fomulation can be simplified, since $n\geq 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 $\epsilon >0$ arbitrary. For all $n\in \mathbb {N}$ (and hence, almost all $n\in \mathbb {N}$) there is

$|a_{n}-c|=|c-c|=0<\epsilon$

Harmonic sequence

Theorem (Limit of the Harmonic sequence)

There is $\lim _{n\rightarrow \infty }{\tfrac {1}{n}}=0$.

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

We have to establish the inequality $\left|{\tfrac {1}{n}}-0\right|<\epsilon$ . First, let us get rid of the absolute $\left|{\tfrac {1}{n}}-0\right|$:

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

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

${\begin{array}{rrl}&{\tfrac {1}{n}}&<\epsilon \\\Leftrightarrow \ &1&<\epsilon \cdot n\\\Leftrightarrow \ &{\tfrac {1}{\epsilon }}&<n\end{array}}$

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

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

Just choose any $N\in \mathbb {N}$ with $N>{\tfrac {1}{\epsilon }}$. If we consider any bigger number $n\geq N$, then also $n\geq {\tfrac {1}{\epsilon }}$.

How do we know that such an $N$ exist? 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$ exist?

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={\tfrac {1}{\epsilon }}$.

Proof (Limit of the Harmonic sequence)

Let $\epsilon >0$ be arbitrary. We choose an $N\in \mathbb {N}$ with $N>{\tfrac {1}{\epsilon }}$. Te existence is provided by the Archimedean axiom. Let $n\geq N$ be arbitrary. Then

${\begin{aligned}\left|{\tfrac {1}{n}}-0\right|&=\left|{\tfrac {1}{n}}\right|={\tfrac {1}{n}}\leq {\tfrac {1}{N}}<\epsilon \end{aligned}}$

Inverse power series

Theorem

For all $k\in \mathbb {N}$ there is $\lim _{n\rightarrow \infty }{\tfrac {1}{n^{k}}}=0$.

How to get to the proof?

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

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

Now, resolve ${\tfrac {1}{n^{k}}}<\epsilon$ for $n$:

${\begin{array}{rrl}&{\tfrac {1}{n^{k}}}&<\epsilon \\\Leftrightarrow \ &1&<\epsilon \cdot n^{k}\\\Leftrightarrow \ &{\tfrac {1}{\epsilon }}&<n^{k}\\\Leftrightarrow \ &{\sqrt[{k}]{\tfrac {1}{\epsilon }}}&<n\\\Leftrightarrow \ &{\frac {1}{\sqrt[{k}]{\epsilon }}}&<n\end{array}}$

So we need to find an $N$ with $N>{\frac {1}{\sqrt[{k}]{\epsilon }}}$ . This can be done by the Archimedean axiom

Proof

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

${\begin{array}{rrl}&n&\geq N\\[0.5em]&&{\color {OliveGreen}\left\downarrow \ N>{\frac {1}{\sqrt[{k}]{\epsilon }}}\right.}\\[0.3em]\Rightarrow \ &n&>{\frac {1}{\sqrt[{k}]{\epsilon }}}\\[0.3em]\Rightarrow \ &n\cdot {\sqrt[{k}]{\epsilon }}&>1\\[0.3em]\Rightarrow \ &{\sqrt[{k}]{\epsilon }}&>{\tfrac {1}{n}}\\[0.3em]\Rightarrow \ &\epsilon &>{\tfrac {1}{n^{k}}}\\[0.3em]\Rightarrow \ &\epsilon &>\left|{\tfrac {1}{n^{k}}}-0\right|\\[0.3em]\Rightarrow \ &\left|{\tfrac {1}{n^{k}}}-0\right|&<\epsilon \end{array}}$

Inverse root sequence

Theorem

For all $k\in \mathbb {N}$ there is $\lim _{n\rightarrow \infty }{\tfrac {1}{\sqrt[{k}]{n}}}=0$.

How to get to the proof?

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

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

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

${\begin{array}{rrl}&{\tfrac {1}{\sqrt[{k}]{n}}}&<\epsilon \\\Leftrightarrow \ &1&<\epsilon \cdot {\sqrt[{k}]{n}}\\\Leftrightarrow \ &{\tfrac {1}{\epsilon }}&<{\sqrt[{k}]{n}}\\\Leftrightarrow \ &\left({\tfrac {1}{\epsilon }}\right)^{k}&<n\\\Leftrightarrow \ &{\frac {1}{\epsilon ^{k}}}&<n\end{array}}$

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

Proof

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

${\begin{array}{rrl}&N&>{\frac {1}{\epsilon ^{k}}}\\[0.3em]\Rightarrow \ &N\cdot \epsilon ^{k}&>1\\[0.3em]\Rightarrow \ &\epsilon ^{k}&>{\tfrac {1}{N}}\\[0.3em]\Rightarrow \ &\epsilon &>{\tfrac {1}{\sqrt[{k}]{N}}}\\[0.3em]\end{array}}$

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

${\begin{array}{rrl}&N&\leq n\\[0.5em]\Rightarrow \ &{\tfrac {1}{n}}&\leq {\tfrac {1}{N}}\\[0.5em]\Rightarrow \ &{\tfrac {1}{\sqrt[{k}]{n}}}&\leq {\tfrac {1}{\sqrt[{k}]{N}}}<\epsilon \\\end{array}}$

Geometric series

Theorem

For all $q\in \mathbb {R}$ with $|q|<1$ there is $\lim _{n\rightarrow \infty }q^{n}=0$ .

This is now an exponentially (and no longer polynomially) decreasing sequence, so in the end, it goes to 0 even faster.

Example

• $\lim _{n\rightarrow \infty }\left(-{\tfrac {1}{2}}\right)^{n}=0$
• $\lim _{n\rightarrow \infty }\left({\tfrac {1}{\pi }}\right)^{n}=0$

How to get to the proof?

We start again by simplifying the absolute $\left|q^{n}-0\right|$:

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

Using the Bernoulli-inequality we can show:

„For each $0\leq a<1$ and $\epsilon >0$ there is an $N\in \mathbb {N}$ mit $a^{N}<\epsilon$.“

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

$|q|^{n}=\underbrace {|q|^{n-N}} _{\leq \ 1}\cdot \underbrace {|q|^{N}} _{<\ \epsilon }<\epsilon$

Proof

Let $\epsilon >0$ and $q\in \mathbb {R}$ mit $|q|<1$ be arbitrary. By the Bernoulli-inequality, we obtain a $N\in \mathbb {N}$ mit $|q|^{N}<\epsilon$ . For all $n\geq N$, there is:

${\begin{aligned}\left|q^{n}-0\right|&=\left|q^{n}\right|=|q|^{n}=\underbrace {|q|^{n-N}} _{\leq \ 1}\cdot \underbrace {|q|^{N}} _{<\ \epsilon }<\epsilon \end{aligned}}$

Hint

We can also investigate convergence for $|q|\geq 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 $\lim _{n\to \infty }q^{n}=\lim _{n\to \infty }1=1$.
• $q=-1:$ Here, we get the alternating sequence $(q^{n})_{n\in \mathbb {N} }=\left((-1)^{n}\right)_{n\in \mathbb {N} }$. It "jumps" between 0 and 1 and hence divergence. 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 divrge“ 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 $\lim _{n\rightarrow \infty }{\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 $\left|{\sqrt[{n}]{c}}-1\right|<\epsilon$ . First, let us focus on the proof for $c\geq 1$. Then, ${\sqrt[{n}]{c}}\geq 1$ and we can leave out the absolute:

Fall 1: $c\geq 1$

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

${\begin{array}{rrl}&{\sqrt[{n}]{c}}-1&<\epsilon \\\Leftrightarrow \ &{\sqrt[{n}]{c}}&<1+\epsilon \\\Leftrightarrow \ &c&<(1+\epsilon )^{n}\\\end{array}}$

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

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

If we now set $p=1+\epsilon$ and $M=c$ , we get the desired $N\in \mathbb {N}$ mit $(1+\epsilon )^{N}>c$. we only need to show $(1+\epsilon )^{n}>c$ for all greater real numbres $n>N$, which is done via

$(1+\epsilon )^{n}=\underbrace {(1+\epsilon )^{n-N}} _{\geq \ 1}\underbrace {(1+\epsilon )^{N}} _{>\ c}>c$

Fall 2: $c<1$

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

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

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

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

So

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

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

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

Fall 1: $c\geq 1$

Let $\epsilon >0$ be arbitrary. We know that:

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

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

$(1+\epsilon )^{n}=\underbrace {(1+\epsilon )^{n-N}} _{\geq \ 1}\underbrace {(1+\epsilon )^{N}} _{>\ c}>c$

So

${\begin{array}{rrl}&c&<(1+\epsilon )^{n}\\\Rightarrow \ &{\sqrt[{n}]{c}}&<1+\epsilon \\\Rightarrow \ &{\sqrt[{n}]{c}}-1&<\epsilon \\\Rightarrow \ &\left|{\sqrt[{n}]{c}}-1\right|&<\epsilon \\\end{array}}$

Fall 2: $c<1$

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

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

So

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

n-th root of n

Theorem (Grenzwert n-te Wurzel von n)

There is $\lim _{n\rightarrow \infty }{\sqrt[{n}]{n}}=1$.

How to get to the proof? (Grenzwert n-te Wurzel von n)

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

${\begin{array}{rrl}&\left|{\sqrt[{n}]{n}}-1\right|&<\epsilon \\[0.3em]&&{\color {OliveGreen}\left\downarrow \ {\sqrt[{n}]{n}}\geq 1\right.}\\[0.3em]\Leftrightarrow \ &{\sqrt[{n}]{n}}-1&<\epsilon \\\Leftrightarrow \ &{\sqrt[{n}]{n}}&<1+\epsilon \\\Leftrightarrow \ &n&<(1+\epsilon )^{n}\\\end{array}}$

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

$(1+\epsilon )^{n}=\sum _{k=0}^{n}{\binom {n}{k}}\epsilon ^{k}=1+n\epsilon +{\frac {n(n-1)}{2}}\epsilon ^{2}+\ldots +\epsilon ^{n}$

Each term in this sum is $\geq 0$. So, if we can show that $n$ gets smaller than any part of the sum $1+n\epsilon +{\frac {n(n-1)}{2}}\epsilon ^{2}+\ldots +\epsilon ^{n}$ , we know that $n$ is smaller than the entire series $1+n\epsilon +{\frac {n(n-1)}{2}}\epsilon ^{2}+\ldots +\epsilon ^{n}=(1+\epsilon )^{n}$ . We choose the terms $1$ and ${\tfrac {n(n-1)}{2}}\epsilon ^{2}$ both suffice to establish

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

which in turn is smaller than

$1+{\frac {n(n-1)}{2}}\epsilon ^{2}\leq 1+n\epsilon +{\frac {n(n-1)}{2}}\epsilon ^{2}+\ldots +\epsilon ^{n}=(1+\epsilon )^{n}$

so

$n<(1+\epsilon )^{n}$

What is a suitable $n$ to get $n<1+{\tfrac {n(n-1)}{2}}\epsilon ^{2}$? Let us resolve for $n$:

${\begin{array}{rrl}&n&<1+{\frac {n(n-1)}{2}}\epsilon ^{2}\\[0.3em]\Leftrightarrow \ &n-1&<{\frac {n(n-1)}{2}}\epsilon ^{2}\\[0.3em]\Leftrightarrow \ &1&<{\frac {n}{2}}\epsilon ^{2}\\[0.3em]\Leftrightarrow \ &2&<n\epsilon ^{2}\\[0.3em]\Leftrightarrow \ &{\frac {2}{\epsilon ^{2}}}&<n\end{array}}$

By the Archimedean axiom, there is an $N$, with ${\tfrac {2}{\epsilon ^{2}}}<n$ for all $n\geq N$ .

Proof (Grenzwert n-te Wurzel von n)

Let $\epsilon >0$ be arbitrary. We choose $N\in \mathbb {N}$ by the Archimedean axiom, such that $N>{\tfrac {2}{\epsilon ^{2}}}$ . Let $n\geq N$ be arbitrary. Then,

${\begin{array}{rrl}&{\frac {2}{\epsilon ^{2}}}&<n\\[0.3em]\Rightarrow \ &2&<n\epsilon ^{2}\\[0.3em]\Rightarrow \ &1&<{\frac {n}{2}}\epsilon ^{2}\\[0.3em]\Rightarrow \ &n-1&<{\frac {n(n-1)}{2}}\epsilon ^{2}\\[0.3em]\Rightarrow \ &n&<1+{\frac {n(n-1)}{2}}\epsilon ^{2}\\[0.3em]&&{\color {OliveGreen}\left\downarrow \ 1+{\frac {n(n-1)}{2}}\epsilon ^{2}\leq \sum _{k=0}^{n}{\binom {n}{k}}\epsilon ^{k}=(1+\epsilon )^{n}\right.}\\[0.3em]\Rightarrow \ &n&<(1+\epsilon )^{n}\\[0.3em]\Rightarrow \ &{\sqrt[{n}]{n}}&<1+\epsilon \\[0.3em]\Rightarrow \ &{\sqrt[{n}]{n}}-1&<\epsilon \\[0.3em]&&{\color {OliveGreen}\left\downarrow \ {\sqrt[{n}]{n}}\geq 1\right.}\\[0.3em]\Rightarrow \ &\left|{\sqrt[{n}]{n}}-1\right|&<\epsilon \\[0.3em]\end{array}}$

Ratio - power series / geometric series

In simple words: "exponential beats polynomial":

Theorem

Let $k\in \mathbb {N}$ be arbitrary and $z$ a real number with $|z|>1$. Then, $\lim _{n\rightarrow \infty }{\tfrac {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{aligned}\left|{\frac {n^{k}}{z^{n}}}\right|&={\frac {\left|n^{k}\right|}{\left|z^{n}\right|}}\\[0.5em]&={\frac {n^{k}}{|z|^{n}}}\\[0.5em]&={\frac {n^{k}}{(1+x)^{n}}}\\[0.5em]&\quad {\color {Gray}\left\downarrow \ {\text{binomial theorem}}\right.}\\[0.5em]&={\frac {n^{k}}{\sum \limits _{l=0}^{n}{\binom {n}{l}}x^{l}}}\end{aligned}}$

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 ${\binom {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 enumerator includes $n^{k}$ , it may be useful to replace the denominator by some term $c_{k}\cdot n^{k+1}$ with $c_{k}\in \mathbb {R} ^{+}$ 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 ${\binom {n}{k+1}}x^{k+1}$. All other terms are left out for simplicity. Multiplying out yields ${\binom {n}{k+1}}={\tfrac {n(n-1)\cdot \ldots \cdot (n-k)}{(k+1)!}}$ as pre-factor of the term with $n^{k+1}$ , whenever there is $n\geq k+1$ . In that case,

${\begin{aligned}{\frac {n^{k}}{\sum _{l=0}^{n}{\binom {n}{l}}x^{l}}}&\leq {\frac {n^{k}}{{\binom {n}{k+1}}x^{k+1}}}\\[0.5em]&={\frac {n^{k}}{{\frac {n\cdot (n-1)\cdot (n-2)\dots (n-k)}{(k+1)!}}x^{k+1}}}\\[0.5em]&={\frac {(k+1)!}{x^{k+1}}}\cdot {\frac {\overbrace {n\cdot n\cdot n\dots n} ^{k{\text{ factors}}}}{\underbrace {n\cdot (n-1)\cdot (n-2)\dots (n-k)} _{(k+1){\text{ factors}}}}}\\[0.5em]&={\frac {(k+1)!}{x^{k+1}}}\cdot {\frac {\overbrace {n\cdot n\cdot n\dots n} ^{k{\text{ factors}}}}{\underbrace {(n-1)\cdot (n-2)\dots (n-k)} _{k{\text{ factors}}}}}\cdot {\frac {1}{n}}\end{aligned}}$

If we can now estimate the expression ${\tfrac {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 ${\tfrac {(k+1)!}{x^{k+1}}}$ remains constant in the limit process $n\to \infty$ and cannot avoid convergence to 0. However, we will need to additionally require $n\geq 2k\iff {\tfrac {n}{2}}\geq k$. Hence,

${\begin{aligned}n-1&={\frac {n}{2}}+\underbrace {{\frac {n}{2}}-1} _{\geq 0}\geq {\frac {n}{2}},\\[0.3em]n-2&={\frac {n}{2}}+\underbrace {{\frac {n}{2}}-2} _{\geq 0}\geq {\frac {n}{2}},\\[0.3em]\vdots &\\[0.3em]n-k&={\frac {n}{2}}+\underbrace {{\frac {n}{2}}-k} _{\geq 0}\geq {\frac {n}{2}}\end{aligned}}$

This in turn implies

${\begin{aligned}{\frac {n\cdot n\cdot n\dots n}{(n-1)\cdot (n-2)\dots (n-k)}}&\leq {\frac {\overbrace {n\cdot n\cdot n\dots n} ^{k{\text{ times}}}}{\underbrace {({\frac {n}{2}})\cdot ({\frac {n}{2}})\dots ({\frac {n}{2}})} _{k{\text{ times}}}}}\\[0.3em]&={\frac {n^{k}}{\frac {n^{k}}{2^{k}}}}\\[0.3em]&=2^{k}\end{aligned}}$

So all together,

${\begin{aligned}{\frac {n^{k}}{\sum _{l=0}^{n}{\binom {n}{l}}x^{l}}}&\leq {\frac {n^{k}}{{\binom {n}{k+1}}x^{k+1}}}\\[0.5em]&\leq {\frac {(k+1)!}{x^{k+1}}}\cdot {\frac {n^{k}}{(n-1)\cdot (n-2)\dots (n-k)}}\cdot {\frac {1}{n}}\\[0.5em]&\leq {\frac {2^{k}(k+1)!}{x^{k+1}}}\cdot {\frac {1}{n}}\end{aligned}}$

Since the expression ${\frac {2^{k}(k+1)!}{x^{k+1}}}$ does not depend on $n$ and $({\tfrac {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 $\epsilon >0$ such that for all $n\geq N$ there is:

$\left|{\frac {n^{k}}{z^{n}}}-0\right|={\frac {n^{k}}{|z|^{n}}}<\epsilon$

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

${\begin{array}{lrl}&{\frac {2^{k}(k+1)!}{x^{k+1}}}\cdot {\frac {1}{n}}&<\epsilon \\[1em]\iff \ &{\frac {2^{k}(k+1)!}{x^{k+1}}}&<\epsilon n\\[1em]\iff \ &{\frac {2^{k}(k+1)!}{x^{k+1}}}\cdot {\frac {1}{\epsilon }}&<n\end{array}}$

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

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

So, let's write this into a concise proof

Proof

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

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

${\begin{aligned}\left|{\frac {n^{k}}{z^{n}}}\right|&={\frac {\left|n^{k}\right|}{\left|z^{n}\right|}}\\[0.3em]&={\frac {n^{k}}{|z|^{n}}}\\[0.3em]&={\frac {n^{k}}{(1+x)^{n}}}\\[0.3em]&\quad {\color {Gray}\left\downarrow \ {\text{binomial theorem}}\right.}\\[0.3em]&={\frac {n^{k}}{\sum _{l=0}^{n}{\binom {n}{l}}x^{l}}}\\[0.3em]&\leq {\frac {n^{k}}{{\binom {n}{k+1}}x^{k+1}}}\\[0.3em]&={\frac {(k+1)!\cdot \overbrace {n\cdot n\cdot n\dots n} ^{k{\text{ times}}}}{n\cdot (n-1)\cdot (n-2)\dots (n-k)\cdot x^{k+1}}}\\[0.3em]&={\frac {(k+1)!\cdot \overbrace {n\cdot n\cdot n\dots n} ^{k{\text{ times}}}}{\underbrace {(n-1)\cdot (n-2)\dots (n-k)} _{k{\text{ times}}}\cdot x^{k+1}}}\cdot {\frac {1}{n}}\\[0.3em]&\quad {\color {Gray}\left\downarrow \ n>2k\ \Longrightarrow \ n-1\geq {\frac {n}{2}},\ \ldots \ ,n-k\geq {\frac {n}{2}}\right.}\\[0.3em]&={\frac {(k+1)!\cdot \overbrace {n\cdot n\cdot n\dots n} ^{k{\text{ times}}}}{\underbrace {{\frac {n}{2}}\cdot {\frac {n}{2}}\dots {\frac {n}{2}}} _{k{\text{ times}}}\cdot x^{k+1}}}\cdot {\frac {1}{n}}\\[0.3em]&={\frac {2^{k}(k+1)!}{x^{k+1}}}\cdot {\frac {1}{n}}\\[0.3em]&\quad {\color {Gray}\left\downarrow \ n\geq N>{\frac {2^{k}(k+1)!}{x^{k+1}}}{\frac {1}{\epsilon }}\right.}\\[0.3em]&<{\frac {2^{k}(k+1)!}{x^{k+1}}}\cdot {\frac {1}{{\frac {2^{k}(k+1)!}{x^{k+1}}}{\frac {1}{\epsilon }}}}\\[0.3em]&={\frac {1}{\frac {1}{\epsilon }}}\\&=\epsilon \end{aligned}}$

Hint

Sometimes, you may encounter sequences of the form$\lim _{n\to \infty }n^{k}q^{n}=0$ for all $k\in \mathbb {N}$ and $q\in \mathbb {R}$ with $|q|<1$. We can reduce them to the above case by setting $z={\tfrac {1}{q}}$. Obviously $|z|={\tfrac {1}{|q|}}>1$, so

$\lim _{n\to \infty }n^{k}q^{n}{\overset {z={\tfrac {1}{q}}}{=}}\lim _{n\to \infty }{\tfrac {n^{k}}{z^{n}}}=0$

Ratio - geometric series / factorial sequences

In simple words: "factorial beats exponential":

Theorem

Let $z$ be a real number with $|z|>1$. Then, $\lim _{n\rightarrow \infty }{\tfrac {z^{n}}{n!}}=0$.

How to get to the proof?

We need to show that $\left|{\tfrac {z^{n}}{n!}}\right|={\tfrac {|z|^{n}}{n!}}={\tfrac {|z|\cdot |z|\cdot \ldots \cdot |z|}{1\cdot 2\cdot \ldots \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: Enumerator and denominator consist of an equal amount of factors ($n$ of them). But those in the denominator are gradually increasing, whereas those in the enumerator stay constant at $|z|$ . So at some $k>|z|\Leftrightarrow {\tfrac {|z|}{k}}<1$ we expect the denominator to "overtake" the enumerator 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 bounded amount of factors. By contrast, the part with $k>|z|$ will continue to grow with increasing $n$. We choose $M\geq |z|$ as a threshold, after which "$k$ has overtaken $|z|$" and consider $n\geq M+1$. Then

${\begin{aligned}{\frac {|z|^{n}}{n!}}&={\frac {|z|\cdot |z|\cdot \ldots \cdot |z|}{1\cdot 2\cdot \ldots \cdot n}}\\[0.5em]&=\underbrace {\frac {|z|\cdot |z|\cdot \ldots \cdot |z|}{1\cdot 2\cdot \ldots \cdot M}} _{={\tfrac {|z|^{M}}{M!}}}\cdot \overbrace {\frac {|z|\cdot |z|\cdot \ldots \cdot |z|}{(M+1)\cdot (M+2)\cdot \ldots \cdot n}} ^{n-M{\text{ factors, each}}}\\&{\color {Gray}\left\downarrow \ {\tfrac {|z|}{M+1}},{\tfrac {|z|}{M+2}},\ldots ,{\tfrac {|z|}{n}}\leq {\tfrac {|z|}{M+1}}\right.}\\[0.5em]&\leq {\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}}}\\&=\underbrace {\frac {(M+1)^{M}}{M!}} _{{\text{constant w.r. to }}n}\cdot \left({\frac {|z|}{M+1}}\right)^{n}\end{aligned}}$

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

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

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

${\begin{aligned}&&{\frac {(M+1)^{M}}{M!}}\cdot \left({\frac {|z|}{M+1}}\right)^{n}&<\epsilon \\[0.5em]&\iff &\left({\frac {|z|}{M+1}}\right)^{n}&<\epsilon \cdot {\frac {M!}{(M+1)^{M}}}\end{aligned}}$

The right-hand side does not depend on $n$. Since ${\tfrac {|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}<\epsilon \cdot {\frac {M!}{(M+1)^{M}}}$

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

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

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

Proof

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

${\begin{aligned}{\frac {|z|^{n}}{n!}}&={\frac {|z|\cdot |z|\cdot \ldots \cdot |z|}{1\cdot 2\cdot \ldots \cdot n}}\\[0.5em]&={\frac {|z|^{M}}{M!}}\cdot {\frac {|z|^{n-M}}{(M+1)\cdot (M+2)\cdot \ldots \cdot n}}\\[0.5em]&{\color {Gray}\left\downarrow \ {\tfrac {|z|}{M+1}},{\tfrac {|z|}{M+2}},\ldots ,{\tfrac {|z|}{n}}\leq {\tfrac {|z|}{M+1}}\right.}\\[0.5em]&\leq {\frac {|z|^{M}}{M!}}\cdot {\frac {|z|^{n-M}}{(M+1)^{n-M}}}\\&=\underbrace {\frac {(M+1)^{M}}{M!}} _{\text{fest}}\cdot \left({\frac {|z|}{M+1}}\right)^{n}\end{aligned}}$

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

${\begin{aligned}\left|{\frac {z^{n}}{n!}}\right|&={\frac {|z|^{n}}{n!}}\\[0.5em]&\leq {\frac {|z|^{M}}{M!}}\cdot {\frac {|z|^{n-M}}{(M+1)^{n-M}}}\\[0.5em]&={\frac {(M+1)^{M}}{M!}}\cdot \left({\frac {|z|}{M+1}}\right)^{n}\\[0.5em]&\leq {\frac {(M+1)^{M}}{M!}}\cdot \left({\frac {|z|}{M+1}}\right)^{L}\\[0.5em]&<{\frac {(M+1)^{M}}{M!}}\cdot \epsilon \cdot {\frac {M!}{(M+1)^{M}}}\\[0.5em]&=\epsilon \end{aligned}}$

Ratio - factorial / $n^{n}$

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

Theorem

There is $\lim _{n\rightarrow \infty }{\tfrac {n!}{n^{n}}}=0$.

Proof

Let $\epsilon >0$. Choose $N\in \mathbb {N}$ such that $N\geq {\tfrac {1}{\epsilon }}+1$. For all $n\geq N$ there is

${\begin{aligned}\left|{\frac {n!}{n^{n}}}-0\right|&={\frac {n!}{n^{n}}}={\frac {1}{n}}\cdot {\frac {2\cdot 3\cdot \ldots \cdot n}{n\cdot n\cdot \ldots \cdot n}}\\[0.3em]&={\frac {1}{n}}\cdot \prod _{k=2}^{n}{\frac {k}{n}}\\[0.3em]&{\color {OliveGreen}\left\downarrow \ {\frac {k}{n}}\leq 1{\text{ for all }}k\in \{2,\ldots ,n\}{\text{ and hence }}\prod _{k=2}^{n}{\frac {k}{n}}\leq 1\right.}\\[0.3em]&\leq {\frac {1}{n}}\leq {\frac {1}{{\tfrac {1}{\epsilon }}+1}}<\epsilon \end{aligned}}$