Summations, Big Operators, and Power Sums Review

Vocabulary flashcards covering summation notation, index bounds, summation identities, asymptotic bounds, product notation, big logical/set operators, and power sum equations.

Summations

Discrete versions of integrals written as $\sum_{i=a}^b x_i$ to represent the sum of a sequence $x_a, x_{a+1}, \dots, x_b$.

Index of summation

The variable in a summation (such as $i$) that loops through all integer values from the lower limit $a$ to the upper limit $b$.

Lower limit

The starting bound (such as $a$ in $\sum_{i=a}^b x_i$) for the index of summation.

Upper limit

The ending bound (such as $b$ in $\sum_{i=a}^b x_i$) for the index of summation.

Empty sum

A summation where the upper bound $b$ is strictly less than the lower bound $a$ ($b < a$), which is defined to equal $0$.

Scope of a summation

The portion of an expression covered by a summation symbol, extending to the first addition or subtraction symbol that is not enclosed in parentheses or part of a larger term.

Einstein summation convention

A notation convention in which the summation symbol $\sum$ is omitted entirely in certain special types of sums where the index set is understood.

Double sum

An expression containing two nested summations, such as $\sum_{i=1}^a \sum_{j=1}^b 1$, which sums the inner expression over all pairs of values of the two indices.

Geometric series formula

The identity $\sum_{i=0}^n r^i = \frac{1 - r^{n+1}}{1 - r}$, which holds when $r \neq 1$.

Arithmetic series formula

The sum identity $\sum_{i=1}^n i = \frac{n(n + 1)}{2}$, which equals $n$ times the average value $\frac{n + 1}{2}$.

Harmonic series

The sum $\sum_{i=1}^n \frac{1}{i}$, denoted $H_n$, which has an asymptotic bound of $\Theta(n \log(n))$.

Linearity of summation

The algebraic property allowing constant factors to be pulled out of sums ($\sum_{i \in S} a x_i = a \sum_{i \in S} x_i$) and additive terms inside sums to be split ($\sum_{i \in S} (x_i + y_i) = \sum_{i \in S} x_i + \sum_{i \in S} y_i$).

Product notation

The operator $\prod_{i=1}^n x_i$ used to multiply a sequence of values together, as in the factorial function $n! = \prod_{i=1}^n i$.

Empty product

A product over an empty index set ($b < a$), which is defined to equal $1$ (the identity element for multiplication).

Big AND

The operator $\bigwedge_{x \in S} P(x)$, which evaluates to True when taken over an empty index set.

Big OR

The operator $\bigvee_{x \in S} P(x)$, which evaluates to False when taken over an empty index set.

Big Union

The operator $\bigcup_{i=1}^n A_i$, which evaluates to the empty set $\emptyset$ when taken over an empty collection of sets.

Big Intersection

The operator $\bigcap_{i=1}^n A_i$, which is undefined over an empty collection of sets because no general identity element exists.

Power Sums System

A system of equations involving three variables $a, b, c$ given by $a + b + c = 4$, $a^2 + b^2 + c^2 = 10$, and $a^3 + b^3 + c^3 = 22$ to solve for $a^4 + b^4 + c^4$.