Summations and Related Topics Flashcards

Definition-based flashcards covering summation notation, special series, bounding techniques, and aggregate operators based on the lecture notes.

Summations

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

Index of summation

The variable (such as $i$) in a summation that loops through all values from the lower bound to the upper bound.

Lower bound (lower limit)

The starting value (denoted as $a$) for the index of summation.

Upper bound (upper limit)

The ending value (denoted as $b$) for the index of summation.

Empty sum

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

Scope (of a summation)

Extends to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term (like a fraction's numerator).

Index set (summation over)

A sum where consecutive integers are replaced by a single subscript representing a set or a predicate that the indices must satisfy.

Einstein summation convention

A notation used by theoretical physicists that omits the summation symbol ($\sum$) entirely in certain special types of sums.

Infinite Sum

The limit of a series of partial sums $s_n$ as $n$ approaches infinity; it converges to $x$ if for any $\epsilon > 0$, there exists an $N$ such that for all $n > N$, $|s_n - x| < \epsilon$.

Double sums

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

Simplest Arithmetic series

The sum $\sum_{i = 1}^{n} i = \frac{n(n + 1)}{2}$, which can be remembered as $n$ times the average value $\frac{n + 1}{2}$.

Geometric series (finite form)

A sum where the ratio between adjacent terms is constant, defined as $\sum_{i = 0}^{n} r^i = \frac{1 - r^{n+1}}{1 - r}$.

Geometric series (infinite form)

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

Harmonic series

The sum of the reciprocals of integers $\sum_{i = 1}^{n} \frac{1}{i} = H_n$, which has the asymptotic growth $\Theta(n \text{ log } n)$, as noted in the transcript's algorithm analysis section.

Linearity of the summation operator

The property allowing constant factors to be pulled out ($\sum ax_i = a \sum x_i$) and internal sums to be split ($\sum (x_i + y_i) = \sum x_i + \sum y_i$).

Guess but verify method

A technique where values of a sum are computed for small limits to identify a pattern, which is then proven using induction.

Gauss's trick

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

Integral technique (for bounding)

Using integration to find a big-Theta bound for sums of non-decreasing functions: $\int_{a-1}^{b} f(x)dx \leq \sum_{i = a}^{b} f(i) \leq \int_{a}^{b+1} f(x)dx$.

Pi notation (Product)

Used to denote the multiplication of a series of values, such as in the factorial definition $n! = \prod_{i = 1}^{n} i$.

Empty product

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

Big AND

The operator $\bigwedge_{x \in S} P(x)$, which is equivalent to the universal quantifier $\forall x \in S : P(x)$.

Big OR

The operator $\bigvee_{x \in S} P(x)$, which is equivalent to the existential quantifier $\exists x \in S : P(x)$.

Big Intersection

The operator $\bigcap_{i = 1}^{n} A_i = A_1 \cap A_2 \cap \text{...} \cap A_n$, which is undefined for an empty collection of sets.

Big Union

The operator $\bigcup_{i = 1}^{n} A_i = A_1 \cup A_2 \cup \text{...} \cup A_n$, where the result for an empty index set is the empty set.