Discrete Summations and Products Lecture Notes

This set of flashcards covers vocabulary and formal definitions related to summation notation, standard series formulas, identities, and big operators as presented in the lecture notes.

Summation

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

Index of summation

The variable $i$ in \text{\textsum}_{i=a}^b x_i that iterates through all values from the lower bound to the upper bound.

Lower bound (lower limit)

The starting value $a$ in a summation notation.

Upper bound (upper limit)

The ending value $b$ in a summation notation.

Empty sum

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

Scope

The extent of a summation symbol, which continues until the first addition or subtraction symbol not enclosed in parentheses or part of a larger term like a fraction numerator.

Index set

A specific set or predicate used to define which indices are included in a summation, especially when they are not consecutive integers.

Einstein summation convention

A notation style used in theoretical physics where the summation symbol is omitted entirely for specific types of sums.

Infinite sum

The limit of a series of partial sums $s_n$ as $n$ approaches infinity, converging to $x$ if for any \text{\textepsilon} > 0, there exists an $N$ such that for all $n > N$, |s_n - x| < \text{\textepsilon}.

Double sum

Nested summations representing two nested for loops, summing the innermost expression over all pairs of values of the two indices.

Arithmetic series

A series where the difference between adjacent terms is constant, with the simplest form being \text{\textsum}_{i=1}^n i = \frac{n(n+1)}{2}, which equals $n$ times the average value $\frac{n+1}{2}$.

Geometric series

A series where the ratio between adjacent terms is constant, with the finite form \text{\textsum}_{i=0}^n r^i = \frac{1 - r^{n+1}}{1 - r}.

Harmonic series

The series \text{\textsum}_{i=1}^n 1/i, also known as the $n\text{-th}$ harmonic number $H_n$, which is \text{\textTheta}(n \text{ log } n).

Linearity of summation

The property allowing constant factors to be pulled out (\text{\textsum} a x_i = a \text{\textsum} x_i) and sums inside summations to be split (\text{\textsum} (x_i + y_i) = \text{\textsum} x_i + \text{\textsum} y_i).

Guess but verify method

A technique for identifying the value of a sum by writing out the first few values of the upper limit to find a pattern and then proving it by induction.

Product notation

An operation denoted by the Greek letter pi (\text{\textprod}) used to multiply a series of values, such as the factorial function n! = \text{\textprod}_{i=1}^n i.

Empty product

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

Big AND (logical conjunction)

An operator \text{\textbigwedge}_{x \text{\textin} S} P(x) that performs a logical AND over a series of predicates, returning True for an empty index set.

Big OR (logical disjunction)

An operator \text{\textbigvee}_{x \text{\textin} S} P(x) that performs a logical OR over a series of predicates, returning False for an empty index set.

Big Intersection

The operator \text{\textcap}_{i=1}^n A_i representing the intersection of multiple sets; it is undefined for an empty collection of sets.

Big Union

The operator \text{\textcup}_{i=1}^n A_i representing the union of multiple sets; it returns the empty set for an empty index set.