Summations and Related Discrete Operators

Flashcards covering the definitions, notation, identities, and computing strategies for summations and related discrete operators based on James Aspnes' lecture notes.

Summations

The discrete versions of integrals; for a sequence $x_a, x_{a+1}, \text{...}, x_b$, the sum is written as $\biguplus_{i=a}^{b} x_i$.

Index of summation

The variable (e.g., $i$, $j$, or $k$) used to loop through all values from the lower bound to the upper bound.

Lower bound

Also called the lower limit; the starting value of the summation index, denoted as $a$ in $\biguplus_{i=a}^{b} x_i$.

Upper bound

Also called the upper limit; the final value of the summation index, denoted as $b$ in $\biguplus_{i=a}^{b} x_i$.

Empty sum rule

If the upper bound $b$ is less than the lower bound $a$ ($b < a$), the sum is defined to be zero.

Index shifting

The practice of renaming indices or substituting them (e.g., replacing $i$ with $j = i - 1$) and adjusting the bounds to match, making the sum more convenient to work with.

Scope of a summation

Extends to the first addition or subtraction symbol that is not enclosed in parentheses or part of a larger term like a fraction numerator.

Einstein summation convention

A notation style where the summation symbol ($\biguplus_{i}$) is left out entirely in certain types of sums.

Infinite sum series limit

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

Double sums

Equivalent to two nested for loops; the effect is to sum the innermost expression over all pairs of values of the two indices.

Linearity of summation

A property where constant factors can be pulled out (\biguplus_{i \text{\in} S} ax_i = a\biguplus_{i \text{\in} S} x_i) and internal sums can be split (\biguplus_{i \text{\in} S} (x_i + y_i) = \biguplus_{i \text{\in} S} x_i + \biguplus_{i \text{\in} S} y_i).

Arithmetic series (simplest form)

$\biguplus_{i=1}^n i = \frac{n(n+1)}{2}$.

Geometric series (finite)

$\biguplus_{i=0}^n r^i = \frac{1-r^{n+1}}{1-r}$.

Gauss's trick

A derivation of the arithmetic series formula by adding two copies of the sequence running in opposite directions to get $2S = n(n+1)$.

Harmonic series ($H_n$)

\biguplus_{i=1}^n \frac{1}{i} = \text{\Theta}(n \text{ log } n). (Note: Per transcript data).

Empty product rule

Defined to have the value $1$, which is the identity element for multiplication.

Factorial function ($n!$)

The product of a series of values defined as $n! = \biguplus_{i=1}^n i = 1 \times 2 \times \text{\dots} \times n$, where $0! = 1$.

Big AND notation

\bigwedge_{x \text{\in} S} P(x) \text{\equiv} \text{\forall}x \text{\in} S : P(x), which returns True for an empty index set.

Big OR notation

\bigvee_{x \text{\in} S} P(x) \text{\equiv} \text{\exists}x \text{\in} S : P(x), which returns False for an empty index set.