You put $1{,}000 into an account paying 4% interest per year. What is the balance after 1 year, 2 years, 10 years? A ball is dropped from 10 m and each bounce reaches 60% of the previous height. How high is the seventh bounce? A theatre has 20 seats in the front row and each row behind has 2 more. How many seats are in row 30?

Each question asks for one item in an ordered list of numbers that is generated by a rule. That list is a sequence, and the questions become: given the rule, find the nth item — and, later, add the items up.

Think of a sequence as an array that never ends, indexed by position: a[1], a[2], a[3], …​. The interesting thing is never the individual numbers; it is the rule that produces them. Once you know the rule, you can answer questions about item 1,000,000 without writing out the first 999,999.

There are two natural ways to state a rule, and programmers already know both:

Here is the same sequence, the perfect squares, described both ways:

Check the recursive version: \(a_2 = 1 + 3 = 4\), \(a_3 = 4 + 5 = 9\), \(a_4 = 9 + 7 = 16\). Each square is the previous square plus the next odd number. The explicit form is better for jumping straight to \(a_{1000} = 1{,}000{,}000\); the recursive form often reflects how the quantity actually arises — the bank adds interest to last year’s balance, the ball’s bounce depends on the previous bounce. Much of this chapter is about converting a recursive description (which is easy to write down from a story) into an explicit one (which is easy to compute and reason about).

Find an explicit formula for \(2, 5, 10, 17, 26, \ldots\).

Step 1 — look at differences. \(5-2=3,\ 10-5=5,\ 17-10=7,\ 26-17=9\). The differences are consecutive odd numbers, which is the signature of squares (as we just saw).

Step 2 — compare with \(n^2\). For \(n = 1,2,3,4,5\): \(n^2 = 1, 4, 9, 16, 25\). Each given term is exactly one more.

Step 3 — state and check. \(a_n = n^2 + 1\). Check \(n = 4\): \(16 + 1 = 17\). ✓

The theatre (20 seats in row 1, two more each row) and the savings account (multiply by 1.04 each year) are the two prototypes. We want explicit formulas for both.

For an arithmetic sequence, getting from term 1 to term \(n\) takes \(n-1\) steps, each adding \(d\):

The "\(n-1\)" is the classic fence-post count: \(n\) posts, \(n-1\) gaps. For a geometric sequence the same unrolling multiplies instead of adds, giving \(a_n = a_1 r^{n-1}\).

Seen as functions of \(n\), an arithmetic sequence is a linear function sampled at whole numbers (slope \(d\)), and a geometric sequence is an exponential function sampled at whole numbers (base \(r\)). The picture makes the difference unforgettable.

Theatre seats. \(a_1 = 20\), \(d = 2\). Row 30 has

Which term? In \(7, 11, 15, 19, \ldots\), is 203 a term, and if so which one? Here \(d = 4\), so \(a_n = 7 + 4(n-1) = 4n + 3\). Solve \(4n + 3 = 203\): \(4n = 200\), \(n = 50\). Yes, 203 is the 50th term. (If solving had given a non-integer \(n\), the number would not be in the sequence.)

Bouncing ball. The first bounce reaches 6 m (60% of 10 m), so \(a_1 = 6\), \(r = 0.6\). The seventh bounce reaches

How many years to double? At 4% per year, the balance after \(n\) years is \(1000 \cdot 1.04^{n}\) (indexing from \(n = 0\), the initial deposit). Doubling means \(1.04^{n} = 2\), so, taking logarithms (Chapter 12),

so the balance first exceeds $2,000 after 18 years.

Before adding up sequences we need a way to write a sum of many terms without ellipses and ambiguity. "\(1 + 4 + 9 + \cdots + 100\)" relies on the reader guessing the pattern. Mathematics has a precise, compact notation for this — and it is exactly a for loop.

Here is the notation in full:

Read it as "the sum, for \(i\) from 1 to \(n\), of \(x\) sub \(i\)". Each piece has a job:

