Notes on Summations and Related Topics

Flashcards covering the definitions, notation, identities, and calculation strategies for summations and products based on 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$ used in a summation; $a$ is the lower bound or lower limit, and $b$ is the upper bound or upper limit.

Empty sum rule

If the upper bound is less than the lower bound ($b < a$), the sum is defined to be $0$.

Summation scope

Extends to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term, such as a fraction numerator.

Finite sum formal definition

Defined by the recurrence $\sum_{i=a}^b f(i) = f(b) + \sum_{i=a}^{b-1} f(i)$ if $b \ge a$, and $0$ if $b < a$.

Sums over index sets

A summation where indices are members of a given set or satisfy a specific predicate, written by replacing limits with a single subscript (e.g., $\sum_{i \in \{3,5,7\}} i^2$).

Einstein summation convention

A practice used by theoretical physicists where the summation symbol ($\sum_i$) is omitted entirely in certain special types of sums.

Infinite sum

Defined as the limit of the series $s$ obtained by summing terms sequentially; it converges to $x$ if for any $\epsilon > 0$, there exists an $N$ such that $|s_n - x| < \epsilon$ for all $n > N$.

Double sums

Two nested summations, similar to nested for loops, where the innermost expression is summed over all pairs of values of the two indices.

Standard sum of a constant

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

Arithmetic series (simplest form)

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

Geometric series

A sum where the ratio between adjacent terms is constant; the finite form is $\sum_{i=0}^n r^i = \frac{1 - r^{n+1}}{1 - r}$, and the infinite form for $|r| < 1$ is $\frac{1}{1 - r}$.

Summation linearity

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

Harmonic series

The series $\sum_{i=1}^n \frac{1}{i} = H_n$, which is characterized as $\Theta(n \log n)$ in the provided text.

Guess but verify method

A technique for computing sums by writing out values for the first few upper limits, identifying a pattern (sequence), and proving it via induction.

Factorial function

A product of a series of values for non-negative $n$, defined as $n! = \prod_{i=1}^n i = 1 \times 2 \times \dots \times n$.

Empty product rule

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

Big OR summation

An aggregate operator spanning a series represented as $\bigvee_{x \in S} P(x)$, which returns False (the identity element) for an empty index set.