Summations and Related Topics Flashcards

Vocabulary terms and definitions covering summations, series, product notation, and big operators as defined in the December 13, 2010 lecture by James Aspnes.

Summations

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 $\sum_{i=a}^b x_i$.

Index of summation

The variable $i$ in the notation $\sum_{i=a}^b x_i$ which loops through all values from the lower limit to the upper limit.

Empty sum

A summation where the upper bound $b$ is less than the lower bound $a$ ($b < a$), which is defined to have a value of $0$.

Summation recurrence (definition 1)

$\sum_{i=a}^b f(i) = 0$ if $b < a$, and $f(a) + \sum_{i=a+1}^b f(i)$ otherwise.

Scope of a summation

The range of terms included in the sum, extending to 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 sum written by replacing bounds with a subscript predicate that indices must obey, such as $\sum_{i \text{\{3, 5, 7\}}} i^2$, which equals $3^2 + 5^2 + 7^2 = 83$.

Einstein summation convention

A notation where the summation symbol $\sum_i$ is omitted entirely in certain special types of sums, proposed by physicist Albert Einstein.

Infinite sum limit

The limit of the series $s$; it converges to $x$ if for any $\epsilon > 0$, there exists an $N$ such that for all $n > N$, $|s_n - x| < \epsilon$.

Double sum

Two nested for loops in summation notation, such as $\sum_{i=1}^a \sum_{j=1}^b 1$, which sums the innermost expression over all pairs of values of the two indices.

Simple arithmetic series formula

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

Finite geometric series formula

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

Infinite geometric series formula

$\sum_{i=0}^{\infty} r^i = \frac{1}{1 - r}$, which holds when $|r| < 1$.

Carl Friedrich Gauss

The 18th-century mathematician alleged to have invented the trick of adding two copies of a sequence in opposite directions to derive the sum of an arithmetic series.

Linearity (summation identity)

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

Harmonic series

The sum $\sum_{i=1}^n 1/i$, denoted as $H_n$, which is given in the notes as being $\Theta(n \log n)$. (Note: Standard mathematics defines $H_n$ as $\Theta(\ln n)$).

Guess but verify method

A technique where values for the first few upper limits are tabulated to recognize a sequence, which is then proven correct by induction.

Integral technique for sums

A method to find big-Theta bounds for non-decreasing functions $f(n)$ using $\int_{a-1}^b f(x)\,dx \le \sum_{i=a}^b f(i) \le \int_{a}^{b+1} f(x)\,dx$.

Products notation ($\prod$)

Notation using the capital Greek letter pi to represent the multiplication of a series of values.

Factorial function ($n!$)

Defined for non-negative $n$ as $\prod_{i=1}^n i = 1 \times 2 \times \dots \times n$, where $0! = 1$.

Empty product

A product with an empty index set, defined to have the value $1$ (the identity element for multiplication).

Big AND (identity)

An aggregate operator returning True for an empty index set.

Big OR (identity)

An aggregate operator returning False for an empty index set.

Big Intersection over empty set

An operation that is undefined because there is no identity element in general for the intersection of a collection of sets.