Sequences and Series

A sequence is a function with an ordered index set. This viewpoint distinguishes a list of values from a set, explains recursive definitions, and fixes which terms a partial sum contains. Read Functions and Mappings first; techniques for manipulating sums are developed separately in Finite Sums and Summation Techniques.

This chapter moves from individual terms to partial sums and series. It introduces the meaning of convergence; convergence tests and a systematic treatment of infinite summation belong to Infinite Series in calculus.

Indexing is part of the definition

DefinitionDefinition and notation for a sequence

An infinite sequence in a set $X$ is a function $x:\mathbb N\to X$, with $x(n)$ written $x_n$. Here $\mathbb N=\{0,1,2,\ldots\}$. The entire sequence is denoted by

$$\{x_n\}_{n=0}^{\infty}=(x_0,x_1,x_2,\ldots).$$

When the terms are numbers, this is a numerical sequence; for example, $X=\mathbb R$ gives a real sequence. A single $x_n$ denotes the term at index $n$, whereas $\{x_n\}_{n=0}^{\infty}$ denotes the whole sequence.

The braces notation $\{x_n\}_{n=0}^{\infty}$ is common; the parentheses notation $(x_n)_{n=0}^{\infty}$ denotes the same sequence. Braces in this sequence notation do not turn it into an ordinary set that ignores order and repetition. For example, the sequence $(1,1,2)$ has three terms, while its set of values $\{1,2\}$ has two elements. The index range and context distinguish these uses.

The subscript $n=0$ outside the braces specifies the starting index. The superscript $\infty$ means that the indices continue indefinitely; it is neither a power nor a final term indexed by infinity. This notation lists terms and does not add them. Letters such as $a_n$ may be used instead, and $\{x_n\}$ or $(x_n)$ may abbreviate the sequence when the index range is understood.

Starting at $1$ is equally legitimate, in which case we write

$$\{x_n\}_{n=1}^{\infty}=(x_1,x_2,x_3,\ldots).$$

A finite sequence of length $N\ge1$ is a function on $\{0,\ldots,N-1\}$, denoted by

$$\{x_n\}_{n=0}^{N-1}=(x_0,x_1,\ldots,x_{N-1}).$$

There are $N$ terms, with final index $N-1$. When $N=0$, the domain is empty and we obtain the empty sequence.

Order and repetition matter. The sequences $(2,2,5)$ and $(2,5,2)$ differ, although both have the same set of values $\{2,5\}$. A real sequence takes values in $\mathbb R$, but sequences may also consist of vectors, functions, symbols, or other objects. A mathematical definition does not necessarily supply an efficient algorithm for computing arbitrary terms.

For example, with indices $i=1,\ldots,10$, let $a_i$ be the least prime divisor of $i+1$. The sequence is $(2,3,2,5,2,7,2,3,2,11)$. Each value is defined because $i+1>1$. Giving the index range prevents the mistaken request for a prime divisor of $1$.

Separate the index set, codomain, and image

A sequence is a function, so three sets must be distinguished: its indices, its possible values, and its values that actually occur. Naive Set Theory defines finite, countably infinite, and uncountable sets; here those terms must be attached to the right object.

All three examples below have the uncountable codomain $\mathbb R$, but their images are much smaller.

Sequence	Index set	Image
$(2,2,5)$	$\{0,1,2\}$, finite	$\{2,5\}$, finite
$x_n=7$ for $n\ge0$	$\mathbb N$, countably infinite	$\{7\}$, finite
$x_n=2n$ for $n\ge0$	$\mathbb N$, countably infinite	Nonnegative even integers, countably infinite

An infinite sequence has infinitely many positions, not necessarily infinitely many distinct values. Its image is always at most countable: assign each value its first occurrence index to obtain an injection into $\mathbb N$. Thus an ordinary real sequence cannot enumerate all real numbers. The uncountability proof for $\mathbb R$ appears in Number Systems, Algorithms, and Recursion.

More generally, a function $x:I\to X$ is an indexed family, written $(x_i)_{i\in I}$. The set $I$ may be uncountable; for example, $x_t=t$ for $t\in\mathbb R$. Such a family is not an ordinary sequence indexed by natural numbers. An ordinal-indexed family is called a transfinite sequence; ordinal indices may be countable or uncountable. This extension belongs to later set theory, not to the arithmetic and geometric sequences below.

One further distinction matters: the set of all infinite binary sequences is uncountable, although each individual binary sequence has only countably many positions and at most two values. The exploration at the end makes this precise.

