Summations and Related Topics Flashcards

VOCABULARY style flashcards covering the definitions, notation, and properties of summations, products, and big operators based on lecture notes by James Aspnes.

Summation

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

Index of summation

The variable (such as $i$, $j$, or $k$) that loops through all values from the lower bound to the upper bound.

Lower bound (or lower limit)

The starting value of the index in a summation, denoted by the value $a$.

Upper bound (or upper limit)

The ending value of the index in a summation, denoted by the value $b$.

Empty sum

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

Scope of a summation

The range of an expression affected by the sigma; it extends to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term like a fraction.

Einstein summation convention

A practice in theoretical physics attributed to Albert Einstein where the summation symbol $\sum_{i}$ is omitted entirely for certain types of sums.

Infinite sum

An expression where the upper limit is infinite, defined as the limit of the series of partial sums $s_n$ as $n$ approaches infinity.

Double sum

A summation where the expression inside is another summation, functioning like nested for loops to sum values over all pairs of indices.

Arithmetic series

A series where the difference between adjacent terms is constant, notably the simplest form $\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}$ for $r \neq 1$.

Linearity of summation

A property allowing constant factors to be pulled out ($\sum ax_i = a \sum x_i$) and allowing sums inside the summation to be split ($\sum (x_i + y_i) = \sum x_i + \sum y_i$).

Harmonic series

The sequence of sums denoted by $\sum_{i=1}^{n} \frac{1}{i} = H_n = \Theta(n \log(n))$.

Product notation

A notation used to multiply a series of values, indicated by the capital Greek letter pi ($\prod$).

Empty product

A product where the index set is empty, defined to have the value $1$ because it is the identity element for multiplication.

Factorial function

A specific product for non-negative integers defined as $n! = \prod_{i=1}^{n} i = 1 \times 2 \times \dots \times n$, where $0! = 1$.

Big AND

An operator ($\bigwedge$) used to compute a logical AND over a series, equivalent to the universal quantifier $\forall x \in S : P(x)$. Its identity element for an empty set is True.

Big OR

An operator ($\bigvee$) used to compute a logical OR over a series, equivalent to the existential quantifier $\exists x \in S : P(x)$. Its identity element for an empty set is False.

Big Intersection

The operator $\bigcap_{i=1}^{n} A_i$ representing the intersection of a series of sets; it is undefined over an empty collection because there is no identity element.

Big Union

The operator $\bigcup_{i=1}^{n} A_i$ representing the union of a series of sets, with the empty set as its identity element.