Summations and Related Topics Lecture Notes

Practice flashcards covering definitions, formulas, and properties of summations, products, and other big operators as described in the lecture notes.

Summation

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

Index of summation

The variable (usually $i$, $j$, or $k$) used to loop through values in a sum 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 variable $a$ in $\sum_{i=a}^b x_i$.

Upper bound (or upper limit)

The ending value of the index in a summation, denoted by the variable $b$ in $\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 portion of an expression affected by the summation operator; it extends to 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 as $\sum_{i \in S} x_i$.

Infinite sum

The limit of a series of partial sums $s_n$ as the number of terms approaches infinity, defined as $\sum_{i=0}^{\infty} x_i$.

Einstein summation convention

A notation proposed by Albert Einstein where the summation symbol $\sum$ is omitted entirely for certain special types of sums.

Double sum

A summation where the expression inside is itself another summation, behaving like nested for loops and summing over all pairs of values of the two indices.

Summation linearity

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

Arithmetic series

A series where the difference between adjacent terms is constant, with the simplest form being $\sum_{i=1}^n i = \frac{n(n + 1)}{2}$.

Geometric series

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

Harmonic series ($H_n$)

The sum of the inverses of the first $n$ integers, denoted as $\sum_{i=1}^n \frac{1}{i}$, which is approximated as $\Theta(n \log n)$ in these notes.

Product notation (Big Pi)

An operator, denoted by $\prod$, used to multiply a series of values, such as in the definition of factorial: $n! = \prod_{i=1}^n i$.

Empty product

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

Big AND ($\bigwedge$)

An operator that computes the logical AND over a set of predicates, equivalent to the universal quantifier $\forall x \in S : P(x)$, with an identity value of True.

Big OR ($\bigvee$)

An operator that computes the logical OR over a set of predicates, equivalent to the existential quantifier $\exists x \in S : P(x)$, with an identity value of False.

Big Intersection ($\bigcap$)

An operator representing the intersection of multiple sets; it is undefined for an empty collection of sets because there is no identity element.

Big Union ($\bigcup$)

An operator representing the union of multiple sets, which returns the empty set for an empty collection of sets.