Notes on Summations and Related Topics

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

Summation

The discrete version of integrals; 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 $i$ in the summation notation $\sum_{i=a}^{b} x_i$, which loops through all values from the lower bound to the upper bound.

Lower bound (lower limit)

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

Upper bound (upper limit)

The ending value $b$ in the summation notation $\sum_{i=a}^{b} x_i$, which is the final value included in the loop.

Empty sum

A summation where the upper bound is less than the lower bound ($b < a$); it is defined to have a value of $0$.

Scope (of a summation)

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 numerator.

Infinite sum

The limit of the series $s_n$ obtained by taking the sum of the first $n$ terms as $n$ approaches infinity, formally converging if $|s_n - x| < \epsilon$ for all $n > N$.

Einstein summation convention

A notation style where the summation symbol is left out entirely in certain types of sums, proposed by Albert Einstein.

Double sum

A summation where the expression inside is another summation, functioning like two nested for loops.

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}$, which is $n$ times the average value.

Geometric series

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

Harmonic series

The sum $\sum_{i=1}^{n} \frac{1}{i}$, denoted as $H_n$ (the $n$-th harmonic number), and characterized in the text as $\Theta(n \log n)$.

Linearity (of summation)

The property allowing constant factors to be pulled out as in $\sum ax_i = a \sum x_i$, and allowing sums to be split as in $\sum (x_i + y_i) = \sum x_i + \sum y_i$.

Product notation

A notation used to multiply a series of values, denoted by the Greek letter pi ($\prod$), such as in the definition of factorials: $n! = \prod_{i=1}^{n} i$.

Empty product

A product with no factors that is defined to have the value $1$, which is the identity element for multiplication.

Big AND (\bigwedge)

An operator representing universal quantification ($\forall$) over a set of predicates; returns $True$ for an empty index set.

Big OR (\bigvee)

An operator representing existential quantification ($\exists$) over a set of predicates; returns $False$ for an empty index set.

Big Intersection

The intersection of a collection of sets; it is undefined if the collection of sets is empty because there is no identity element.

Big Union

The union of a collection of sets; returns the empty set if the index set is empty.