Summations and Related Topics Practice Flashcards

Vocabulary flashcards covering the definitions, notation, and standard formulas for summations, products, and related mathematical operators based on the lecture notes.

Summations

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

Index of summation

The variable $i$ in a summation formula that loops through all values from the lower bound to the upper bound.

Lower bound (lower limit)

The starting value $a$ for the index of summation $i$.

Upper bound (upper limit)

The ending value $b$ for the index of summation $i$, including the endpoint.

Empty Sum

A sum where the upper bound $b$ is less than the lower bound $a$ ($b < a$); by definition, its value is $0$.

Scope of a summation

The extent of the sum, which lasts until 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 used by theoretical physicists where the $\sum_i$ part is omitted entirely in certain special types of sums.

Infinite sum convergence

A sum $\sum_{i=0}^{\infty} a_i$ converges to a value $x$ 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 sums

Nested summations that act like nested for loops, summing the innermost expression over all pairs of values of the two indices.

Constant series formula

$\sum_{i=1}^{n} 1 = n$.

Arithmetic series formula (simple)

$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Geometric series formula (finite)

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

Geometric series formula (infinite)

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

Linearity of summation

The property allowing constant factors to be pulled out ($\sum a x_i = a \sum x_i$) and internal sums to 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 $\Theta(n \log n)$ according to the notes.

Factorial function ($n!$)

Defined for non-negative integers as the product $\prod_{i=1}^{n} i = 1 \cdot 2 \cdot \text{...} \cdot n$.

Empty product

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

Big AND (\bigwedge)

An operator for a series of predicates $\bigwedge_{x \in S} P(x)$, equivalent to $\forall x \in S : P(x)$; returns $True$ for an empty set.

Big OR (\bigvee)

An operator for a series of predicates $\bigvee_{x \in S} P(x)$, equivalent to $\exists x \in S : P(x)$; returns $False$ for an empty set.

Big Intersection (\bigcap)

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