Summations and Related Topics

Vocabulary and definitions related to summations, index notation, infinite series, and aggregate mathematical operators.

Summations

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

Index of summation

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

Lower bound (lower limit)

The variable $a$ in the summation notation $\sum_{i=a}^b x_i$, representing the starting value of the index.

Upper bound (upper limit)

The variable $b$ in the summation notation $\sum_{i=a}^b x_i$, representing the ending value of the index.

Empty sum

A sum where the upper bound $b$ is less than the lower bound $a$, which is defined to have a value of $0$.

Scope of a summation

The extent of the summation which continues until the first addition or subtraction symbol that is not enclosed in parentheses or part of a larger term.

Bijection

A one-to-one correspondence used to rewrite a sum over a finite set $S$ as a sum over indices in $|S|$; if $|S| = n$, then $\sum_{i \in S} x_i = \sum_{i=0}^{n-1} x_{f(i)}$.

Einstein summation convention

A notation proposed by Albert Einstein where the $\sum_i$ part is left out entirely in certain special types of sums.

Infinite sum

The limit of the series $s$ obtained by taking the sum of the first term, then the first two terms, etc., converging to a value $x$ if for any $\epsilon > 0$, there exists an $N$ such that for all $n > N$, $|s_n - x| < \epsilon$.

Double sums

Nested summations, such as $\sum_{i=1}^a \sum_{j=1}^b 1$, which can be thought of as two nested for loops summing an expression over all pairs of index values.

Linearity

A property of the summation operator where constant factors can be pulled out ($\sum_{i \in S} ax_i = a \sum_{i \in S} x_i$) and sums can be split ($\sum_{i \in S} (x_i + y_i) = \sum_{i \in S} x_i + \sum_{i \in S} y_i$).

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 by $\sum_{i=0}^n r^i = \frac{1-r^{n+1}}{1-r}$.

Harmonic series

The sum $\sum_{i=1}^n 1/i = H_n = \Theta(n \log n)$, which can be rederived using the integral technique or by grouping terms.

Identity element

The value that, when applied in an operation, does not change the other value; for sums it is $0$ and for products it is $1$.

Factorial function

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

Big AND (\bigwedge)

The aggregate operator $\bigwedge_{x \in S} P(x) \equiv \forall x \in S : P(x)$, which returns True if the index set is empty.

Big OR (\bigvee)

The aggregate operator $\bigvee_{x \in S} P(x) \equiv \exists x \in S : P(x)$, which returns False if the index set is empty.