Summation Notation, Operations, and Symmetric Equations

Vocabulary flashcards covering summation notation, index properties, identities, asymptotic evaluation techniques, big operators, and symmetric equation systems.

Summation

The discrete version of an integral where a sequence $x_a, x_{a+1}, \dots, x_b$ is added together, denoted by $\sum_{i=a}^{b} x_i$ using the capital Greek letter sigma.

Index of Summation

The variable (such as $i$, $j$, or $k$) in a summation that loops through all integer values from the lower bound to the upper bound inclusive.

Lower Limit

The starting value of the index variable in a summation, written as $a$ below the sigma symbol.

Upper Limit

The ending value of the index variable in a summation, written as $b$ above the sigma symbol.

Empty Sum

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

Scope of a Summation

The portion of an algebraic expression included within a summation, extending to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term.

Einstein Summation Convention

A notation convention proposed by theoretical physicist Albert Einstein that omits the explicit summation symbol $\sum_i$ entirely in certain special types of sums.

Infinite Sum

An expression where the upper limit is infinite ($\sum_{i=0}^{\infty} f(i)$), defined as the limit of the series $s_n$ of partial sums as $n$ approaches infinity.

Double Sum

A summation whose body is another summation, equivalent to two nested for-loops that sum the innermost expression over all pairs of index values.

Gauss Summation Formula

The identity $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, derived by adding two copies of the sequence running in opposite directions term by term.

Summation Linearity

The property that allows constant factors to be pulled out of a sum ($\sum a x_i = a \sum x_i$) and sums of terms to be split ($\sum (x_i + y_i) = \sum x_i + \sum y_i$).

Guess but Verify Method

A technique for identifying a summation formula by tabulating the sum for the first few values of the upper limit and proving the resulting pattern by induction.

Geometric Series

A series in which the ratio between adjacent terms is constant, satisfying $\sum_{i=0}^{n} r^i = \frac{1 - r^{n+1}}{1 - r}$ for $r \neq 1$ and $\sum_{i=0}^{\infty} r^i = \frac{1}{1 - r}$ for $|r| < 1$.

Arithmetic Series

A series in which the difference between adjacent terms is constant, with the general form $\sum_{i=1}^{n} (a i + b) = a \frac{n(n+1)}{2} + b n$.

Harmonic Series

The series $\sum_{i=1}^{n} \frac{1}{i} = H_n$, which yields the $n$-th harmonic number $H_n$ and has an asymptotic bound of $\Theta(n \log(n))$.

Product Operator

An operator denoted by the capital Greek letter pi $\prod$ used to compute the multiplication of a sequence of terms, as seen in $n! = \prod_{i=1}^{n} i$.

Empty Product

A product evaluated over an empty index set, defined to yield the multiplicative identity $1$ (which implies $0! = 1$).

Big AND Operator

An aggregate logical operator denoted by $\bigwedge_{x \in S} P(x)$ that evaluates to True when applied over an empty index set.

Big OR Operator

An aggregate logical operator denoted by $\bigvee_{x \in S} P(x)$ that evaluates to False when applied over an empty index set.

Big Intersection Operator

An aggregate set operation denoted by $\bigcap_{i=1}^{n} A_i$ that is undefined over an empty collection of sets because there is no general identity element.

Big Union Operator

An aggregate set operation denoted by $\bigcup_{i=1}^{n} A_i$ that yields the empty set when evaluated over an empty collection of sets.

Symmetric Power Sum System

A system of polynomial equations given by $a + b + c = 4$, $a^2 + b^2 + c^2 = 10$, and $a^3 + b^3 + c^3 = 22$ used to evaluate symmetric polynomial expressions.