Notes on Summations

Vocabulary and formulas concerning summations, series, products, and big operators from James Aspnes' lecture notes.

Summation

A discrete version of an integral; given a sequence $x_a, x_{a+1}, \text{...}, x_b$, its sum is written as $\sum_{i=a}^b x_i$.

Index of summation

The variable (such as $i$, $j$, or $k$) used to loop through all values from the lower limit to the upper limit in a sum.

Empty sum rule

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

Index shifting

The process of renaming or changing the range of an index variable by adjusting the lower and upper bounds to match, such as substituting $j = i - 1$.

Scope of a summation

The portion of an expression governed by the sigma; it extends to 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 style often used by theoretical physicists that leaves out the $\sum_i$ part entirely in certain special types of sums.

Infinite sum limit

The value $x$ a series converges to 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.

Standard Sum: $\sum_{i=1}^n 1$

The result is exactly $n$.

Simple Arithmetic Series: $\sum_{i=1}^n i$

The formula is $\frac{n(n+1)}{2}$, which equals $n$ times the average value $\frac{n+1}{2}$.

Finite Geometric Series: $\sum_{i=0}^n r^i$

The sum is equal to $\frac{1 - r^{n+1}}{1 - r}$, provided $r \neq 1$.

Infinite Geometric Series: $\sum_{i=0}^{\infty} r^i$

This sum equals $\frac{1}{1 - r}$ provided that $|r| < 1$.

Harmonic Series ($H_n$)

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

Linearity of Summation

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

Guess but verify method

A technique involving writing out the values of a sum for specific cases to recognize a pattern and then proving the formula by induction.

Big-Theta of Geometric Series

When $x$ is a constant not equal to $1$, the sum of a geometric series is always big-Theta of its largest term.

Integral trick (non-decreasing)

A strategy for bounding sums where $\int_{a-1}^b f(x)\,dx \leq \sum_{i=a}^b f(i) \leq \int_a^{b+1} f(x)\,dx$.

Product notation

A series of multiplied values written with the capital Greek letter pi ($\prod$).

Factorial function ($n!$)

The product of integers from $1$ to $n$, defined as $n! = \prod_{i=1}^n i$.

Empty product rule

An empty product is defined to have the value $1$, which is the identity element for multiplication.

Identity element (Big AND)

For the Big AND operator ($\bigwedge$), the value for an empty index set is True.

Identity element (Big OR)

For the Big OR operator ($\bigvee$), the value for an empty index set is False.

Identity element (Big Intersection)

There is no identity element in general for the Big Intersection ($\bigcap$) operator, and its value over an empty set is undefined.