Summations and Related Topics

Vocabulary and key definitions regarding summations, products, specific mathematical series, and notation conventions used in discrete mathematics and algorithm analysis.

Summations

The discrete versions of integrals, written as $\sum_{i=a}^b x_i$ for a sequence $x_a, x_{a+1}, \dots, x_b$.

Index of summation

The variable (traditionally $i$, $j$, or $k$) used to loop through values from the lower limit to the upper limit.

Lower bound (or lower limit)

The starting value $a$ in the summation $\sum_{i=a}^b x_i$.

Upper bound (or upper limit)

The ending value $b$ in the summation $\sum_{i=a}^b x_i$.

Summation of an empty set

A sum where the upper bound $b$ is less than the lower bound $a$ ($b < a$), defined as $0$.

Scope of a summation

Extends to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term like a fraction numerator.

Einstein summation convention

A notation used in theoretical physics where the $\sum_i$ part is omitted entirely in certain special types of sums.

Infinite sum

The limit of the series $s$ obtained by taking the sum of the first term, the first two terms, the first three terms, and so on.

Double sums

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

Arithmetic series

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

Geometric series

A series where the ratio between adjacent terms is constant, defined as $\sum_{i=0}^n r^i = \frac{1-r^{n+1}}{1-r}$. When $|r| < 1$, the infinite sum is $\frac{1}{1-r}$.

Harmonic series

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

Linearity of summation

The property that allows constant factors to be pulled out ($\sum ax_i = a\sum x_i$) and internal sums to be split ($\sum (x_i + y_i) = \sum x_i + \sum y_i$).

Identity element for addition

The value $0$, which is returned for an empty sum because adding it to a value $x$ does not change $x$.

Identity element for multiplication

The value $1$, which is returned for an empty product because multiplying it by a value $x$ does not change $x$.

Product notation

Uses the capital Greek letter pi ($\prod$) to represent multiplying a series of values together.

Factorial function ($n!$)

Defined for non-negative $n$ as $\prod_{i=1}^n i = 1 \times 2 \times \dots \times n$, where $0! = 1$.

Big AND ($\bigwedge$)

A logical operator across a set that returns $True$ for an empty index set.

Big OR ($\bigvee$)

A logical operator across a set that returns $False$ for an empty index set.

Big Intersection ($\bigcap$)

An operator for a collection of sets that is undefined for an empty collection because there is no identity element.

Big Union ($\bigcup$)

An operator for a collection of sets that returns the empty set for an empty index set.