Summations and Related Topics

Vocabulary terms and definitions related to summations, products, and other big operators based on lecture notes.

Summation

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

Index of summation

The variable (typically $i$) used in summation notation that loops through all values from the lower bound to the upper bound.

Lower bound

The starting value (or lower limit) in a summation, denoted by $a$ in the expression $\sum_{i=a}^{b} f(i)$.

Upper bound

The ending value (or upper limit) in a summation, denoted by $b$ in the expression $\sum_{i=a}^{b} f(i)$.

Empty sum

A summation 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 extent of a summation expression, which continues until the first addition or subtraction symbol not enclosed in parentheses or part of a larger term.

Index set

A set of values over which an expression is summed, often used when indices are not consecutive integers, written using a predicate such as $\sum_{i \in \{3,5,7\}} i^2$.

Infinite sum

An expression where the upper limit is infinite, defined as the limit of the series of partial sums.

Convergence

The property where a limit of partial sums reaches a particular value $x$ such that for any $\epsilon > 0$, there exists an $N$ where all $s_n$ for $n > N$ satisfy $|s_n - x| < \epsilon$.

Einstein summation convention

A notation style where the summation symbol ($\sum$) is omitted entirely in certain special types of sums.

Double sum

Two nested summations that sum an innermost expression over all pairs of values of two indices, analogous to two nested for loops.

Geometric series

A series where the ratio between adjacent terms is constant, defined by the formula $\sum_{i=0}^{n} r^i = \frac{1 - r^{n+1}}{1 - r}$.

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}$.

Harmonic series

The sum $\sum_{i=1}^{n} \frac{1}{i}$, denoted as $H_n$, which is characterized by the asymptotic bound $\Theta(n \log(n))$ in the text.

Summation linearity

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

Product notation

A notation using the capital Greek letter pi ($\prod$) to represent the multiplication of a series of values, similar to summation notation.

Empty product

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

Factorial

A function for non-negative integers defined as $n! = \prod_{i=1}^{n} i$, where $0! = 1$.

Big AND

The operator ($\bigwedge$) that performs a logical AND over a set of predicates, returning True if the index set is empty.

Big OR

The operator ($\bigvee$) that performs a logical OR over a set of predicates, returning False if the index set is empty.

Big Intersection

The operator ($\bigcap$) for the intersection of a series of sets, which is undefined for an empty collection of sets.

Big Union

The operator ($\bigcup$) for the union of a series of sets, which returns the empty set if the index set is empty.