Chapter 12: Sequences, Sums, and Products

This chapter introduces notation for working with ordered lists of numbers and with repeated addition or multiplication. These ideas appear throughout mathematics whenever we want to describe a pattern compactly instead of writing out every term.

Sequences

A sequence is an ordered list of numbers. For example,

$0, 1, 2, 3, 4, 5, \dots$

is a sequence. A sequence differs from the sets introduced in Chapter 1 because order matters. When we use variables to represent terms in a sequence, we attach an index to each term:

$a_{0}, a_{1}, a_{2}, a_{3}, \dots$

The numbers in the subscripts are called indices (the plural of index).

Definition: Sequence

A sequence is an ordered list of numbers. We often denote the entire sequence by

$(a_{n})_{n = 0}^{\infty} .$

When the index range is clear, we may write this more simply as $(a_{n})$ . In either case, $a_{n}$ is the term with index $n$ . Braces are also sometimes used in the notation ${a_{n}}_{n = 0}^{\infty}$ , but parentheses more clearly emphasize that a sequence is ordered, unlike an ordinary set.

Definitions: Sequences and Tuples

Finite sequence. A finite sequence is an ordered list with a fixed number of terms:

$(a_{1}, a_{2}, \dots, a_{n}) .$

The number $n$ is the length of the finite sequence.

Infinite sequence. An infinite sequence, such as $(a_{n})_{n = 1}^{\infty}$ , continues indefinitely.

$n$ -tuple. An $n$ -tuple is another name for a finite sequence of length $n$ . In this chapter, an object that continues indefinitely is simply called a sequence rather than a tuple.

Finite Sequences as Coordinates

Chapter 11 introduced points with two, three, or more real coordinates. In the language of sequences, a point in $R^{n}$ is a finite sequence of $n$ real numbers:

$(x_{i})_{i = 1}^{n} = (x_{1}, x_{2}, \dots, x_{n}) \in R^{n},$

where

$R^{n} = n copies R \times R \times \dots \times R .$

For example, $(2, 3) \in R^{2}$ has two coordinates and represents a point in the plane, while $(2, 3, 1) \in R^{3}$ has three coordinates and represents a point in three-dimensional space.

The coordinate points (2, 3) in the plane and (2, 3, 1) in three-dimensional space, shown without vector arrows — Figure 12.1. Finite real sequences interpreted as points in two- and three-dimensional coordinate spaces.

Here, each tuple identifies a point. In linear algebra, the same tuple can give the coordinates of a vector; context determines the interpretation.

Warning: A Tuple Is Not a Set

The finite sequence

$(2, 5, 5)$

is a $3$ -tuple. As a tuple, both order and repetition matter. Therefore,

$(2, 5, 5) \neq = (5, 2, 5),$

because the entries occur in a different order.

As a set, repeated elements are only listed once, so

${2, 5, 5} = {2, 5} .$

Tuples and sets are therefore different mathematical objects and should not be used interchangeably.

Summation Notation

Definition: Summation Notation

Given a sequence $(a_{n})$ and integers $m$ and $p$ satisfying $m \leq p$ , the sum from $m$ to $p$ is written

$n = m \sum p a_{n} = a_{m} + a_{m + 1} + \dots + a_{p} .$

The variable $n$ is called the index of summation. The number $m$ is the lower limit of summation, while the number $p$ is the upper limit of summation.

Example: Expanding Sums

Expanding a sum makes the lower limit, upper limit, and pattern of terms explicit.

To illustrate this, we can expand the following sum by writing out the first few terms.

$n = 1 \sum 100 (3 + 4 n) = (3 + 4 \cdot 1) + (3 + 4 \cdot 2) + (3 + 4 \cdot 3) + \dots + (3 + 4 \cdot 100) = 7 + 11 + 15 + \dots + 403$ We can similarly do it with the following sum: $n = 1 \sum p (\frac{1}{2})^{n} = \frac{1 ^{1}}{2 ^{1}} + \frac{1 ^{2}}{2 ^{2}} + \frac{1 ^{3}}{2 ^{3}} + \dots + \frac{1 ^{p}}{2 ^{p}} = \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{2 ^{p}}$

Example: Writing Sums in Sigma Notation

Suppose we are given the following sum:

$1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \dots + \frac{1}{50}$

This sum can be written as

$n = 1 \sum 50 \frac{1}{n} .$

Now, consider the alternating sum:

$1 - 2 + 3 - 4 + 5 - 6 + 7 - 8$

This sum can be written as

$n = 1 \sum 8 (- 1)^{n - 1} n .$

The sign alternates because $(- 1)^{k} = 1$ when $k$ is even and $(- 1)^{k} = - 1$ when $k$ is odd. Here, $n - 1$ is even when $n$ is odd and odd when $n$ is even, so the terms have signs $+, -, +, -, \dots$ .

Example: Evaluating Sums

When the limits are finite, one direct way to evaluate a sum is to write out all its terms.

First, evaluate the following sum:

$g = 4 \sum 9 (5 g + 3) .$

Writing out the terms from $g = 4$ through $g = 9$ gives

$g = 4 \sum 9 (5 g + 3) = 23 + 28 + 33 + 38 + 43 + 48 = 213.$

Next, consider a sum whose terms are powers of $10$ :

$k = 1 \sum 3 \frac{7}{1 0 ^{k}} .$

Writing out the terms and converting them to decimals gives

$k = 1 \sum 3 \frac{7}{1 0 ^{k}} = \frac{7}{10} + \frac{7}{100} + \frac{7}{1000} = 0.7 + 0.07 + 0.007 = 0.777.$

The index variable is a dummy variable: it can be changed without changing the value of the sum. For instance,

$n = 3 \sum 6 (2 n - 1) = k = 3 \sum 6 (2 k - 1) = j = 3 \sum 6 (2 j - 1) .$

This is similar to how the name of a variable inside a programming loop can often be changed without changing what the loop computes.

Some algebraic rules make it possible to simplify sums without expanding every term.

Properties: Summation Notation

Let $c$ be a constant. For finite sums, the following properties are often useful.

Adding term by term. For sums with the same lower and upper limits,

$k = m \sum p (a_{k} + b_{k}) = k = m \sum p a_{k} + k = m \sum p b_{k} .$

Constant multiple. Constant factors can be pulled outside a sum:

$k = m \sum p c a_{k} = c k = m \sum p a_{k} .$

Sum of a constant. A constant added repeatedly is multiplied by the number of terms:

$k = m \sum p c = (p - m + 1) c .$

Splitting a sum. If $m \leq q < p$ , then a sum can be split into two parts:

$k = m \sum p a_{k} = k = m \sum q a_{k} + k = q + 1 \sum p a_{k} .$

Warning: A Common Mistake with Sums

In general, a sum of products is not the product of sums:

$k = m \sum p a_{k} b_{k} \neq = (k = m \sum p a_{k}) (k = m \sum p b_{k}) .$

Example: Using Properties of Sums

Consider the following sum:

$k = 1 \sum 4 (2 k + 3) .$

First, use the term-by-term addition property to separate the two parts of each term:

$k = 1 \sum 4 (2 k + 3) = k = 1 \sum 4 2 k + k = 1 \sum 4 3.$

Next, pull the constant factor $2$ outside the first sum. The second sum contains four copies of $3$ :

$k = 1 \sum 4 2 k + k = 1 \sum 4 3 = 2 k = 1 \sum 4 k + 4 \cdot 3.$

Finally, expand the remaining sum and evaluate:

$2 k = 1 \sum 4 k + 4 \cdot 3 = 2 (1 + 2 + 3 + 4) + 12 = 32.$

We can check the result by expanding the original sum directly:

$k = 1 \sum 4 (2 k + 3) = (2 \cdot 1 + 3) + (2 \cdot 2 + 3) + (2 \cdot 3 + 3) + (2 \cdot 4 + 3) = 5 + 7 + 9 + 11 = 32.$

Both routes give the same value. This direct expansion illustrates why the properties work in this example without serving as a general proof.

Summation notation also appears in mathematical definitions. For example, it allows the polynomials introduced in Chapter 4 to be written in the form

$f (x) = a_{n} x^{n} + a_{n - 1} x^{n - 1} + \dots + a_{1} x + a_{0} = k = 0 \sum n a_{k} x^{k} .$

Here:

$n$ is a non-negative integer.
$a_{n}, a_{n - 1}, \dots, a_{0}$ are real constants.
For a nonzero polynomial, $a_{n} \neq = 0$ , and $n$ is its degree.

The zero polynomial has all coefficients equal to zero. Its degree is left undefined in this book.

Product Notation

If we want to multiply elements of a sequence instead of adding them, we use product notation.

Definition: Product Notation