So \(\sum_{i=1}^{n} x_i\) means \(x_1 + x_2 + \cdots + x_n\). The index steps by 1 from lower bound to upper bound; there is no "step" parameter.

Note the hi + 1: Python’s range excludes its end point, sigma includes it. That single fact causes most off-by-one errors when translating formulas into code.

Expand. \(\sum_{k=2}^{5} (2k - 1)\): the index runs over \(k = 2, 3, 4, 5\), giving \(3 + 5 + 7 + 9 = 24\).

Expand with an index that appears as an exponent. \(\sum_{j=0}^{4} 3^{j} = 3^0 + 3^1 + 3^2 + 3^3 + 3^4 = 1 + 3 + 9 + 27 + 81 = 121\).

Summand not depending on the index. \(\sum_{i=1}^{6} 5 = 5 + 5 + 5 + 5 + 5 + 5 = 30\). The summand is evaluated six times, even though it ignores \(i\).

Compress. Write \(\tfrac{1}{2} + \tfrac{1}{4} + \tfrac{1}{8} + \cdots + \tfrac{1}{1024}\) in sigma notation. The terms are \(\tfrac{1}{2^k}\) and \(1024 = 2^{10}\), so the sum is \(\sum_{k=1}^{10} \frac{1}{2^k}\).

Compress an alternating sum. \(1 - \tfrac{1}{2} + \tfrac{1}{3} - \tfrac{1}{4} + \tfrac{1}{5}\). The sign flips each term, which \((-1)^{k+1}\) does neatly (positive when \(k\) is odd): \(\sum_{k=1}^{5} \frac{(-1)^{k+1}}{k}\).

The same idea with multiplication uses capital pi, \(\Pi\), for "P" as in product:

The most famous example is the factorial: \(n! = \prod_{k=1}^{n} k\). Another, from probability (Chapter 29): the chance that \(n\) people all have different birthdays (ignoring leap years) is

which first falls below one-half at \(n = 23\) — the "birthday paradox".

Because a sum is just repeated addition, the ordinary laws of arithmetic give a handful of rules. Each one is the distributive, commutative, or associative law in disguise.

The first two together say that sigma is linear — the same property you will meet again for derivatives (Chapter 17), integrals (Chapter 19), expected values (Chapter 29), and matrices (Chapter 27).

Worked example. Evaluate \(\sum_{i=1}^{10} (3i + 2)\) using the rules and the fact (proved in the next section) that \(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\).

Check by brute force: the terms are \(5, 8, 11, \ldots, 32\); that is an arithmetic sequence of ten terms with first 5 and last 32, and (as we are about to see) its sum is \(10 \cdot \frac{5 + 32}{2} = 185\). ✓

Every average, total and score you have ever been given is a sigma expression.

A series is the sum of the terms of a sequence. The partial sum \(S_n = a_1 + a_2 + \cdots + a_n = \sum_{k=1}^{n} a_k\) answers questions such as "how many seats in the whole theatre?" or "how many operations does this loop perform?" Adding the terms one at a time is fine for ten terms and hopeless for a million. We want a closed form.

The story (possibly embellished) is that the young Carl Friedrich Gauss, told to add the numbers 1 to 100 as busywork, wrote down 5050 almost immediately. The trick: pair the first and last terms, the second and second-to-last, and so on.

Fifty pairs, each summing to 101, total 5050.

Pairing is fiddly when \(n\) is odd (one number is left unpaired). A cleaner version writes the sum forwards and backwards and adds the two lines:

The picture is even more convincing: a staircase of blocks of heights \(1, 2, \ldots, n\), plus a copy turned upside down, fills an \(n \times (n+1)\) rectangle exactly.

The same "write it twice" argument works for any arithmetic series, because in an arithmetic sequence the first plus the last equals the second plus the second-to-last, and so on (each step forward adds \(d\) to one and subtracts \(d\) from the other):

In words: number of terms times the average of the first and last term. That phrasing is easy to remember and hard to misuse.

