Summations and Related Topics Flashcards

Flashcards covering the definitions, formulas, and rules for summations, products, and other big operators like big AND/OR and set operations.

Summations

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

Index of summation

The variable (e.g., $i$) used in a summation that loops through all values from the lower bound to the upper bound.

Lower bound

The starting value of the index of summation, also known as the lower limit.

Upper bound

The ending value of the index of summation, also known as the upper limit.

Empty sum

A summation where the upper bound $b$ is less than the lower bound $a$, which is defined to have the value $0$. For example, $\sum_{i=0}^{-5} \frac{2^i \tan(i)}{i^3} = 0$.

Scope of a summation

Extends to the first addition or subtraction symbol that is not enclosed in parentheses or part of a larger term like a fraction numerator.

Einstein summation convention

A technique used by theoretical physicists where the summation symbol $\sum_i$ is left out entirely in certain types of sums.

Infinite sum

The limit of a series $s$ obtained by adding terms one by one; 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

A summation where the expression inside is another summation, functioning like two nested for loops.

Standard arithmetic series formula

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

Standard geometric series formula

$\sum_{i=0}^{n} r^i = \frac{1-r^{n+1}}{1-r}$, valid even when $r > 1$, but not for $r = 1$.

Infinite geometric series formula

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

Linearity of summation

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

Harmonic series

$\sum_{i=1}^{n} 1/i = H_n = \Theta(n \log n)$, according to the provided lecture notes.

Factorial function (product notation)

$n! ≔ \prod_{i=1}^{n} i = 1 \times 2 \times ··· \times n$.

Empty product

Defined to have the value $1$, which is the identity element for multiplication.

Big AND

$\bigwedge_{x \in S} P(x) \equiv \forall x \in S : P(x)$. Its identity element for an empty index set is True.

Big OR

$\bigvee_{x \in S} P(x) \equiv \exists x \in S : P(x)$. Its identity element for an empty index set is False.

Big Intersection

$\bigcap_{i=1}^{n} A_i = A_1 \cap A_2 \cap ··· \cap A_n$. It is undefined over an empty collection of sets as there is no identity element.

Big Union

$\bigcup_{i=1}^{n} A_i = A_1 \cup A_2 \cup ··· \cup A_n$. Its identity element is the empty set.