Explicit and recursive descriptions

An explicit formula such as $a_n=2n+4$ specifies the value directly from the index. A recurrence such as $a_{n+1}=a_n+2$, together with $a_0=4$, defines the same sequence by relating neighboring terms. Both the recurrence and its starting data are needed.

The equation $a_{n+1}=2a_n-a_{n-1}$ alone does not specify a unique sequence. Supplying $a_0=4,a_1=6$ gives $a_n=2n+4$, as proved in Mathematical Induction. Different initial values generally give different solutions. For more involved recursive objects and termination arguments, continue with Number Systems, Algorithms, and Recursion.

The term “closed form” is relative to which operations and functions are admitted. A finite sum is not an infinite expression merely because it has a variable upper bound. It may require more arithmetic as the bound increases, but that is a computational issue distinct from whether it has finitely many terms.

Arithmetic sequences

DefinitionConstant first difference

An arithmetic sequence satisfies $a_{n+1}-a_n=d$ for a fixed constant $d$. With initial term $a_0$, its explicit formula is $a_n=a_0+nd$ for $n\ge0$.

The formula follows by induction: it holds at $0$, and adding $d$ changes $a_0+nd$ into $a_0+(n+1)d$. The word is arithmetic, referring to a constant difference, not “algorithmic,” which would concern computational procedures.

Let $S_N$ be the sum of the first $N$ terms, from $a_0$ through $a_{N-1}$. Writing the sum in forward and reverse order pairs each term with one whose index sums to $N-1$. Every pair has value $2a_0+(N-1)d$, so

$$S_N=\frac N2\bigl(2a_0+(N-1)d\bigr).$$

There are $N$ such pairs in the sum of the two copies; dividing by $2$ corrects the duplication. At $N=0$, the expression is zero, agreeing with the empty sum. If terms instead start at $a_1$, the corresponding formula uses $a_1$ and the last index $N$.

Geometric sequences

DefinitionConstant multiplicative step

A geometric sequence satisfies $a_{n+1}=ra_n$ for fixed $r$, with explicit form $a_n=a_0r^n$. The zeroth power in this formula is the constant $1$, including the polynomial convention when $r=0$.

The recurrence definition remains meaningful when some terms are zero; defining the sequence solely through ratios $a_{n+1}/a_n$ would exclude those cases. For the first $N$ terms, subtract $rS_N$ from $S_N$ to cancel the interior terms:

$$(1-r)S_N=a_0(1-r^N).$$

Consequently,

$$S_N= \begin{cases} \displaystyle a_0\frac{1-r^N}{1-r},&r\ne1,\\ Na_0,&r=1. \end{cases}$$

The condition $r\ne1$ comes from division, not from the definition of a geometric sequence. The finite identity holds even for $|r|\ge1$. Passing to an infinite sum is a separate limit question; the familiar limit $a_0/(1-r)$ applies when $|r|<1$. Convergence is developed in Infinite Series.

Terms, partial sums, and infinite series

For a sequence starting at zero, define

$$S_N=\sum_{n=0}^{N-1}a_n, \qquad S_0=0.$$

The original sequence lists terms; $(S_N)$ lists cumulative sums. The relation $a_N=S_{N+1}-S_N$ recovers a term. An infinite series is studied through whether its sequence of partial sums converges; merely writing infinitely many terms does not assign a finite sum.

For example, $a_n=1$ gives $S_N=N$, so the partial sums do not approach a finite real number. In contrast, $a_n=2^{-n}$ has $S_N=2(1-2^{-N})$, which approaches $2$. These examples distinguish a perfectly well-defined infinite sequence from convergence of its series.

Indicator sequences connect sets to sums

Let a finite universe be listed without repetition as $U=\{x_1,\ldots,x_N\}$. A subset $A\subseteq U$ has indicator sequence

$$\chi_A(i)= \begin{cases} 1,&x_i\in A,\\ 0,&x_i\notin A. \end{cases}$$

The subset itself has no order, but its indicator sequence depends on the chosen listing. For $U=(1,3,5,7,9)$ in this order, the prime subset has sequence $(0,1,1,1,0)$, while the multiples-of-three subset has $(0,1,0,0,1)$. Note that $1$ is not prime.

For each index,

$$\chi_{A\cap B}(i)=\chi_A(i)\chi_B(i),$$ $$\chi_{A\cup B}(i)=\chi_A(i)+\chi_B(i)-\chi_A(i)\chi_B(i),$$