The whole theatre. 30 rows, \(a_1 = 20\), \(a_{30} = 78\) (found earlier):

Odd numbers. The sum of the first \(n\) odd numbers \(1 + 3 + 5 + \cdots + (2n-1)\): here \(a_1 = 1\), \(a_n = 2n - 1\), so

confirming the "squares are sums of odd numbers" pattern from the start of the chapter.

Sum of multiples. Sum all multiples of 7 between 100 and 500. The first is \(105 = 7\cdot 15\), the last is \(497 = 7 \cdot 71\). Number of terms: \(71 - 15 + 1 = 57\). Sum: \(\frac{57\,(105 + 497)}{2} = \frac{57 \times 602}{2} = 57 \times 301 = 17{,}157\).

Gauss’s formula is the first of a family. Others you will occasionally need:

For example \(\sum_{k=1}^{100} k^2 = \frac{100 \cdot 101 \cdot 201}{6} = 338{,}350\). These are best verified by induction (Chapter 22) rather than derived here. For algorithm analysis the takeaway is the pattern: summing \(k^p\) up to \(n\) gives something that grows like \(\frac{n^{p+1}}{p+1}\) — the discrete cousin of \(\int x^p\,dx = \frac{x^{p+1}}{p+1}\) (Chapter 19).

You deposit $100 at the end of every year into an account paying 5% annually. How much is there after 10 years? The deposit made at the end of year 10 has earned nothing; the one from year 9 has earned one year’s interest, and so on back to the first deposit, which has earned 9 years. The total is

a geometric series. Gauss’s pairing trick does nothing here — the terms do not pair to a constant. We need a different idea.

Multiplying a geometric series by its ratio \(r\) shifts every term one place along. Subtracting the shifted copy from the original then cancels almost everything. Let

This is one of the most useful formulas in mathematics. In sigma notation:

The two forms are the same (multiply top and bottom by \(-1\)); use the second when \(r > 1\) to keep things positive. If \(r = 1\) every term is \(a\) and the sum is simply \(na\).

Savings (an annuity). \(a = 100\), \(r = 1.05\), \(n = 10\):

You deposited $1,000; the other $257.79 is interest on interest.

Powers of two. \(1 + 2 + 4 + \cdots + 2^{n-1}\) has \(a = 1\), \(r = 2\):

So \(1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 = 255 = 2^8 - 1\). Every programmer knows this one in disguise: the largest unsigned 8-bit number, binary 11111111, is \(2^8 - 1\). Notice also that the sum of all the earlier powers of two is one less than the next power. That fact is the engine behind the dynamic-array analysis later in the chapter.

Alternating ratio. \(5 - 2.5 + 1.25 - 0.625 + \cdots\) to 7 terms: \(a = 5\), \(r = -0.5\), \(n = 7\). \((-0.5)^7 = -0.0078125\), so

matching the Python output above.

Around 450 BCE Zeno of Elea argued that motion is impossible. To walk to a wall you must first cover half the distance, then half of what remains, then half of that, and so on — infinitely many tasks. How can infinitely many tasks ever be completed?

In numbers: the distances are \(\tfrac12, \tfrac14, \tfrac18, \ldots\) of the total, and the question becomes whether

can sensibly have a value. The picture strongly suggests the answer is 1: the pieces tile a unit square ever more completely.

We cannot literally perform infinitely many additions. What we can do is look at the partial sums and see whether they settle down:

The gap halves each time. It never becomes exactly zero, but it becomes smaller than any positive tolerance you care to name. That is what we mean when we say the infinite sum equals 1: not that we finish adding, but that the partial sums converge to 1.

The finite formula already contains the answer. For \(n\) terms,

If \(|r| < 1\), then \(r^{n}\) shrinks towards 0 as \(n\) grows (each multiplication by \(r\) makes it smaller in size). So \(S_n\) approaches \(a \cdot \frac{1 - 0}{1 - r}\):

