Summations and Related Topics

These vocabulary flashcards cover the definitions, notation, and properties of summations, products, and other big operators as discussed in the 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 $i$, $j$, or $k$) used in a summation to loop through values from the lower bound to the upper bound.

Lower Bound

The starting value of the index in a summation, also known as the lower limit.

Upper Bound

The ending value of the index in a summation, also known as the upper limit.

Empty Sum

A summation where the upper bound $b$ is less than the lower bound $a$ ($b < a$), which by definition equals $0$.

Scope of a Summation

The range of the expression being summed, which extends until the first addition or subtraction symbol not enclosed in parentheses or part of a larger term like a fraction numerator.

Infinite Sum

The limit of the series of partial sums $s_n$ as $n$ approaches infinity, which converges to a value $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 summation symbol ($\sum$) is omitted entirely in certain special types of sums.

Double Sum

A series of nested summations, similar to nested for-loops, that sum an expression over all pairs of values of two indices.

Arithmetic Series

A series where the difference between adjacent terms is constant; its 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; the finite sum is given by $\sum_{i=0}^{n} r^i = \frac{1-r^{n+1}}{1-r}$.

Harmonic Series

A series denoted by the $n$-th harmonic number $H_n$, defined as $\sum_{i=1}^{n} \frac{1}{i}$, which is roughly $\Theta(\log(n))$.

Identity Element (Summation)

The value that when added to $x$ does not change $x$; for summations, this is $0$, which is also the value of an empty sum.

Product Notation

A notation using the capital Greek letter pi ($\prod$) to represent multiplying a series of values, such as the factorial function $n! = \prod_{i=1}^{n} i$.

Empty Product

A product over an empty set of indices, which is defined to be $1$ because it is the identity element for multiplication.

Big AND (\bigwedge)

A big operator representing the logical AND operation over a set; its value for an empty index set is True.

Big OR (\bigvee)

A big operator representing the logical OR operation over a set; its value for an empty index set is False.

Big Intersection (\bigcap)

A big operator representing the intersection of sets; it is undefined for an empty collection of sets.

Big Union (\bigcup)

A big operator representing the union of sets; its value for an empty index set is the empty set.