Summations and Related Topics Practice Flashcards

Flashcards covering vocabulary and core concepts of summations, standard series formulas, and other big operators like products and logical quantifiers based on James Aspnes' lecture notes.

Summation

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

Index of summation

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

Lower bound (lower limit)

The value $a$ in the expression \text{\textsum}_{i=a}^b x_i representing the start of the summation loop.

Upper bound (upper limit)

The value $b$ in the expression \text{\textsum}_{i=a}^b x_i representing the end of the summation loop.

Empty sum

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

Scope of a summation

The range of terms included in a sum, extending to the first addition or subtraction symbol not enclosed in parentheses or part of a larger term such as a fraction numerator.

Index set

A set of values (not necessarily consecutive integers) over which an expression is summed, written using a single subscript under the sigma as in \text{\textsum}_{i \text{\textin} S} x_i.

Einstein summation convention

A notation proposed by Albert Einstein where the summation symbol \text{\textsum} is omitted entirely in certain special types of sums.

Infinite sum

The limit of a series $s$ obtained by summing the first term, then the first two terms, then the first three, and so on; it converges 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

An expression where one summation is inside another, acting like two nested for loops and summing the innermost expression over all pairs of index values.

Arithmetic series (simplest)

The sum of the first $n$ positive integers, \text{\textsum}_{i=1}^n i = \frac{n(n+1)}{2}.

Finite geometric series

A sum where the ratio between adjacent terms is constant, expressed by the formula \text{\textsum}_{i=0}^n r^i = \frac{1 - r^{n+1}}{1 - r}.

Infinite geometric series

A series that converges when $|r| < 1$ to the value \text{\textsum}_{i=0}^{\text{\textinfty}} r^i = \frac{1}{1 - r}.

Harmonic series

The sum \text{\textsum}_{i=1}^n \frac{1}{i}, denoted as $H_n$, which the text identifies as \text{\textTheta}(n \text{\textlog}(n)).

Linearity of summations

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

Factorial function ($n!$)

A product of a series of values defined for non-negative integers as \text{\textprod}_{i=1}^n i = 1 \text{\texttimes} 2 \text{\texttimes} \text{...} \text{\texttimes} n.

Empty product

A product taken over an empty set, which is defined to have the value $1$, the identity element for multiplication.

Big AND (\text{\textbigwedge})

A logical operator that computes the conjunction over a series, equivalent to the universal quantifier \text{\textforall} x \text{\textin} S : P(x), returning True for an empty index set.

Big OR (\text{\textbigvee})

A logical operator that computes the disjunction over a series, equivalent to the existential quantifier \text{\textexists} x \text{\textin} S : P(x), returning False for an empty index set.

Big Intersection (\text{\textbigcap})

An operator that computes the intersection of a collection of sets A_1 \text{\textcap} A_2 \text{\textcap} \text{...} \text{\textcap} A_n; it is undefined for an empty collection of sets.

Big Union (\text{\textbigcup})

An operator that computes the union of a collection of sets A_1 \text{\textcup} A_2 \text{\textcup} \text{...} \text{\textcup} A_n, returning the empty set for an empty collection.