If \(|r| \ge 1\), \(r^n\) does not shrink, and the partial sums either grow without bound (\(r \ge 1\)), alternate with growing size (\(r < -1\)), or bounce between two values forever (\(r = -1\)). In all these cases the infinite series has no value; we say it diverges.

The phrase "approaches as \(n\) grows" is the idea of a limit, made precise in Chapter 16. For now the intuitive meaning — "gets and stays as close as you like" — is enough.

Zeno. \(a = \tfrac12\), \(r = \tfrac12\): \(\frac{1/2}{1 - 1/2} = 1\). ✓

0.999… = 1. The repeating decimal \(0.\overline{9}\) means the series

Not "infinitely close to 1", not "1 minus a tiny bit": exactly 1. The partial sums \(0.9, 0.99, 0.999, \ldots\) fall short by \(\tfrac{1}{10}, \tfrac{1}{100}, \tfrac{1}{1000}, \ldots\), and the only number they approach is 1.

Repeating decimals to fractions. \(0.\overline{27} = 0.272727\ldots = \frac{27}{100} + \frac{27}{100^2} + \cdots\):

This is why every repeating decimal is a rational number (Chapter 1).

The bouncing ball, all the way. Dropped from 10 m, rebounding to 60% each time. The ball falls 10 m, then rises and falls 6 m, rises and falls 3.6 m, and so on:

Achilles and the tortoise. Achilles runs 10 times as fast as a tortoise that starts 100 m ahead. By the time Achilles reaches the tortoise’s start, it has moved 10 m; when he covers that, it has moved 1 m; and so on. Achilles runs \(100 + 10 + 1 + 0.1 + \cdots = \frac{100}{1 - 0.1} = 111.\overline{1}\) m before drawing level — a finite distance, covered in a finite time. Zeno’s infinitely many tasks fit inside a finite total.

The geometric series is unusually friendly: we have an exact formula for its partial sums. Most series are not like that. Given \(\sum a_k\), how can we tell whether it converges without a closed form? A full answer belongs to a calculus course, but two facts take you a long way, and one famous example is essential culture.

If a series converges, its partial sums settle down, so consecutive partial sums get very close together. But \(S_n - S_{n-1} = a_n\). So if \(\sum a_k\) converges, then \(a_k \to 0\). Turned around:

For example, \(\sum_{k=1}^{\infty} \frac{k}{k+1} = \frac12 + \frac23 + \frac34 + \cdots\) diverges, since the terms approach 1: you keep adding almost 1 forever.

The test is one-directional. Terms going to zero is necessary but not sufficient, and the harmonic series is the example everyone should know.

The terms shrink to zero. Surely the sum converges? Compute: after 10 terms it is about 2.93; after 100, about 5.19; after a million, about 14.39. It is growing, but painfully slowly. Is there a ceiling?

There is not. The proof, due to Nicole Oresme around 1350, is a model of how to bound something you cannot compute: group the terms into blocks that each add up to at least one half.

Block \(m\) contains the \(2^{m-1}\) terms from \(\frac{1}{2^{m-1}+1}\) to \(\frac{1}{2^m}\); each is at least \(\frac{1}{2^m}\), so the block is at least \(2^{m-1}\cdot\frac{1}{2^m} = \frac12\). Adding infinitely many halves exceeds every bound, so the harmonic series diverges. More precisely, the first \(2^m\) terms sum to at least \(1 + \frac{m}{2}\).

The partial sums \(H_n = \sum_{k=1}^{n} \frac1k\) (the harmonic numbers) grow like the natural logarithm: \(H_n \approx \ln n + 0.5772\), where 0.5772… is the Euler–Mascheroni constant \(\gamma\). The reason will be clear once you know that \(\int_1^n \frac{dx}{x} = \ln n\) (Chapter 19). To push the sum past 10 you need more than twelve thousand terms:

To pass 100 you would need about \(e^{99.42} \approx 1.5 \times 10^{43}\) terms. Divergent, but only just.

