Summations, Products, and Big Operators

Vocabulary flashcards covering summations, series identities, estimation rules, big operators, empty evaluations, and systems of power sums.

Index of Summation

The variable in a summation (commonly $i$, $j$, or $k$) that iterates through each value from the lower limit to the upper limit.

Lower Limit

The starting boundary (denoted as $a$ in \begin{equation*}\sum_{i=a}^b x_i\end{equation*}) for the index variable in a summation.

Upper Limit

The ending boundary (denoted as $b$ in \begin{equation*}\sum_{i=a}^b x_i\end{equation*}) for the index variable in a summation.

Empty Sum

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

Scope of a Summation

The portion of a mathematical expression affected by the summation operator, which extends up to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term.

Einstein Summation Convention

A notation convention used in theoretical physics where the explicit summation symbol \begin{equation*}\sum_i\end{equation*} is omitted in certain repeated-index sums.

Infinite Sum Convergence

A property where the limit of partial sums $s_n$ approaches a value $x$ such that for any ̢ > 0, there exists an $N$ where |s_n - x| < ̢ for all $n > N$.

Double Sum

A summation nested inside another summation, equivalent to nested for-loops, that sums an inner expression over all pairs of index values.

Linearity of Summation

The algebraic property allowing constant factors to be factored out of sums ($\sum a x_i = a \sum x_i$) and additive terms to be split ($\sum (x_i + y_i) = \sum x_i + \sum y_i$).

Arithmetic Series

A sum of terms where the difference between consecutive terms is constant, exemplified by the identity $\sum_{i=1}^n i = \frac{n(n + 1)}{2}$.

Geometric Series

A sum of terms with a constant ratio between adjacent terms, evaluated as $\sum_{i=0}^n r^i = \frac{1 - r^{n+1}}{1 - r}$ for finite sums, or $\sum_{i=0}^{\infty} r^i = \frac{1}{1 - r}$ when $|r| < 1$.

Harmonic Series

The sum of reciprocals of positive integers, denoted as $\sum_{i=1}^n \frac{1}{i} = H_n$, which has an asymptotic order of growth of $\Theta(n \log(n))$ when multiplied by $n$ as $\sum_{i=1}^n \frac{n}{i}$.

Guess but Verify Method

A strategy for evaluating summations by calculating initial values to identify a pattern, forming a candidate closed-form solution, and verifying it by mathematical induction.

Integral Bounding Technique

A method to bound non-decreasing discrete sums using definite integrals, given by $\int_{a-1}^b f(x)\,dx \le \sum_{i=a}^b f(i) \le \int_a^{b+1} f(x)\,dx$.

Empty Product

A product over an empty set of indices, defined to equal $1$ because $1$ is the identity element for multiplication.

Big AND Operator

An aggregate logical operator $\bigwedge_{x \in S} P(x)$ computing conjunction across a set, which returns $\text{True}$ when evaluated over an empty index set.

Big OR Operator

An aggregate logical operator $\bigvee_{x \in S} P(x)$ computing disjunction across a set, which returns $\text{False}$ when evaluated over an empty index set.

Big Intersection Operator

An aggregate set operator $\bigcap_{i=1}^n A_i$ computing the common elements of sets, which is undefined when evaluated over an empty collection of sets.

Big Union Operator

An aggregate set operator $\bigcup_{i=1}^n A_i$ combining elements across sets, which returns the empty set $\emptyset$ when evaluated over an empty collection.

System of Power Sums

A set of symmetric polynomial equations involving sums of powers of variables, such as $a + b + c = 4$, $a^2 + b^2 + c^2 = 10$, and $a^3 + b^3 + c^3 = 22$.