Summations and Big Operators Notes

Flashcards covering the definitions, notation, and standard formulas for summations, products, and other big operators as discussed in James Aspnes' lecture notes.

Summations

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

Index of summation

The variable $i$ in the notation $\sum_{i=a}^b x_i$ used to loop through values from the lower limit to the upper limit.

Lower bound (lower limit)

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

Upper bound (upper limit)

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

Empty sum

A summation where the upper bound is less than the lower bound ($b < a$), resulting in a value of $0$.

Scope of a summation

The extent of the expression being summed, which continues until the first addition or subtraction symbol not enclosed in parentheses or part of a larger term.

Infinite sum

The limit of the series of partial sums $s_n$; it converges to $x$ if for any $\epsilon > 0$, there exists an $N$ such that for all $n > N$, $|s_n - x| < \epsilon$.

Einstein summation convention

A notation used by theoretical physicists where the sigma ($\sum$) is omitted entirely in certain special types of sums.

Double sum

Two nested summations, similar to nested for loops, where the innermost expression is summed over all pairs of values of the two indices.

Arithmetic series (simplest form)

The sum $\sum_{i=1}^n i = \frac{n(n+1)}{2}$, which can be remembered as $n$ times the average value $\frac{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}$. If $|r| < 1$, the infinite sum is $\frac{1}{1-r}$.

Linearity of summation

A property allowing constant factors to be pulled out of sums ($\sum axi = a \sum xi$) and sums inside sums to be split ($\sum (xi + yi) = \sum xi + \sum yi$).

Guess but verify method

A technique for computing sums by writing out the first few values to identify a pattern and proving the resulting formula by induction.

Harmonic series

The sum $\sum_{i=1}^n \frac{1}{i} = H_n = \Theta(n \log(n))$ (as specialized in this transcript's specific asymptotic notation).

Big Pi notation ($\prod$)

Notation used to represent the product of a series of values, defined similarly to summation but with multiplication.

Factorial function

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

Empty product

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

Big AND ($\bigwedge$)

A big operator that computes the logical conjunction of a series of predicates; its identity element/empty set value is True.

Big OR ($\bigvee$)

A big operator that computes the logical disjunction of a series of predicates; its identity element/empty set value is False.

Big Union ($\bigcup$)

An operator that computes the union of a collection of sets; its identity element/empty set value is the empty set.