Given a sequence $(a_{n})$ and integers $m$ and $p$ satisfying $m \leq p$ , the product from $m$ to $p$ is written

$n = m \prod p a_{n} = a_{m} \cdot a_{m + 1} \cdot \dots \cdot a_{p} .$

The variable $n$ is called the index of multiplication. The number $m$ is the lower limit of the product, while $p$ is the upper limit of the product.

Example: Expanding Products

Expanding a product makes the lower limit, upper limit, and pattern of factors explicit.

To illustrate this, consider the following product:

$n = 1 \prod 4 n$

Writing out each factor gives

$n = 1 \prod 4 n = 1 \cdot 2 \cdot 3 \cdot 4 = 24.$

Now, consider a product with a general upper limit $p$ :

$n = 0 \prod p (2 + 3 n)$

Substituting successive values of $n$ gives

$n = 0 \prod p (2 + 3 n) = (2 + 3 \cdot 0) (2 + 3 \cdot 1) (2 + 3 \cdot 2) \dots (2 + 3 p) = 2 \cdot 5 \cdot 8 \dots (2 + 3 p) .$

Example: Writing Products in Pi Notation

Suppose we are given the product of the first $p$ even positive integers:

$2 \cdot 4 \cdot 6 \dots 2 p .$

This product can be written as

$n = 1 \prod p 2 n .$

Now, consider the product of the first $p$ odd positive integers:

$1 \cdot 3 \cdot 5 \dots (2 p - 1) .$

This product can be written as

$n = 1 \prod p (2 n - 1) .$

Example: Evaluating Products

When the limits are finite, a product can be evaluated by writing out and multiplying all its factors.

First, consider a constant factor repeated $p$ times:

$n = 1 \prod p 5 = 5^{p},$

because the factor $5$ is multiplied by itself $p$ times.

Now, evaluate the following finite product:

$n = 1 \prod 3 (n + 1) .$

Writing out its factors gives

$n = 1 \prod 3 (n + 1) = (1 + 1) (2 + 1) (3 + 1) = 2 \cdot 3 \cdot 4 = 24.$

Factorial notation is a common shorthand for a product of consecutive positive integers.

Definition: Factorial

For a positive integer $n$ , the factorial of $n$ , written $n!$ , is defined by

$n! = 1 \cdot 2 \cdot 3 \dots n = k = 1 \prod n k .$

It is also standard to define

$0! = 1.$

Example: Factorials and Product Notation

First, consider the product of the first five positive integers. By the definition of factorial,

$k = 1 \prod 5 k = 5! = 120.$

Now, consider the product of the first $p$ even positive integers. Each of the $p$ factors contains a factor of $2$ , so these factors can be collected as $2^{p}$ :

$k = 1 \prod p 2 k = (2 \cdot 1) (2 \cdot 2) (2 \cdot 3) \dots (2 \cdot p) = 2^{p} (1 \cdot 2 \cdot 3 \dots p) = 2^{p} p! .$

Product notation has algebraic properties similar to summation notation, but the operation is multiplication rather than addition.

Properties: Product Notation

Let $c$ be a constant. For finite products, the following properties are often useful.

Multiplying term by term. For products with the same lower and upper limits,

$k = m \prod p a_{k} b_{k} = (k = m \prod p a_{k}) (k = m \prod p b_{k}) .$

Constant factor. A constant factor appears once for each value of the index:

$k = m \prod p c a_{k} = c^{p - m + 1} k = m \prod p a_{k} .$

Product of a constant. In particular,

$k = m \prod p c = c^{p - m + 1} .$

Splitting a product. If $m \leq q < p$ , then a product can be split into two parts:

$k = m \prod p a_{k} = (k = m \prod q a_{k}) (k = q + 1 \prod p a_{k}) .$

Example: Using Properties of Products

Consider the following product:

$k = 1 \prod 4 2 k .$

The constant-factor property gives

$k = 1 \prod 4 2 k = 2^{4} k = 1 \prod 4 k = 2^{4} \cdot 4! = 384.$

We can check the result by expanding the original product directly:

$k = 1 \prod 4 2 k = (2 \cdot 1) (2 \cdot 2) (2 \cdot 3) (2 \cdot 4) = 2 \cdot 4 \cdot 6 \cdot 8 = 384.$

Again, the direct expansion illustrates the property in this example; the general rule is the one stated above.

Warning: A Common Mistake with Products

In general, a product of sums is not the sum of products:

