Math for Non-Geeks/How to prove convergence and divergence

{{#invoke:Math for Non-Geeks/Seite|oben}}

In this chapter, we will explain how convergence and divergence of a sequence can be proven. Usually, this job splits into two steps: At first, one tries some brainstorming (with a pencil on a piece of paper), trying to find a way to prove convergence or divergence. Then, if one has a solution, one tries to write it down in a short and elegant way. What you can read in most math books is the result of the second step. The aim of step 2 ist to conserve your thoughts for further people (or a later version of yourself), such that the reader can understand the proof investing as little time / effort as possible. However, the thoughts which a mathematician has when trying to find a proof (in step 1) are often quite different from what is written down in step 2. The problems given in this chapter will illustrate both steps and the difference between how to get to a proof and how to write it down.

Be aware that for proving convergence or divergence, there is no "cooking recipe", which will always lead you to a working proof! There is rather a collection of tools you can always carry around with you (like a Swiss pocket knife) and which you can use for mathematical problem solving. In this chapter, we would like to provide you with a specific collection of such tools. Not every problem you encounter in an exercise class is directly solvable with one tool and sometimes, you need to creatively combine different tools and techniques in order to crack open a problem. Those exercises are designed for purpose: They are intended to train your skills in solving abstract problems by combining strategies you know in creative and uncommon ways. These problem solving skills turn out to be useful in a broad variety of jobs and even for your personal life. This is the reason, why math courses are part of the syllabus in school and a huge variety of university degree programmes! (Torturing you with technical formulas is only secondary Template:Smiley).

Proving convergence Template:Anchor

File:Beispielaufgabe zum Konvergenzbeweis einer Folge 01.webm

General structure of proof

Before turning to examples, we take a closer look at the structure of the proof. This way, we know what the final proof should look like. There is a mathematical definition for convergence of a sequence $(a_n{)}_{n\in \mathbb{N}}$ to a limit $a$, which looks as follows:

I.e. after passing an index number $N$, all elements with index number $n$ coming afterwards will be closer to the limit than a small amount $ϵ$. The proof that this statement holds looks as follows:

If you explicitly write down, what the natural number $N$ looks like, you do not need to explicitly show that $N$ exists, because writing down an explicit expression is already a proof.

An example problem

The solution involves the following steps:

1. Investigate the sequence for high $n$, in order to find a limit $a$
2. Make up a proof that $(a_n{)}_{n\in \mathbb{N}}$ converges to $a$ with a pencil on a piece of paper
3. Write down the proof in a short way, structured as above

Finding a limit

How does the sequence $a_n=\frac{n}{n+1}$ behave for high $n$? Will it converge? In order to get more confident with the sequence, there are some actions you could try:

• Calculate the first couple of elements: Compute the first couple of elements and what they explicitly look like. It is also useful to draw them in a diagram. Do they increase or decrease faster and faster? Are they jumping between two values? Or do they seem to approach a certain value?
• Compute some elements with huge indices: What is $a_{1000}$? How about $a_{1000000}$? A calculator or PC can be useful to find that out. Or you can make rough estimates what those $a_n$ are. Do they come close to a specific real number $a$? Then this may be your limit.
• Make assertions based in intuition: The more problems you solve, the more you get an intuition what a limit might be. Polynomials $n^k$ always run to infinity, as $n\to \mathrm{\infty }$. Exponentials $e^n$ run away even faster. Sequences like $\frac{1}{n^k}$ and $e^{-n}$ tend to 0. For fractions $\frac{n^a}{n^b}$, the higher power wins and exponential functions win against everything (if you feel confused now: we will later explain in detail what these intuitions mean).

So let us start to compute the first (let's say 10) elements of the sequence $a_n=\frac{n}{n+1}$ :

$n$	$\frac{n}{n+1}$
1	0,5
2	0,666…
3	0,75
4	0,8
5	0,833…
6	0,857…
7	0,875
8	0,888…
9	0,9
10	0,909…

We could also plot them in a diagram:

The elements seem to be monotonically increasing. The increase is getting smaller and smaller. Perhaps, it converges. But what can be a possible limit? Maybe, we compute some elements with high index numbers to see it:

or even higher:

These numbers are suspiciously close to $1$ . So we may assert that $1$ is the limit of the sequence. This intuitively makes sense in the following way: For high $n$ , there is $n+1\approx n$ ($1000001$ is almost the same as $1000000$). So for the quotient, we expect

following these considerations, we make the assertion that $1$ is the limit of the sequence $a_n=\frac{n}{n+1}$.

Finding the proof steps

The proof builds around establishing an inequality of the form $|a_n-a|<\dots <ϵ$. It is best to start with $|a_n-a|$ and try to find greater and greater terms, until one of them is $ϵ$ . Throughout these estimates, we can make any assumptions on $n$ of the form $n\ge N$ with $N$ being a natural number only depending on $ϵ$ and $a$ (note $N$ must not depend on $a_n$ !). If $N$ is too small, we just choose a bigger $N$.

Another often successful technique is to take $|a_n-a|<ϵ$ and get $n$ standing alone on one side. That means, we use some equivalent reformulations of the term in order to get it in the form $n\ge \dots$ with $\dots$ some term depending on $ϵ$. If we choose $N$ such that $N\ge \dots$, then for any $n>N$, there is also $n\ge \dots$. $n\ge \dots$ is just equivalent to $|a_n-a|<ϵ$ (if we only use equivalent reformulations, of course). So we have found a suitable $N$, such that $|a_n-a|<ϵ$ for all $n>N$. The following chapters will provide some examples how these techniques are applied.

Now let us return to the example. It is very useful to equivalently reformulate $|1-\frac{n}{n+1}|$:

We know that this term must get lower than any $ϵ>0$ for sufficiently high $n$. This is sometimes also called Archimedean axiom: for all $ϵ>0$ there exists an $M\in \mathbb{N}$ with $\frac{1}{M}<ϵ$ . We can directly reach $\frac{1}{n+1}<ϵ$ by choosing $n+1\ge M$ , since we instantly get $\frac{1}{n+1}\le \frac{1}{M}<ϵ$. Hence, it suffices if $n$ meets the following condition:

So we found the desired bound with condition $n\ge M-1$. For writing down the proof, we choose $N=M-1$, with $M$ being the fixed number from the Archimedean axiom above.

Writing down the proof

Now, we go over to step 2 and write down the proof. The final solution is quite short and concise:

That's it already! If we compare the proof above (step 2) with the derivation (step 1), we notice that they look entirely different. The proof is enormously short and the $M$ and $N$ seem to appear out of nowhere! It ma appear to you that the mathematician who wrote the proof is some kind of superhuman genius who has found some magical way to always and instantly get the right $M$ and $N$. However, this is not the case. In the beginning, the author often had no idea how the proof works and performed a lot of trial and error, as well as lengthy considerations in step 1. He/ she just did not write them down, because they would just require additional space on the paper and additional time to read.

Übungsaufgabe

We recommend that you try to solve the following exercise by yourself

Conducting proofs for divergence Template:Anchor

General proof structure

Divergence of a sequence occurs by definition if and only if the series is not convergent. Or in other words, divergence is the negation of convergence. That means, in the formal definition we have to switch quantifiers $\mathrm{\forall }\leftrightarrow \mathrm{\exists }$ and exchange $<\leftrightarrow \ge$. (or $>\leftrightarrow \le$ or $=\leftrightarrow \ne$ , respectively.) So divergence of $(a_n{)}_{n\in \mathbb{N}}$ amounts to:

The structure of proof is hence:

Some parts of the proof can later be omitted if they are obvious. But the proof structure is always the same.

An example

Now, let us take a look at an example for a proof of divergence:

The above techniques (compute the first sequence elements, see what happens for large element numbers) can be applied to make an assertion. the first sequence elements are $2,4,8,16,32,...$ and they start to grow quickly. For big $n$, the sequence elements become very large, as $2^{10}>1000,2^{20}>1000000,...$ . So $(a_n{)}_{n\in \mathbb{N}}$ should diverge. Now, let us try to find a proof for this assertion.

How to get the proof

The proof will base on an inequality chain of the form

So we start with the term $|a_n-a|$ and try to make it smaller and smaller, until we hit some $ϵ>0$ . $a$ is assumed to be arbitrary and we can not put any bounds on it: The proof must be conducted for all $a\in ℝ$.

However, $ϵ$ and $n$ can be chosen arbitrarily. We only need to respect that $ϵ>0$ and $n\ge N$ where $N$ is again some arbitrary natural number. Since $ϵ$ is introduced in the proof after $a$ our $ϵ$ is allowed to depend on $a$ (but not on $n$). The natural number $n$ may depend both on $a$, and on $ϵ$ . So within the estimate chain, we can set a bunch of conditions on $ϵ$ and $n$ . Later, those will be collected and put together in the beginning of the proof.

So, let us start with the expression $|2^n-a|$, where $a$ is arbitrary. We expect $2^n$ to get large, so it makes sense to use that it eventually gets larger than $a$. In case $2^n\ge a$ , we can omit the absolute which makes things a lot easier. Intuitively, it is clear that there must be an $n\in \mathbb{N}$ such that $2^n\ge a$ holds, since the $2^n$-terms get arbitrarily large. Mathematically, we can use the implications of the Bernoulli inequality:

In our case, setting $M=a$ and $p=2$ implies $2^n\ge a$:

(This will later be considered obvious and does not have to be proven, then). Now, we need to show $2^n-a\ge ϵ$ in order to complete the inequality chain:

Which means, we are done, if we can find an $ϵ$ with $2^n\ge a+ϵ$. In this case, for any $ϵ$ there is an $n$ with $2^n\ge a+ϵ$ , since $2^n$ grows arbitrarily large. The only condition we have to observe for the proof is $ϵ>0$ .Let us just take $ϵ=1$. For $n$ , the two conditions $2^n\ge a$ and $2^n\ge a+ϵ=a+1$ have to be simultaneously fulfilled. This can be done by choosing $2^n\ge \max \{a,a+1\}=a+1$.

Writing down the proof

Now, we have all material necessary to conduct a full proof:

Further proof methods for convergence and divergence

The examples above were some very detailed proofs of convergence or divergence, using the Epsilon-definition. Establishing those proofs may take a while. In practice, there are several tricks which short-cut the proof and make you directly recognize whether a sequence converges or diverges (and experienced mathematicians are frequently using them):

• All unbounded and monotone sequences diverge. Examples: $a_n=n,a_n=2n,a_n=n^2,$ diverge, as well as the above $a_n=2^n$, or $a_n=10^n$, or in general $a_n=q^n$ with $q>1$ and many more...
• A monotone but bounded sequence must always converge. Examples: $a_n=1-\frac{1}{2^n}$ is bounded from below by $\frac{1}{2}$ and from above by $1$. It increases monotonically, so it must converge.
• Let $(a_n{)}_{n\in \mathbb{N}}$ . If for any $ϵ>0$ there is an $N\in \mathbb{N}$ with $|a_n-a_m|<ϵ$ for all $n,m\ge N$ (i.e. sequence elements get closer and closer together) , then $(a_n{)}_{n\in \mathbb{N}}$ converges. This is called Cauchy-criterion and widely used in mathematics. Basically any time, $a$ is complicated or not well-known, which is mostly the case in abstract proofs.
• The Limit theorems tell you what happens if you add or multiply sequence, Examples: $a_n=n,a_n=n^2,$ diverge and so do $a_n=n+n^2$ or $a_n=4n^2$.
• The Squeeze theorem proves convergence by squeezing a sequence between a smaller and a larger sequence. This avoids the Epsilon-definition and can save a lot of effort.

{{#invoke:Math for Non-Geeks/Seite|unten}}