Summations and Related Topics

Vocabulary and concepts related to summations, series, products, and big operators as used in algorithm analysis and discrete mathematics.

Summation

The discrete version of an integral; given a sequence $x_a, x_{a+1}, \text{...}, x_b$, its sum is written as $\sum_{i=a}^{b} x_i$.

Index of summation

The variable (e.g., $i$) used in a summation that loops through all values from the lower bound to the upper bound.

Lower bound

Also called the lower limit, it is the starting value for the index of summation (denoted as $a$ in $\sum_{i=a}^{b} x_i$).

Upper bound

Also called the upper limit, it is the ending value for the index of summation (denoted as $b$ in $\sum_{i=a}^{b} x_i$).

Empty sum

A sum where the upper bound $b$ is less than the lower bound $a$; it is defined to be zero.

Scope

The extent of a summation, which reaches to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term (like a fraction's numerator).

Einstein summation convention

A practice in theoretical physics where the summation symbol $\sum_{i}$ is left out entirely in certain types of sums.

Infinite sum

The limit of the partial series $s_n$ as $n$ approaches infinity. It converges to $x$ if for any $\epsilon > 0$, there exists an $N$ such that for all $n > N$, |s_n - x| < \text{\epsilon}.

Double sum

Two nested summations that sum the innermost expression over all pairs of values of the two indices.

Arithmetic series

A sum where the difference between adjacent terms is constant; the simplest example is $\sum_{i=1}^{n} i = \frac{n(n + 1)}{2}$.

Geometric series

A sum where the ratio between adjacent terms is constant; the finite formula is $\sum_{i=0}^{n} r^i = \frac{1 - r^{n+1}}{1 - r}$.

Harmonic series

The sum $\sum_{i=1}^{n} 1/i$, denoted as $H_n$, which is categorized as $\Theta(n \text{ log } n)$.

Linearity

A property of summations where constant factors can be pulled out ($\sum a x_i = a \sum x_i$) and sums inside sums can be split.

Product notation (Pi)

A notation using the uppercase Greek letter pi (\Pi) to represent multiplying a series of values, such as the factorial $n! = \prod_{i=1}^{n} i$.

Empty product

A product with an empty index set, which is defined to have the value $1$, the identity element for multiplication.

Big AND (\bigwedge)

The logical operator $\bigwedge_{x \in S} P(x)$, which computes the conjunction of predicates across a set; its identity element is True.

Big OR (\bigvee)

The logical operator $\bigvee_{x \in S} P(x)$, which computes the disjunction of predicates across a set; its identity element is False.

Big Intersection (\bigcap)

The operator $\bigcap_{i=1}^{n} A_i$, which performs the intersection of a collection of sets; it is undefined for an empty collection.

Big Union (\bigcup)

The operator $\bigcup_{i=1}^{n} A_i$, which performs the union of a collection of sets; its identity element is the empty set.