# Sequences

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\]

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. 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:

- If \(0<q<1\), the sequence is monotonically decreasing and converges to zero as \(q^n\to 0\) as \(n\to\infty\).
- If \(-1<q<0\), the sequence is alternating in sign and converges to zero as \(q^n\to 0\) as \(n\to\infty\).
- If \(q>1\), the sequence is monotonically increasing as \(q^n\to\infty\) as \(n\to\infty\).
- If \(q<-1\), the sequence is unbound and alternates in sign.
- If \(q=0\) the sequence is constant \(0\).
- If \(q=1\) the sequence is constant \(a_1\).
- If \(q=-1\) the sequence is alternating between \(a_1\) and \(-a_1\).

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\) beng the first term.

Linear recurrence sequences can be expressed in a closed form as

\[\begin{array}{rl} x_2 &= a_1 \cdot q + d\\ x_3 &= (a_1 \cdot q + d) \cdot q + d = a_1 \cdot q^2 + d\cdot q + d\\ x_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\\ x_n &= a_1\cdot q^{n-1} + d\cdot(q^{n-2} + \dots + r + 1)\\ &= a_1\cdot q^{n-1} + d\cdot\left(\frac{r^{n-1}-1}{r-1}\right)\\ &= \left(a_1 + \frac{d}{q-1}\right)\cdot q^{n-1} - \frac{d}{q-1} \,\,\forall q\neq 1 \end{array}\]

Note that arithmetic sequences are linear recurrence sequence with \(q=1\) and geomtric 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 increasing}\\ \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\) 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:

- A limit is always distinct.
- \(\pm\infty\) is no valid limit
- Every monotonical and bounded sequence is convergent.
- Every convergent sequence is bounded.

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**.