raw book


Robert Eisele

If we assign each \(n\in\mathbb{N}\) a real number \(a_n\in\mathbb{R}\), we get a sequence \((a_n)\) with elements

\[(a_n) = a_1, a_2, a_3, \dots a_n\]

A sequence is a collection of numbers that follow a certain order or pattern. If a sequence starts at index \(k\), we call the sequence

\[(a_n)_{n\geq k} = a_k, a_{k+1}, a_{k+2}, \dots a_n = a_n - a_{k-1}\]

If \(n < \infty\), we call the sequence finite and otherwise infinite.

To define a sequence, we can state elements in explicit form

\[(a_n) = 1,2,3,4,\dots\]

or in closed form

\[(a_n) = n^2 = 1, 4, 9, 16, \dots\]

Additionally, we can define a sequence as a recurrence relation, where each term depends on the previous term:

\(a_1=0, a_2=a_1+1, a_3=a_2+2, a_4=a_3+3, \dots\)

A sequence is called a first-order recurrence if each element depends on only one previous term, such

\[(a_n) = \frac{1}{2}(a_{n-1} + \frac{c}{a_n})\]

A second-order recurrence for example is the famous Fibonacci-Sequence:

\[(a_n) = a_{n-1} + a_{n-2}\text{ with } a_0=a_1 = 1\]

Arithmetic Sequences

If the difference between two elements \(d\) is constant, such that

\[a_{n+1} - a_{n} = d\]

we call the sequence

\[(a_{n+1}) = a_{n} + d\]

an arthmetic sequence or arithmetic progression with \(a_1\) being the first term.

Arithmetic sequences can also be defined in a closed form:

\[(a_n) = a_1 + (n - 1)\cdot d\]

If \(d=0\) the sequence is constant. If \(d>0\), the sequence is monotonically increasing and if \(d<0\), the sequence is monotonically decreasing.

The name Aritmetic Sequence arises because each term other than the first is the arithmetic mean of its two neighbouring terms:

\[a_n = \frac{a_{n-1} + a_{n+1}}{2}\]

Geometric Sequences

If the quotient \(q\) of two consecutive elements is constant, such that

\[\frac{a_{n+1}}{a_n} = q\]

we call the sequence

\[(a_{n+1}) = a_n\cdot q\]

a geometric squence with \(a_1\) being the first term.

Geometric squences can also be defined in a closed form:

\[(a_n) = a_1\cdot q^{n-1}\]

Geometric series have the following behavior:

The name Geometric Sequence arises because each term other than the first is the geometric mean of its two neighbouring terms:

\[|a_n| = \sqrt{a_{n-1} \cdot a_{n+1}}\]

Linear Recurrence Sequences

In practice often a combination of arithmetic and geometric sequences aries. If we have a constant \(d\) and a constant \(q\) we call the sequence

\[(a_{n+1}) = a_n \cdot q + d\]

a linear recurrence sequence with \(a_1\) being the first term.

Linear recurrence sequences can be expressed in a closed form as

\[\begin{array}{rl} a_2 &= a_1 \cdot q + d\\ a_3 &= (a_1 \cdot q + d) \cdot q + d = a_1 \cdot q^2 + d\cdot q + d\\ a_4 &= (a_1 \cdot q^2 + d\cdot q + d) \cdot q + d = a_1 \cdot q^3 + d\cdot q^2 + d\cdot q + d\\ & \vdots\\ a_n &= a_1\cdot q^{n-1} + d\cdot(q^{n-2} + \dots + q + 1)\\ &= \begin{cases} a_1\cdot q^{n-1} + d\cdot\left(\frac{q^{n-1}-1}{q-1}\right) & \text{for } q \neq 1 \\ a_1 + d \cdot (n - 1) & \text{for } q = 1 \end{cases} \end{array}\]

Note that arithmetic sequences are linear recurrence sequence with \(q=1\) and geometric sequenecs are linear recurrence sequences with \(d=0\).

Inferring Parameters for Linear Recurrence Sequences

Let’s say we get the sequence \(a_1, a_2, a_3, \dots\), how can we infer the parameter \(q\) and \(d\) of this sequence?

We know that

\[\begin{array}{rl} a_2 &= a_1 \cdot q + d\\ a_3 &= a_2 \cdot q + d \end{array}\]

Subtracting both equations from another gives

\[a_3 - a_2 = (a_2 - a_1)\cdot q\]

From which follows that

\[q = \frac{a_3 - a_2}{a_2 - a_1}\]

Taking the first equation again gives

\[d = a_2 - a_1 \cdot q\]

Monotonicity of Sequences

An important criterion to distinguish sequences is the monotonicity of sequences. If the elements get larger with increasing index, the sequence is called monotonically increasing, if the elements get smaller with increasing index, the sequence is called monotonically decreasing. If the sequence is changing the sign, we call it an alternating sequence.

For a sequnce \((a_n)\) we say

\[\begin{array}{l} a_{n+1}\geq a_n \,\forall n\Leftrightarrow (a_n)\text{ is monotonically increasing}\\ a_{n+1}\leq a_n \,\forall n\Leftrightarrow (a_n)\text{ is monotonically decreasing}\\ a_{n+1}= a_n \,\forall n\Leftrightarrow (a_n)\text{ is constant}\\ \end{array}\]

If the relations hold for \(>\) and \(<\) instead of \(\geq\) and \(\leq\), we call the sequences strictly monotonically increasing and decreasing respectively.

Boundedness of Sequences

A sequence \((a_n)\) is called bounded if there exist two real numbers \(s\) and \(S\) such that all elements of the sequence are between lower bound \(s\) and upper bound \(S\):

\[s\leq a_n\leq S\,\forall n\]

Limits of Sequences

A sequence \((a_n)\) has a limit \(a\) if an infinite neighborhood of \(a<\infty\) results in a finite set of elements. In this case we say

\[\lim\limits_{n\to\infty} a_n=a\]

If a series has a limit, we call it convergent, otherwise divergent.

We can say the following about sequences:

Sequences that converge to zero are called null sequence.

We can say that a sequence \((a_n)\) converges to \(a\) if the sequence \((a_n-a)\) is a null sequence.

Cauchy convergence criterion

Augustin-Louis Cauchy formulated a more general criterion for the case that the limit \(a\) is not known beforehand. It says that a sequence \((a_n)\) is convergent iff for every arbitrary small \(\epsilon>0\) exists a \(n_0\in\mathbb{N}\) such that all all sequence elements \(a_i, a_j\) follow \(|a_i-a_j|<\epsilon\), begining with element \(a_{n_0}\). More formally this means

\[\forall\epsilon>0\exists n_0\in\mathbb{N}\forall i,j\geq n_0 : |a_i-a_j|<\epsilon\]

Important sequence limits

\[\begin{array}{rl} \lim\limits_{n\to\infty}\frac{a}{n} &= 0\forall a\in\mathbb{R}\\ \lim\limits_{n\to\infty}a^n &= 0\,\forall |a|<1\\ \lim\limits_{n\to\infty}\sqrt[n]{a}&=1\,\forall a\in\mathbb{R}^+\\ \lim\limits_{n\to\infty}\sqrt[n]{n} &= 1\\ \lim\limits_{n\to\infty}\left(1+\frac{1}{n}\right)^n &= e\\ \lim\limits_{n\to\infty}\left(1-\frac{1}{n}\right)^n &= \frac{1}{e}\\ \lim\limits_{n\to\infty}\left(1+\frac{k}{n}\right)^n &= e^k\\ \end{array}\]

Where \(e=2.71828\dots\) is the irrational number called Euler’s number.