The harmonic proof used an idea worth naming. For series with positive terms, partial sums only go up, so there are just two possibilities: they grow without bound, or they are capped and settle to a limit. Hence the comparison test: if \(0 \le a_k \le b_k\) for every \(k\) and \(\sum b_k\) converges, then \(\sum a_k\) converges too (it is capped by the same ceiling). If \(a_k \ge b_k \ge 0\) and \(\sum b_k\) diverges, so does \(\sum a_k\).

Example. Does \(\sum_{k=1}^{\infty} \frac{1}{2^k + k}\) converge? Each term is smaller than \(\frac{1}{2^k}\), and \(\sum \frac{1}{2^k} = 1\). So yes, and its sum is less than 1.

The harmonic numbers \(H_n\) turn up wherever you wait for "the last one of \(n\)".

Many sequences arise naturally as recurrences, and for many of them no one hands you an explicit formula. The Tower of Hanoi puzzle moves \(n\) disks between three pegs, never placing a larger disk on a smaller. To move \(n\) disks you must move the top \(n-1\) out of the way, move the largest disk, and then move the \(n-1\) back on top. So the minimum number of moves \(h_n\) satisfies

How many moves for 64 disks? You do not want to iterate 64 times by hand, and you certainly want to know the growth rate.

Substitute the recurrence into itself repeatedly:

Check: \(h_1 = 1\), \(h_2 = 3\), \(h_3 = 7\). ✓ For 64 disks, \(2^{64} - 1 \approx 1.8 \times 10^{19}\) moves; at one per second that is about 585 billion years. Notice how the geometric series appeared in the middle of the unrolling — this happens constantly.

If you suspect a form, check it satisfies both the recurrence and the initial condition. Guess \(h_n = 2^n - 1\): then \(2h_{n-1} + 1 = 2(2^{n-1} - 1) + 1 = 2^n - 2 + 1 = 2^n - 1 = h_n\) ✓, and \(h_1 = 2 - 1 = 1\) ✓. This "verify" step is essentially a proof by induction (Chapter 22).

The most famous recurrence is second order:

giving \(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots\). Leonardo of Pisa (Fibonacci) introduced it in 1202 as an idealised rabbit-breeding puzzle, but it turns up in plant spirals, in the analysis of Euclid’s algorithm (Chapter 23), and in counting problems: \(F_{n+1}\) is the number of ways to tile a \(1 \times n\) strip with squares and dominoes.

Ratios of consecutive terms. Compute \(F_{n+1}/F_n\): \(1, 2, 1.5, 1.667, 1.6, 1.625, 1.615, 1.619, 1.6176, 1.6182, \ldots\) The ratios settle to a limit. If the ratio approaches some \(\varphi\), then for large \(n\), \(F_n \approx \varphi F_{n-1}\) and \(F_{n-1} \approx \varphi F_{n-2}\); substituting into the recurrence and dividing by \(F_{n-2}\):

(The quadratic formula is derived in Chapter 8.) This is the golden ratio. The same quadratic (called the characteristic equation) leads to the exact closed form, Binet’s formula:

Since \(|\psi| < 1\), the \(\psi^n\) term shrinks to nothing, and \(F_n\) is simply \(\varphi^n/\sqrt5\) rounded to the nearest integer. For instance, \(\varphi^{20}/\sqrt5 \approx 6765.00003\), and \(F_{20} = 6765\). The upshot: Fibonacci numbers grow exponentially, by a factor of about 1.618 per step. (The general technique for linear recurrences, using the characteristic equation, is best seen through eigenvalues: Chapter 28.)

A population of fish is 2,000. Each year it grows by 10% and then 150 fish are harvested. Find a formula for the population \(p_n\) after \(n\) years.

Set up. \(p_0 = 2000\), \(p_n = 1.1\,p_{n-1} - 150\).

Unroll.

Check. \(p_0 = 500 + 1500 = 2000\) ✓. \(p_1 = 1.1(2000) - 150 = 2050\); formula: \(550 + 1500 = 2050\) ✓.

