Summations and Related Topics Practice Flashcards

Flashcards covering definitions, formulas, and terminology related to summations, products, and other big operators as used in discrete mathematics and algorithm analysis.

Summation

The discrete version of an integral, representing the sum of a sequence $x_a, x_{a+1}, \dots, x_b$, denoted by the capital Greek letter sigma ($\sum$).

Index of Summation

The variable (often represented as $i, j, \text{ or } k$) that loops through all values from the lower bound to the upper bound in a summation.

Lower Bound (Lower Limit)

The value $a$ in the notation $\sum_{i=a}^{b} x_i$ that specifies the starting point of the summation.

Upper Bound (Upper Limit)

The value $b$ in the notation $\sum_{i=a}^{b} x_i$ that specifies the endpoint of the summation.

Empty Sum

A summation where the upper bound $b$ is less than the lower bound $a$ ($b < a$), which by definition equals $0$.

Index Shifting

The process of renaming and adjusting the bounds of a summation index to make the sum more convenient to work with, such as substituting $j$ for $i-1$.

Scope of a Summation

The extent of a summation expression, which ends at the first addition or subtraction symbol not enclosed in parentheses or part of a larger term (like a numerator).

Einstein Summation Convention

A notation proposed by Albert Einstein where the summation symbol ($\sum$) is omitted entirely in certain special types of sums.

Infinite Sum

The limit of a series obtained by taking the sum of the first $n$ terms as $n$ approaches infinity, which converges to $x$ if the values stay within $\epsilon$ of $x$ for all $n > N$.

Double Sum

Two nested summations that sum an innermost expression over all pairs of values of the two indices, analogous to nested for loops.

Sum of a Constant

The standard formula $\sum_{i=1}^{n} 1 = n$.

Arithmetic Series

A summation where the difference between adjacent terms is constant, with the simplest form being $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Geometric Series

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

Infinite Geometric Series

A series that converges to $\frac{1}{1-r}$ when $|r| < 1$.

Harmonic Series

The sum of the inverses of consecutive integers, $\sum_{i=1}^{n} \frac{1}{i}$, denoted as $H_n$ and approximated as $\Theta(\log(n))$.

Linearity of Summation

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

Integral Technique

A method for bounding a non-decreasing function $f(n)$ where $\int_{a-1}^b f(x)dx \le \sum_{i=a}^b f(i) \le \int_a^{b+1} f(x)dx$.

Product (Pi Notation)

The multiplication of a series of values ($\prod_{i=1}^{n} i$), such as in the definition of the factorial function $n!$.

Empty Product

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

Big AND (\bigwedge)

A large operator for logical conjunction ($\forall x \in S : P(x)$) which returns True for an empty index set.

Big OR (\bigvee)

A large operator for logical disjunction ($\exists x \in S : P(x)$) which returns False for an empty index set.

Big Intersection (\bigcap)

A large operator for the set intersection of a collection of sets; it is generally undefined for an empty collection.

Big Union (\bigcup)

A large operator for the set union of a collection of sets; it returns the empty set for an empty index set.