Sequences

A sequence is an ordered list of numbers. The two questions that matter are: what is the $n$th term, and where — if anywhere — is the sequence heading?

Defining a sequence

A sequence $u_1, u_2, u_3, \ldots$ can be given in two ways.

By a formula for the $n$th term. $u_n = 4n - 1$ gives $3, 7, 11, 15, \ldots$ — any term can be written down directly, so $u_{100} = 399$ without computing the 99 before it.

By a recurrence relation, which gives each term in terms of previous ones, plus a starting value.

Recurrence relations

Given $u_1 = 3$ and $u_{n+1} = 2u_n + 1$, find the first four terms.

$$u_1 = 3$$ $$u_2 = 2(3) + 1 = 7$$ $$u_3 = 2(7) + 1 = 15$$ $$u_4 = 2(15) + 1 = 31$$

Some recurrences produce periodic sequences. With $u_1 = 2$ and $u_{n+1} = \dfrac{1}{1 - u_n}$:

$$u_1 = 2 \qquad u_2 = \frac{1}{1-2} = -1 \qquad u_3 = \frac{1}{1-(-1)} = \frac12 \qquad u_4 = \frac{1}{1-\frac12} = 2$$

The sequence has period 3, and it repeats forever. Once you spot a period, $u_{100}$ costs nothing: $100 = 3(33) + 1$, so $u_{100} = u_1 = 2$.

Arithmetic sequences

An arithmetic progression adds a constant common difference $d$ each time:

$$u_n = a + (n-1)d$$

For $3, 7, 11, 15, \ldots$: $a = 3$ and $d = 4$, so

$$u_n = 3 + 4(n-1) = 4n - 1$$

$$u_{20} = 4(20) - 1 = 79$$

Geometric sequences

A geometric progression multiplies by a constant common ratio $r$:

$$u_n = ar^{n-1}$$

For $2, 6, 18, 54, \ldots$: $a = 2$ and $r = 3$, so

$$u_n = 2 \times 3^{n-1} \qquad u_5 = 2 \times 81 = 162$$

To identify which type a sequence is, test both: is the difference between consecutive terms constant, or the ratio?

Convergence and limits

A sequence converges to $L$ if $u_n$ gets arbitrarily close to $L$ as $n \to \infty$. Otherwise it diverges.

For a rational expression, divide top and bottom by the highest power of $n$:

$$\lim_{n\to\infty}\frac{3n+1}{n+2} = \lim_{n\to\infty}\frac{3 + \frac1n}{1 + \frac2n} = \frac{3}{1} = 3$$

A geometric sequence $ar^{n-1}$ converges exactly when $|r| < 1$, and then its limit is 0. If $|r| > 1$ the terms grow without bound; if $r = -1$ they oscillate forever.

Proof by induction for sequences

A recurrence plus a conjectured formula is the classic induction question.

Given $u_1 = 3$ and $u_{n+1} = 2u_n - 1$, prove that $u_n = 2^n + 1$.

Base case. When $n = 1$: the formula gives $2^1 + 1 = 3$, matching $u_1 = 3$ ✓

Inductive step. Assume $u_k = 2^k + 1$ for some $k \ge 1$. Then

$$u_{k+1} = 2u_k - 1 = 2\left(2^k + 1\right) - 1 = 2^{k+1} + 2 - 1 = 2^{k+1} + 1$$

which is the formula with $n = k+1$ ✓

Conclusion. By induction, $u_n = 2^n + 1$ for all $n \ge 1$. $\blacksquare$