Interpret. 1500 is the equilibrium (if \(p = 1500\), then \(1.1p - 150 = 1500\) again). Starting above it, the population grows exponentially away from it; starting below it, the harvest would drive the population to zero. A single closed form reveals behaviour the recurrence hides.

The running time of a loop is the sum, over iterations, of the work done in each iteration. Consider checking every unordered pair of \(n\) items (for duplicate detection, collision tests, or a naive closest-pair search):

Translate the loop into a sum. For a fixed \(i\), the inner loop runs for \(j = i+1, \ldots, n-1\), which is \(n - 1 - i\) iterations. So

That is \(\frac12 n^2 - \frac12 n\). For large \(n\) the \(n^2\) term dominates, so we say the loop is \(O(n^2)\) ("order \(n\) squared"): doubling \(n\) roughly quadruples the work. The triangle-shaped loop does half the work of a full \(n \times n\) double loop, but halving does not change the growth rate. The precise meaning of \(O(\cdot)\) as a statement about limits is in Chapter 16.

Python lists, Java ArrayList, C++ std::vector, and Go slices all grow by doubling: when the array is full, allocate one twice as big and copy everything across. Copying is expensive, so how can appending be "constant time"? Try it: Dynamic array amortised cost.

Count element writes for \(n\) appends, starting from capacity 1. Every append writes one new element: \(n\) writes. Resizes happen when the size reaches 1, 2, 4, 8, …, copying that many elements. If the largest resize copies \(2^m\) elements, where \(2^m < n\), the total copying is a geometric series:

So the total work is less than \(n + 2n = 3n\): fewer than 3 writes per append on average, however large \(n\) grows. This "average over a sequence of operations" is called amortised cost. The key is the powers-of-two fact: the sum of all previous resizes is smaller than the latest one.

Try it: Per-append cost, step by step; Grow by 100: quadratic cost.

Merge sort splits an array in half, sorts each half recursively, and merges the halves in linear time. Its cost satisfies, informally (for \(n\) a power of 2, measuring cost in units where merging \(n\) items costs \(n\)), Try it: Merge-sort recursion tree.

Unroll it exactly as we did for Hanoi:

The recursion bottoms out when \(n/2^k = 1\), i.e. \(k = \log_2 n\) (Chapter 12). Then

Picture a recursion tree: \(\log_2 n\) levels, each doing \(n\) total work. That is where the ubiquitous \(O(n \log n)\) comes from. Compare the recurrence \(T(n) = T(n/2) + 1\) (binary search: one half discarded, constant work), which unrolls to \(\log_2 n\), and \(T(n) = 2T(n/2) + 1\) (visiting every node of a balanced tree), which unrolls to a geometric series \(1 + 2 + 4 + \cdots + n/2 \approx n\). The general pattern is captured by the "master theorem" in algorithms textbooks; behind it are nothing but geometric series.

Try it: Binary search recurrence; Visiting every tree node.

Translate the Fibonacci recurrence literally into code and you get something correct but catastrophically slow:

Why 242,785 calls? Let \(C_n\) be the number of calls made by fib_naive(n). Then \(C_0 = C_1 = 1\) and \(C_n = 1 + C_{n-1} + C_{n-2}\) — the call count obeys a Fibonacci-like recurrence itself. Its solution is \(C_n = 2F_{n+1} - 1\) (check: \(2F_{26} - 1 = 2(121{,}393) - 1 = 242{,}785\)). So the cost grows like \(\varphi^n \approx 1.618^n\): exponential. The call tree shows why: the same subproblems are recomputed again and again.

Memoisation caches each result the first time it is computed, so each \(F_k\) is computed once: 26 distinct computations for \(n = 25\), linear in \(n\). The iterative version goes further and keeps only the last two values — the recurrence evaluated "bottom up". That move from top-down recursion with a cache to bottom-up iteration over a table is the essence of dynamic programming. Try it: Call tree of fib(5).