Summations and Related Topics Flashcards

This set of vocabulary flashcards covers fundamental concepts of summations, standard summation formulas, strategies for computing or bounding sums, and other large operators like products and logical quantifiers.

Summation

The discrete version of an integral, written as $\sum_{i=a}^b x_i$, representing the sum of a sequence $x_a, x_{a+1}, \text{...}, x_b$.

Index of summation

The variable (typically $i$, $j$, or $k$) that loops through all values from the lower bound to the upper bound within a summation.

Lower bound (Lower limit)

The starting value specified at the bottom of the summation symbol (denoted as $a$ in $\sum_{i=a}^b x_i$).

Upper bound (Upper limit)

The ending value specified at the top of the summation symbol (denoted as $b$ in $\sum_{i=a}^b x_i$).

Empty sum

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

Scope of a summation

The reach of the summation operator, which extends to 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 proposed by Albert Einstein where the summation symbol ($\Sigma$) is left out entirely in certain special types of sums.

Infinite sum

The limit of the sequence of partial sums $s_n$; 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 that sum over all pairs of indices.

Linearity (Summation operator)

The property allowing constant factors to be pulled out ($\sum ax_i = a \times \sum x_i$) and internal sums to be split ($\sum (x_i + y_i) = \sum x_i + \sum y_i$).

Standard arithmetic series formula

$\sum_{i=1}^n i = \frac{n(n + 1)}{2}$, which can be derived by adding two copies of the sequence in opposite directions.

Standard geometric series formula

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

Sum of a constant series

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

Harmonic series ($H_n$)

The sum $\sum_{i=1}^n \frac{1}{i}$, which has an asymptotic growth rate of $\Theta(\text{log}(n))$.

Guess but verify method

A technique for identifying a closed-form expression for a sum by writing out the first few values and using induction to prove the observed pattern.

Integral trick for bounding sums

A strategy for non-decreasing functions where $\int_{a-1}^b f(x)dx \leq \sum_{i=a}^b f(i) \leq \int_a^{b+1} f(x)dx$ to obtain big-Theta bounds.

Product notation

Notation using the capital Greek letter pi ($\Pi$) to represent multiplying a series of values.

Factorial function ($n!$)

Defined for non-negative integers as the product $\prod_{i=1}^n i = 1 \times 2 \times \text{...} \times n$, where $0! = 1$.

Empty product

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

Big AND ($\bigwedge$)

A logical operator computing a conjunction over a series, equivalent to the universal quantifier ($\forall x \in S : P(x)$).

Big OR ($\bigvee$)

A logical operator computing a disjunction over a series, equivalent to the existential quantifier ($\exists x \in S : P(x)$).

Identity element for Big AND

True (the value returned when the index set is empty).

Identity element for Big OR

False (the value returned when the index set is empty).