Notes on Summations

A set of vocabulary flashcards covering the notation, formal definitions, standard formulas, and manipulation identities for summations and products as presented in James Aspnes' lecture notes.

Summation

The discrete versions of integrals; given a sequence $x_a, x_{a+1}, \text{...}, x_b$, its sum $x_a + x_{a+1} + \text{...} + x_b$ is written as \textstyle \text{\textsum}_{i=a}^b x_i.

Index of Summation

The variable (often $i$, $j$, or $k$) used to loop through values from a lower limit to an upper limit in a summation.

Lower Bound

Also called the lower limit, denoted as $a$ in the notation \textstyle \text{\textsum}_{i=a}^b x_i, representing the starting value of the index.

Upper Bound

Also called the upper limit, denoted as $b$ in the notation \textstyle \text{\textsum}_{i=a}^b x_i, representing the final value of the index.

Empty Sum

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

Scope

Describes which terms are included in a summation; 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 lazy approach adopted by theoretical physicists where the summation symbol (\text{\textsum}_i) is left out entirely in certain special types of sums.

Limit of an Infinite Sum

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

Double Sum

A summation where the expression inside is another summation, functioning like two nested for loops and summing over all pairs of indices.

Linearity

A property of the summation operator allowing constant factors to be pulled out (\text{\textsum} ax_i = a \text{\textsum} x_i) and sums to be split (\text{\textsum} (x_i + y_i) = \text{\textsum} x_i + \text{\textsum} y_i).

Arithmetic Series

A series where the difference between adjacent terms is constant; the simplest form is \textstyle \text{\textsum}_{i=1}^n i = \frac{n(n+1)}{2}.

Geometric Series

A series where the ratio between adjacent terms is constant; for a constant $r \neq 1$, the sum reaches \textstyle \text{\textsum}_{i=0}^n r^i = \frac{1-r^{n+1}}{1-r}.

Harmonic Series

The sum \textstyle \text{\textsum}_{i=1}^n \frac{1}{i}, denoted as $H_n$, which the notes identify as \text{\textTheta}(n \text{ log } n).

Guess but Verify Method

A technique for identifying a closed-form formula for a sum by computing the first few values to recognize a sequence pattern and then proving it by induction.

Big-Theta of a Geometric Series

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

Integral Trick for Summations

A bounding method where if $f(n)$ is non-decreasing, then \textstyle \text{\textintegral}_{a-1}^b f(x)dx \text{\textless} \text{\textsum}_{i=a}^b f(i) \text{\textless} \text{\textintegral}_a^{b+1} f(x)dx.

Empty Product

A product with no terms, which is defined to have the value $1$ because it is the identity element for multiplication.

Factorial Function

Defined for non-negative integers as n! = \textstyle \text{\textprod}_{i=1}^n i, with the consequence that $0! = 1$.

Big AND

A big operator defined as \textstyle \text{\textwedge}_{x \text{\textin} S} P(x) \text{\textequiv} \forall x \text{\textin} S : P(x); its identity element for an empty index set is True.

Big OR

A big operator defined as \textstyle \text{\textvee}_{x \text{\textin} S} P(x) \text{\textequiv} \text{\textexists} x \text{\textin} S : P(x); its identity element for an empty index set is False.

Carl Friedrich Gauss

An 18th-century mathematician alleged to have derived the arithmetic series formula by adding two copies of the series in opposite directions.