Sequences, Sums and Closed Forms

A sequence is simply a list of numbers in a definite order: a first one, a second one, and so on. All we're really talking about here are the two simplest ways such a list can grow: by adding the same amount each time (an arithmetic sequence), or by multiplying by the same amount each time (a geometric sequence, named because each term is the geometric mean of its neighbors). The formulas look like a wall of symbols, but they're tiny: $a_n = a_0 + dn$ (start at $a_0$, add $d$ a total of $n$ times) and $g_n = g_0q^n$ (start at $g_0$, multiply by $q$ a total of $n$ times). The sum formula on the right is just a shortcut so you don't have to add a thousand terms by hand. Bear with the notation; each piece is something you already know how to do.

Sigma notation packs a sum into one symbol: $\sum_{k=1}^{n} k$ means $1 + 2 + \cdots + n$.

Arithmetic sums. Pair the first term with the last, the second with the second-to-last, and so on. Moving inward, one term goes up by $d$ and the other goes down by $d$, so every pair has the same total. That means the sum is (number of terms) × (first + last) / 2, or in other words, the number of terms times the average term. For $3 + 7 + 11 + \cdots + 99$ (25 terms), that's $25 \cdot 102 / 2 = 1275$.

Geometric sums. Pairing doesn't help here, but a different trick does. Write $S = g_0 + g_0q + \cdots + g_0q^{n-1}$. Multiplying by $q$ shifts every term one place over, so $qS$ and $S$ share all but their end terms. Subtract and almost everything cancels: $qS - S = g_0q^n - g_0$, which gives the formula above. With doubling, $1 + 2 + 4 + \cdots + 2^9 = 2^{10} - 1 = 1023$.

Infinite geometric series. When $|q| < 1$, the $q^n$ in the formula goes to $0$, so the sum settles down: $\sum_{k=0}^{\infty} g_0q^k = \frac{g_0}{1 - q}$. That's why $1 + \frac12 + \frac14 + \cdots = 2$. Each term covers half the remaining distance to 2.

Arithmetic sequences grow linearly, while geometric ones with $q > 1$ grow exponentially and eventually beat any arithmetic sequence. That gap between linear and exponential growth comes back later in the course, when we compare how fast algorithms run.

Loan payments, compound interest and the running time of loops are sums of arithmetic or geometric sequences.