Examples for limits – "Math for Non-Geeks"

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

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

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

This fomulation can be simplified, since ${\displaystyle n\geq 1}$ just means that ${\displaystyle n}$ is a natural number:

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

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

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

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

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

Question: Which threshold ${\displaystyle N}$ will we choose for the later proof?

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

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

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

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

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

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

${\displaystyle {\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 ${\displaystyle N}$ with ${\displaystyle N>{\frac {1}{\sqrt[{k}]{\epsilon }}}}$ . This can be done by the Archimedean axiom

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

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

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

${\displaystyle {\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 ${\displaystyle N}$ with ${\displaystyle N>{\frac {1}{\epsilon ^{k}}}}$ . This can be done by the Archimedean axiom:

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

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

Using the Bernoulli's inequality we can show:

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

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

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

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

${\displaystyle {\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}}}$

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

${\displaystyle (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 ${\displaystyle \geq 0}$. So, if we can show that ${\displaystyle n}$ gets smaller than any part of the sum ${\displaystyle 1+n\epsilon +{\frac {n(n-1)}{2}}\epsilon ^{2}+\ldots +\epsilon ^{n}}$ , we know that ${\displaystyle n}$ is smaller than the entire series ${\displaystyle 1+n\epsilon +{\frac {n(n-1)}{2}}\epsilon ^{2}+\ldots +\epsilon ^{n}=(1+\epsilon )^{n}}$ . We choose the terms ${\displaystyle 1}$ and ${\displaystyle {\tfrac {n(n-1)}{2}}\epsilon ^{2}}$ both suffice to establish

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

which in turn is smaller than

${\displaystyle 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

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

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

${\displaystyle {\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 ${\displaystyle N}$, with ${\displaystyle {\tfrac {2}{\epsilon ^{2}}}<n}$ for all ${\displaystyle n\geq N}$ .

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 ${\displaystyle |z|>1}$ as ${\displaystyle 1+x}$ with ${\displaystyle x=|z|-1>0}$ . The term ${\displaystyle (1+x)^{n}}$ can be multiplied out using the binomial theorem:

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

${\displaystyle {\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 ${\displaystyle {\tfrac {n\cdot n\cdot n\dots n}{(n-1)\cdot (n-2)\dots (n-k)}}}$ from above by something independent of ${\displaystyle n}$ , we finally have made it! The pre-factor ${\displaystyle {\tfrac {(k+1)!}{x^{k+1}}}}$ remains constant in the limit process ${\displaystyle n\to \infty }$ and cannot avoid convergence to 0. However, we will need to additionally require ${\displaystyle n\geq 2k\iff {\tfrac {n}{2}}\geq k}$. Hence,

${\displaystyle {\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

${\displaystyle {\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,

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

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

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

${\displaystyle {\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 ${\displaystyle n>{\frac {2^{k}(k+1)!}{x^{k+1}}}\cdot {\frac {1}{\epsilon }}}$. Both conditions can be made sure to be satisfied by setting ${\displaystyle N>\max \left\{2k,{\frac {2^{k}(k+1)!}{x^{k+1}}}\cdot {\frac {1}{\epsilon }}\right\}}$. Then, we get the desired result

${\displaystyle \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

We need to show that ${\displaystyle \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 ${\displaystyle 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.