Summations and Related Topics

Practice vocabulary flashcards covering the notation, formal definitions, standard series formulas, and identities related to summations and products based on notes by James Aspnes.

Index of Summation

The variable (often denoted as $i$, $j$, or $k$) used in a summation that loops through all values from the lower limit to the upper limit.

Lower Bound (Lower Limit)

The starting value, denoted as $a$ in the expression $\sum_{i=a}^{b} x_i$, for the index of summation.

Upper Bound (Upper Limit)

The ending value, denoted as $b$ in the expression $\sum_{i=a}^{b} x_i$, for the index of summation.

Empty Sum Rule

The rule stating that if the upper bound $b$ is less than the lower bound $a$ (i.e., $(b < a)$), then the value of the sum is $0$.

Formal Definition of Finite Sums

Defined by recurrences such as $\sum_{i=a}^{b} f(i) = f(b) + \sum_{i=a}^{b-1} f(i)$ if $b \geq a$, otherwise $0$.

Scope of a Summation

The extent of the summation which continues until the first addition or subtraction symbol not enclosed in parentheses or part of a larger term (like a fraction numerator).

Sum over an Index Set

A summation written with a single subscript giving a predicate that the indices must obey, such as $\sum_{p < 1000, \text{ p is prime}} \frac{1}{p}$.

Einstein Summation Convention

A notation style used by theoretical physicists where the summation symbol ($\sum$) is left out entirely for certain types of sums.

Infinite Sum Convergence

A series converges to a value $x$ if for any $\epsilon > 0$, there exists an $N$ such that for all $n > N$, the partial sum $s_n$ satisfies $|s_n - x| < \epsilon$.

Double Sum

Two nested summations where the innermost expression is summed over all pairs of values of the two indices, analogous to nested for loops.

Arithmetic Series

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

Geometric Series

A series where the ratio between adjacent terms is constant; the sum for a finite series is $\sum_{i=0}^{n} r^i = \frac{1 - r^{n+1}}{1 - r}$.

Harmonic Series

Denoted as $H_n = \sum_{i=1}^{n} \frac{1}{i}$, which is asymptotically $\Theta(n \log(n))$ according to these notes.

Gauss's Trick

The method of proving $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ by adding two copies of the sequence running in opposite directions to get $n$ terms that each sum to $(n+1)$.

Linearity (Summation Identity)

The property allowing constant factors to be pulled out ($\sum axi = a \sum xi$) and sums within sums to be split ($\sum (xi + yi) = \sum xi + \sum yi$).

Product Notation

Represented by the Greek letter capital pi ($\prod$), it denotes multiplying a series of values, such as $n! = \prod_{i=1}^{n} i$.

Identity Element (Summation and Product)

The default value for an empty operator: $0$ for sums (additive identity) and $1$ for products (multiplicative identity).

Big AND ($\bigwedge$)

An aggregate operator representing universal quantification ($\forall x \in S : P(x)$) that returns True for an empty index set.

Big OR ($\bigvee$)

An aggregate operator representing existential quantification ($\exists x \in S : P(x)$) that returns False for an empty index set.

Big Intersection ($\bigcap$)

An aggregate operator for sets that has no general identity element and is undefined for an empty collection of sets.