Summations and Related Topics Flashcards

A set of vocabulary flashcards covering the notation, terminology, identities, and common formulas for summations and products as presented in the lecture notes.

Summations

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

Index of Summation

The variable $i$ in the notation $\sum_{i=a}^{b} x_i$ that loops through all values from the lower limit to the upper limit.

Lower Bound (Lower Limit)

The value $a$ in the summation $\sum_{i=a}^{b} x_i$ representing the start of the index range.

Upper Bound (Upper Limit)

The value $b$ in the summation $\sum_{i=a}^{b} x_i$ representing the end of the index range.

Empty Sum

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

Scope of a Summation

The extent of the expression being summed, which continues until the first addition or subtraction symbol not enclosed in parentheses or part of a larger term.

Index Set

A set of values or a predicate used to define the indices to be summed, written replacing the limits with a single subscript (e.g., $\sum_{i \in \{3, 5, 7\}} i^2$).

Einstein Summation Convention

A notation style used by theoretical physicists where the summation symbol $\sum_{i}$ is omitted entirely for special types of sums.

Infinite Sum

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

Double Sum

A summation where the expression inside is another summation, effectively acting like two nested for loops, such as $\sum_{i=1}^{a} \sum_{j=1}^{b} 1$ to define $a \times b$.

Arithmetic Series (Simple)

A sum where the difference between adjacent terms is constant, represented by the formula $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$.

Geometric Series

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}$.

Harmonic Series

The sum of the reciprocals of the first $n$ integers, written as $H_n = \sum_{i=1}^{n} \frac{1}{i}$, which is approximated as $\Theta(\ln(n))$.

Linearity of Summation

A 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$).

Guess but Verify Method

A technique for solving sums where one writes out initial values, guesses a closed-form formula, and proves it using induction.

Product Notation

The use of the capital Greek letter pi $\prod$ to represent multiplying a series of values, such as $n! = \prod_{i=1}^{n} i$.

Empty Product

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

Big AND ($\bigwedge$)

A logical operator over a set $S$ defined as $\forall x \in S : P(x)$; its identity element for an empty set is $\text{True}$.

Big OR ($\bigvee$)

A logical operator over a set $S$ defined as $\exists x \in S : P(x)$; its identity element for an empty set is $\text{False}$.

Big Intersection ($\bigcap$)

An aggregate operator for sets that is undefined over an empty collection because there is no general identity element.