Summations and Related Topics Flashcards

These flashcards cover the terminology, notation, and standard formulas for summations, products, and other large mathematical operators as detailed in James Aspnes' lecture notes.

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, typically denoted as $i$, $j$, or $k$, that loops through all values from the lower bound to the upper bound in a summation.

Lower bound

Also called the lower limit, it is the starting value $a$ in the summation notation $\sum_{i=a}^{b} x_i$.

Upper bound

Also called the upper limit, it is the ending value $b$ in the summation notation $\sum_{i=a}^{b} x_i$.

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 reach of the summation operator which extends to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term like a fraction numerator.

Einstein summation convention

A lazy approach used by theoretical physicists where the summation symbol ($\sum$) is left out entirely in certain special types of sums.

Infinite sum

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

Double sum

Two nested summations that function like nested for loops, summing an expression over all pairs of values of the two indices.

Carl Friedrich Gauss

The 18th-century mathematician who allegedly invented the trick of summing the sequence $1$ to $n$ by adding two copies of the sequence running in opposite directions.

Standard Arithmetic Series sum

The formula for the sum of the first $n$ integers: $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, which is $n$ times the average value $\frac{n+1}{2}$.

Geometric series

A sum where the ratio between adjacent terms is constant, defined as $\sum_{i=0}^{n} r^i = \frac{1 - r^{n+1}}{1 - r}$ or $\sum_{i=0}^{\infty} r^i = \frac{1}{1-r}$ for $|r| < 1$.

Summation linearity

The property stating that constant factors can be pulled out ($\sum a x_i = a \sum x_i$) and sums inside sums can be split ($\sum (x_i + y_i) = \sum x_i + \sum y_i$).

Harmonic series

Represented by $\sum_{i=1}^{n} \frac{1}{i} = H_n$, which the transcript identifies with an asymptotic estimate of $\Theta(n \log n)$. (Note: $\Theta(\log n)$ is the standard bound, but the text specifies $\Theta(n \log n)$ in several sections).

Product notation

The multiplication of a series of values, denoted by the capital Greek letter pi ($\prod$).

Factorial function

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

Empty product

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

Big AND

The operator $\bigwedge_{x \in S} P(x)$, equivalent to $\forall x \in S : P(x)$, which returns the identity element True for an empty set.

Big OR

The operator $\bigvee_{x \in S} P(x)$, equivalent to $\exists x \in S : P(x)$, which returns the identity element False for an empty set.

Big Intersection

The notation $\bigcap_{i=1}^{n} A_i$ representing the intersection of multiple sets; it is undefined for an empty collection of sets.

Big Union

The notation $\bigcup_{i=1}^{n} A_i$ representing the union of multiple sets; its identity element is the empty set.