Summations and Related Topics

Flashcards covering definitions, formulas, and properties of summations, products, and other big operators based on 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 that loops through all values from the lower bound to the upper bound.

Lower bound

Also known as the lower limit, it is the starting value for the index of summation in a sum, denoted as $a$ in $\sum_{i=a}^{b} x_i$.

Upper bound

Also known as the upper limit, it is the ending value for the index of summation in a sum, denoted as $b$ in $\sum_{i=a}^{b} x_i$.

Empty sum

A sum where the upper bound is less than the lower bound ($b < a$), which is defined to have 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 like a fraction numerator.

Einstein summation convention

A notation used by theoretical physicists where the summation symbol $\sum_{i}$ is left out entirely in certain special types of sums.

Infinite sum

The limit of a series $s$ obtained by taking the sum of the first term, the first two terms, the first three terms, etc., as the upper limit approaches infinity.

Double sum

A summation where the expression inside is another summation, functioning like two nested for loops that sum over all pairs of index values.

Standard arithmetic series sum

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

Finite geometric series formula

The formula used to compute a sum where the ratio between adjacent terms is constant: $\sum_{i=0}^{n} r^i = \frac{1-r^{n+1}}{1-r}$.

Infinite geometric series formula

The sum $\sum_{i=0}^{\infty} r^i = \frac{1}{1-r}$, which holds true when $|r| < 1$.

Harmonic series

The sum represented by $\sum_{i=1}^{n} 1/i = H_n$, which the transcript identifies as $\Theta(n \log(n))$.

Linearity (Summation)

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

Product notation

Notation using the capital Greek letter pi ($\prod$) to represent the multiplication of a series of values.

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 with no terms, which is defined to have the value $1$, the identity element for multiplication.

Big AND

Represented as $\bigwedge_{x \in S} P(x)$, it is equivalent to $\forall x \in S : P(x)$ and returns $True$ for an empty index set.

Big OR

Represented as $\bigvee_{x \in S} P(x)$, it is equivalent to $\exists x \in S : P(x)$ and returns $False$ for an empty index set.

Big Intersection

Represented as $\bigcap_{i=1}^{n} A_i$, its result over an empty collection of sets is undefined as there is no identity element.

Big Union

Represented as $\bigcup_{i=1}^{n} A_i$, it returns the empty set when the index set is empty.