$k = m \prod p (a_{k} + b_{k}) \neq = k = m \prod p a_{k} + k = m \prod p b_{k} .$

Comparing Sums and Products

Summation and product notation have the same basic anatomy: both specify an index, a lower limit, an upper limit, and a term that changes with the index. The operation symbol determines whether those terms are added or multiplied.

For completeness, when an index range contains no terms, we use the conventions

$n = m \sum p a_{n} = 0 and n = m \prod p a_{n} = 1 when m > p .$

These values preserve the usual rules for splitting sums and products.

Indexed Unions and Intersections

Chapter 2 introduced the union and intersection of two sets. When working with a finite sequence of sets

$A_{1}, A_{2}, \dots, A_{n},$

we can use indexed notation to combine all of them compactly.

Definition: Indexed Unions and Intersections

The indexed union contains every element that belongs to at least one of the sets:

$i = 1 ⋃ n A_{i} = A_{1} \cup A_{2} \cup \dots \cup A_{n} = {x ∣ x \in A_{i} for at least one i} .$

The indexed intersection contains every element that belongs to all of the sets:

$i = 1 ⋂ n A_{i} = A_{1} \cap A_{2} \cap \dots \cap A_{n} = {x ∣ x \in A_{i} for every i} .$

As with summation and product notation, $i$ is the index, while $1$ and $n$ specify its lower and upper limits.

Example: Indexed Union and Intersection

Consider the following three sets:

$A_{1} = {1, 2}, A_{2} = {2, 3}, A_{3} = {2, 4} .$

First, form their indexed union by collecting the elements that occur in at least one set:

$i = 1 ⋃ 3 A_{i} = A_{1} \cup A_{2} \cup A_{3} = {1, 2, 3, 4} .$

Next, form their indexed intersection by keeping only the elements that occur in every set:

$i = 1 ⋂ 3 A_{i} = A_{1} \cap A_{2} \cap A_{3} = {2} .$

Thus, the union contains all four elements appearing across the sets, whereas the intersection contains only the shared element $2$ .

The same notation can be used for an infinite sequence of sets. The indexed union

$i = 1 ⋃ \infty A_{i}$

contains the elements that belong to at least one set in the sequence. In contrast, the indexed intersection

$i = 1 ⋂ \infty A_{i}$

contains the elements that belong to every set in the sequence.

Sums and Products Over Sets

The sums and products above run over consecutive integer indices, such as $n = 1, 2, 3, \dots, p$ . In some mathematical statements, however, the index runs over the elements of a set instead. This is useful when the objects being added or multiplied are not naturally described by consecutive integers.

Definition: Sums and Products Over a Finite Set

Let $A$ be a finite set, and suppose that $f (x)$ assigns a number to each element $x \in A$ . The notation

$x \in A \sum f (x)$

means that we add the values $f (x)$ for all elements $x$ in $A$ . Similarly,

$x \in A \prod f (x)$

means that we multiply the values $f (x)$ for all elements $x$ in $A$ .

If $A = {x_{1}, x_{2}, \dots, x_{n}}$ , then

$x \in A \sum f (x) = f (x_{1}) + f (x_{2}) + \dots + f (x_{n}),$

and

$x \in A \prod f (x) = f (x_{1}) \cdot f (x_{2}) \dots f (x_{n}) .$

For finite sets, the order of the elements does not matter because addition and multiplication are commutative.

Example: Summing and Multiplying Over a Set

For a finite set, the notation tells us to apply the rule to each element and then combine the results.

Consider the set

$A = {1, 3, 5} .$

First, square each element of $A$ and add the resulting values:

$x \in A \sum x^{2} = 1^{2} + 3^{2} + 5^{2} = 35.$

Next, add $1$ to each element of $A$ and multiply the resulting values:

$x \in A \prod (x + 1) = (1 + 1) (3 + 1) (5 + 1) = 48.$

Set-indexed notation is also useful when the set contains labels rather than numbers. For example, let

$C = {red, blue, green}$

be a set of categories, and let $n_{c}$ denote the number of observations in category $c$ . The total number of observations across the categories can then be written as

$c \in C \sum n_{c} = n_{red} + n_{blue} + n_{green} .$

When using this notation, remember that a set contains each element only once. If repeated values matter, for example in a data set where the same value occurs multiple times, a sequence, list, or frequency table may be more appropriate than an ordinary set.

Keyboard shortcuts

Mathematics Brush-up for Data Science