and $\chi_{U\setminus A}(i)=1-\chi_A(i)$. Also, $A\subseteq B$ exactly when $\chi_A(i)\le\chi_B(i)$ at every index. Counting becomes

$$|A|=\sum_{i=1}^{N}\chi_A(i).$$

Each formula can be checked on the four possible pairs of indicator values. This is a concrete connection between sets, Boolean values, and finite sums.

Exercises

ExerciseKeep length and final index separate

A sequence has $a_n=3+2n$ for $n\ge0$. Find $a_4$ and the sum of its first five terms. How many terms occur from index $0$ through index $N$?

Show solution

Solution

$a_4=11$. The first five terms are $3,5,7,9,11$, with sum $35$. Indices $0$ through $N$ include $N+1$ terms, whereas the first $N$ terms end at index $N-1$.

ExerciseCheck the exceptional ratio

For $a_n=4r^n$, find the sum of the first three terms for $r=1,0,-1$. Check against the finite geometric-sum formula.

Show solution

Solution

The respective terms are $(4,4,4)$, $(4,0,0)$, and $(4,-4,4)$, with sums $12,4,4$. Use the separate $r=1$ branch for the first case. The other two follow from $4(1-r^3)/(1-r)$. No infinite-series convergence assumption is involved.

ExerciseA quadratic partial sum and its first term

Here terms start at $a_1$. Suppose $\alpha\ne0$ and, for every $n\ge1$,

$$S_n=\sum_{j=1}^{n}a_j=\alpha n^2+\beta n+\gamma.$$

Find $a_n$. When is the entire sequence arithmetic?

Show solution

Solution

The first term is $a_1=S_1=\alpha+\beta+\gamma$. For $n\ge2$,

$$a_n=S_n-S_{n-1}=\alpha(2n-1)+\beta.$$

From $a_2$ onward the common difference is $2\alpha$, but $a_2-a_1=2\alpha-\gamma$. Thus the entire sequence is arithmetic exactly when $\gamma=0$. The given formula was stated only for $n\ge1$, so substituting $n=0$ into it and assuming $S_0=\gamma$ would be invalid: the actual empty sum is zero.

ExerciseReconstruct a subset from its indicator

For the ordered listing $U=(a,b,c,d)$, let $\chi_A=(1,0,1,0)$ and $\chi_B=(0,1,1,0)$. Find $A\cap B$, $A\cup B$, and their sizes.

Show solution

Solution

The intersection indicator is $(0,0,1,0)$, so $A\cap B=\{c\}$ has size one. The union indicator is $(1,1,1,0)$, giving $\{a,b,c\}$ of size three. Summing each indicator counts its selected elements.

ExerciseSupply enough initial data

Explain why $a_{n+1}=2a_n-a_{n-1}$ for $n\ge1$, together with $a_0=4$, does not determine a unique sequence.

Show solution

Solution

Choosing $a_1=6$ gives $a_n=4+2n$, while choosing $a_1=4$ gives the constant sequence $a_n=4$. Both satisfy the stated recurrence and the one given initial value. A second starting value is needed to distinguish them.

ExerciseInfinite positions need not give infinitely many values

Compare the real sequences $x_n=(-1)^n$ and $y_n=n$, both indexed by $n\in\mathbb N$. State the cardinalities of their index sets, codomains, and images.

Show solution

Solution

Both index sets are countably infinite, and both declared codomains $\mathbb R$ are uncountable. The image of $x$ is the finite set $\{-1,1\}$; the image of $y$ is $\mathbb N$, countably infinite. Neither is an exhaustive listing of its codomain.

ExerciseFinite binary strings versus infinite binary sequences

Why is the set of all finite binary strings countable, while the set of all infinite binary sequences is uncountable? Include the empty string in the finite case.

Discussion guide

Solution

List finite strings by length and then lexicographically within each length: the empty string, $0$, $1$, $00$, $01$, $10$, $11$, and so on. There are $2^m$ strings of each length $m$, so any fixed string appears after finitely many earlier strings. This gives a countably infinite list.

For infinite sequences, suppose a list contains rows $s^{(0)},s^{(1)},\ldots$, where $s^{(k)}_n\in\{0,1\}$. Define $d_n=1-s^{(n)}_n$. The sequence $d$ differs from row $k$ at position $k$, so no row equals $d$. Every attempted list fails. This is the indicator-sequence version of the power-set diagonal argument from Naive Set Theory: each subset of $\mathbb N$ corresponds to one infinite binary membership sequence.