Chapter 11: Sequences and Summations

"The art of doing mathematics consists in finding that special case which contains all the germs of generality." — David Hilbert

Overview

Open any piece of code that does real work and you will find a loop, and inside that loop a counter that marches through a sequence of values: 0, 1, 2, ..., or the elements of an array, or the levels of a tree. The moment you ask how long does this loop take? or how much memory does it use?, you are no longer reasoning about one iteration — you are adding up a quantity over a whole sequence of iterations. That sum is the running time. Learning to write that sum and collapse it into a clean formula is the difference between "I think this is fast" and "this is $\Theta(n^2)$, here is the arithmetic."

This chapter is the bridge between the proof techniques of Part I and the algorithm analysis that dominates the rest of the book. In Chapter 6 you proved a handful of summation identities by induction; here you will build a whole toolkit of them, learn the notation that lets you state them crisply, and — crucially — learn to derive a closed form rather than guess one and check it. By the end you will be able to look at a doubly nested loop and write down its cost without running it, which is exactly the skill Chapter 14 turns into Big-O notation.

We also pick up a thread that runs through the entire book. The Fibonacci numbers appeared in Chapter 6 as a target for induction. Here we meet them as a sequence in their own right — defined by a recurrence, summed, and examined for patterns — and we set up the two later chapters that finish the story: Chapter 18, where we solve the recurrence, and Chapter 19, where we compute Fibonacci numbers in logarithmic time.

In this chapter you will learn to:

• Define a sequence by a closed-form rule or by a recurrence, and move between the two descriptions.
• Use summation notation $\sum$ and product notation $\prod$ correctly, including the algebraic laws that let you pull out constants, split a sum, and shift its index.
• Derive the closed forms for arithmetic and geometric series from scratch, not just memorize them.
• Evaluate telescoping sums, where almost everything cancels.
• Work with factorials and see why they explode faster than any polynomial or simple exponential.
• Turn a nested loop into a summation, evaluate it, and read off the running time — the core move of algorithm analysis.

Learning Paths

🏃 Fast Track: If arithmetic and geometric series are old friends, skim 11.1–11.3 for the notation conventions this book uses (especially the half-open index convention), then concentrate on 11.4 (telescoping), 11.5 (factorials), and 11.6 (sums in algorithm analysis) — the last is where the CS payoff lives. Do the ⭐⭐ and ⭐⭐⭐ exercises.

📖 Standard Path: Read in order. Each "Check Your Understanding" is a retrieval cue — answer it from memory before reading on. Derive the geometric-series formula in 11.3 yourself before reading our derivation; that single technique (multiply by the ratio and subtract) recurs constantly.

🔬 Deep Dive: After the chapter, prove the closed form for $\sum_{i=1}^{n} i^2$ both by induction (Chapter 6's method) and by the telescoping technique of 11.4, and compare which one would have let you discover the formula. Then read the "perturbation method" note in Further Reading.

11.1 Sequences: closed-form versus recursive

Start with something you have typed a hundred times:

squares = [i * i for i in range(6)]   # [0, 1, 4, 9, 16, 25]

You have just written a sequence: an ordered list of numbers, one for each index $0, 1, 2, \dots$. The list comprehension describes the sequence the way a mathematician would call a closed form — it gives a direct rule, "the term at index $i$ is $i^2$," that lets you compute any term without computing the ones before it. Want the 1000th square? Evaluate $1000^2$; you need not know the 999th.

Contrast that with how you would generate the same idea if each term depended on the previous one:

def next_square(prev_i, prev_sq):
    # (i+1)^2 = i^2 + 2i + 1
    return prev_sq + 2 * prev_i + 1

This is a recursive description: term $i+1$ is defined in terms of term $i$. Both describe the same sequence of squares; they differ in whether a term is computed directly or from its predecessors. That distinction — closed form versus recurrence — is the central theme of this section and a thread through the next eight chapters.

Definition (sequence). A sequence is a function whose domain is a set of consecutive integers (the indices), usually $\{0, 1, 2, \dots\}$ or $\{1, 2, 3, \dots\}$. We write the term at index $n$ as $a_n$ (read "a sub n") and denote the whole sequence by $\{a_n\}$ or $(a_n)_{n \ge 0}$. The values $a_n$ are the terms.

Calling a sequence a function is not pedantry — it is the payoff of Chapter 9. A sequence $\{a_n\}$ is literally a function $a \colon \mathbb{N} \to \mathbb{R}$ (or into $\mathbb{Z}$, or any codomain), and everything you learned about functions applies. The index is the input; the term is the output. In code, a closed-form sequence is a pure function of its index, which is why lambda i: i*i and "the sequence of squares" are the same object wearing different clothes.

🔗 Connection. Recall from Chapter 9 that a function is determined by its domain, codomain, and rule. A sequence simply fixes the domain to be the integers from some starting point onward. "Closed form" means the rule is given explicitly; "recursive" means the rule is given in terms of earlier outputs — exactly the recursion-versus-direct distinction you met for functions in Chapter 6.

Two ways to pin down the same sequence

Consider the sequence $2, 5, 8, 11, 14, \dots$ — start at 2 and add 3 each time. We can describe it two ways.

Closed form. The term at index $n$ (counting from $n = 0$) is $$a_n = 2 + 3n.$$ Check: $a_0 = 2$, $a_1 = 5$, $a_2 = 8$. Any term in one step.

Recurrence. Give the first term and a rule relating each term to the previous one: $$a_0 = 2, \qquad a_n = a_{n-1} + 3 \ \text{ for } n \ge 1.$$ This says the same thing but computes term $n$ only after term $n-1$. A recurrence always needs one or more initial conditions (here $a_0 = 2$) plus the recurrence equation (here $a_n = a_{n-1} + 3$); without the initial condition the rule floats free and describes infinitely many sequences.

💡 Intuition: A closed form is random access — jump straight to term $n$, like indexing an array. A recurrence is sequential access — you must walk from the start, like traversing a linked list. They describe the same data; they differ in cost. A central project of discrete math (and of Chapters 18–19) is converting a slow recurrence into a fast closed form.

🧩 Productive Struggle. Before reading on, find a closed form for the sequence $1, 3, 6, 10, 15, \dots$ (the *triangular numbers* — the differences are $2, 3, 4, 5, \dots$). Then find one for $1, 3, 7, 15, 31, \dots$ (each term is one less than a power of two). Guess a formula, then test it against the next term. One of these you can derive cleanly by the end of 11.3; the other you can read off almost immediately. Sitting with the search — what rule fits these numbers? — is exactly the instinct this chapter sharpens.

The anchor sequence: Fibonacci

The most famous recursively defined sequence in this book is the Fibonacci sequence, which you met in Chapter 6: $$F_0 = 0, \qquad F_1 = 1, \qquad F_n = F_{n-1} + F_{n-2} \ \text{ for } n \ge 2.$$ Its first terms are $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \dots$$ Notice it needs two initial conditions, because each term reaches two steps back. There is no obvious closed form here — given just the list, you would be hard pressed to write a one-line rule for $F_n$. And yet one exists. It involves the golden ratio $\varphi = \frac{1+\sqrt{5}}{2}$, and deriving it is the headline result of Chapter 18. For now, sit with the discomfort: a sequence can be trivial to define recursively and surprisingly deep to express in closed form. That gap is where a lot of beautiful mathematics lives.

def fib(n):
    """Fibonacci by its recurrence. F_0 = 0, F_1 = 1."""
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

print([fib(n) for n in range(10)])
# Expected output:
# [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

⚠️ Common Pitfall: off-by-one in indexing. Sequences in this book usually start at $n = 0$, but some classic formulas (and some textbooks) start at $n = 1$. The Fibonacci sequence starts at $F_0 = 0$ here. Always state your starting index, and when you read a closed form, check it against the first two or three terms before trusting it. A formula that is "right except shifted by one" is the most common sequence bug, in math and in code alike.

🔄 Check Your Understanding 1. Write both a closed form and a recurrence for the sequence $1, 4, 9, 16, 25, \dots$ (the squares, indexed from $n = 1$). 2. The recurrence $a_n = 2 a_{n-1}$ with $a_0 = 1$ defines which familiar sequence? Give its closed form. 3. Why does the Fibonacci recurrence need two initial conditions while $a_n = a_{n-1} + 3$ needs only one?

Answers

1. Closed form: $a_n = n^2$. Recurrence: $a_1 = 1$, $a_n = a_{n-1} + (2n - 1)$ for $n \ge 2$ (each square exceeds the previous by the next odd number — the gnomon picture from Chapter 6). 2. The powers of two: $1, 2, 4, 8, 16, \dots$; closed form $a_n = 2^n$. 3. The Fibonacci rule references terms two steps back ($F_{n-2}$), so to get started you must already know the two terms before the first one you compute; $a_n = a_{n-1} + 3$ reaches only one step back, so a single starting value suffices.

11.2 Summation notation and its properties

A loop that accumulates a running total is doing addition over a sequence, and we need compact notation for "add these up." Here is the loop, then the notation.

total = 0
for i in range(1, n + 1):
    total += a(i)        # a(i) is the i-th term

The mathematical shorthand for whatever this loop computes is the summation: $$\sum_{i=1}^{n} a_i.$$

Definition (summation; series). Given a sequence $\{a_i\}$, the summation (or sum) $$\sum_{i=m}^{n} a_i = a_m + a_{m+1} + \cdots + a_n$$ is the result of adding the terms from index $m$ (the lower limit) through index $n$ (the upper limit). The symbol $i$ is the index of summation (a bound variable — its name is private to the sum). When the sum runs over infinitely many terms, $\sum_{i=m}^{\infty} a_i$, it is called a series (and we must ask whether it converges to a finite value).

The dictionary between code and notation is exact and worth internalizing:

⚠️ Common Pitfall: the upper limit is inclusive. In $\sum_{i=1}^{n}$ the term $a_n$ is included — there are $n - m + 1$ terms from $m$ to $n$. Python's range(m, n) is exclusive of n, so the faithful translation of $\sum_{i=m}^{n}$ is range(m, n + 1). Forgetting the + 1 drops the last term — a classic off-by-one that silently corrupts a total.

💡 Intuition: An empty sum (when the lower limit exceeds the upper, e.g. $\sum_{i=1}^{0}$) is defined to be $0$, just as an accumulator initialized to 0 stays 0 if the loop body never runs. This is not a special case to memorize; it falls out of the loop analogy and keeps formulas valid at their boundaries.

The algebraic laws of summation

Three laws let you manipulate sums the way you manipulate ordinary algebra. Each is just the distributive, commutative, and associative laws applied term by term — but stating them explicitly lets you transform a hard sum into an easy one.

1. Constant factor (linearity, part one). A constant multiplier pulls outside the sum: $$\sum_{i=m}^{n} c\, a_i = c \sum_{i=m}^{n} a_i.$$ (Factor $c$ out of every term — the distributive law.)

2. Sum of sums (linearity, part two). A sum of two sequences splits: $$\sum_{i=m}^{n} (a_i + b_i) = \sum_{i=m}^{n} a_i + \sum_{i=m}^{n} b_i.$$ (Reorder the additions — commutativity and associativity.) Together, laws 1 and 2 say summation is linear, which is the single most useful fact about it.

3. Splitting the range. A sum breaks at any interior point $p$ with $m \le p < n$: $$\sum_{i=m}^{n} a_i = \sum_{i=m}^{p} a_i + \sum_{i=p+1}^{n} a_i.$$ (Just a regrouping of the same terms.)

There is also a fourth move that trips people up but is indispensable: shifting the index. Because the index name and starting point are arbitrary, you may re-letter and re-base a sum as long as you adjust the summand to compensate. For example, to make a sum start at $0$ instead of $1$, substitute $j = i - 1$ (so $i = j + 1$): $$\sum_{i=1}^{n} a_i = \sum_{j=0}^{n-1} a_{j+1}.$$ Every $i$ becomes $j + 1$; the limits drop by 1 to keep the same terms. This is exactly renaming a loop variable and adjusting the bounds — the total does not change.

🐛 Find the Error. A student writes $\displaystyle\sum_{i=1}^{n} (3i + 2) = 3\sum_{i=1}^{n} i + 2.$ Is that right?

Answer

No. Linearity splits the sum into $\sum 3i + \sum 2$, and the constant $2$ is added once per term, so $\sum_{i=1}^{n} 2 = 2n$, not $2$. The correct statement is $\sum_{i=1}^{n}(3i+2) = 3\sum_{i=1}^{n} i + 2n$. The trap: pulling a constant out of a product (law 1) is fine, but a constant added inside the summand is summed $n$ times. Think of the loop: total += 2 runs $n$ times, contributing $2n$.

A worked manipulation

Suppose we already know (we will prove it in 11.3) that $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$. Use the laws to evaluate $\sum_{i=1}^{n} (3i + 2)$ without summing anything new: $$\sum_{i=1}^{n} (3i + 2) = 3\sum_{i=1}^{n} i + \sum_{i=1}^{n} 2 = 3 \cdot \frac{n(n+1)}{2} + 2n = \frac{3n^2 + 3n + 4n}{2} = \frac{3n^2 + 7n}{2}.$$ This is the standard pattern: break a complicated summand into pieces whose sums you already know, then reassemble. Most algorithm-analysis sums are evaluated exactly this way.

def sum_3i_plus_2(n):
    return sum(3 * i + 2 for i in range(1, n + 1))

# Check the closed form against the loop for n = 4:
# loop: (3+2)+(6+2)+(9+2)+(12+2) = 5+8+11+14 = 38
# formula: (3*16 + 7*4)/2 = (48 + 28)/2 = 76/2 = 38
print(sum_3i_plus_2(4))
# Expected output:
# 38

🔄 Check Your Understanding 1. How many terms are in $\sum_{i=4}^{20} a_i$? 2. Rewrite $\sum_{i=2}^{n} a_i$ as a sum whose index starts at $0$. 3. Use linearity and $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ to evaluate $\sum_{i=1}^{n} (4i - 1)$.

Answers

1. $20 - 4 + 1 = 17$ terms. 2. Let $j = i - 2$: $\sum_{j=0}^{n-2} a_{j+2}$. 3. $4 \cdot \frac{n(n+1)}{2} - \sum_{i=1}^{n} 1 = 2n(n+1) - n = 2n^2 + 2n - n = 2n^2 + n$.

11.3 Arithmetic and geometric series

Two families of sums appear so often — in interest calculations, in loop analysis, in probability — that their closed forms are worth knowing cold. The good news: each comes from a single clever idea you can reconstruct any time you forget the formula.

Arithmetic series

An arithmetic sequence adds a fixed amount, the common difference $d$, at each step: $a, a+d, a+2d, \dots$. Summing the first $n$ terms gives an arithmetic series.

Definition (arithmetic series). The sum of $n$ consecutive terms of an arithmetic sequence with first term $a$ and common difference $d$: $$\sum_{i=0}^{n-1} (a + i d) = a + (a+d) + (a+2d) + \cdots + \big(a + (n-1)d\big).$$

The strategy first. The trick is the one attributed to the schoolboy Gauss: write the sum forwards, write it again backwards beneath, and add the two columns. Every column gives the same total — first-plus-last — so $n$ identical columns make $2 \times (\text{the sum})$. We then divide by two. This "fold the sum onto itself" idea is more valuable than the formula it produces.

Theorem (arithmetic series). For $n \ge 1$, $$\sum_{i=0}^{n-1} (a + i d) = \frac{n\big(2a + (n-1)d\big)}{2} = n \cdot \frac{(\text{first}) + (\text{last})}{2}.$$

Proof. Call the sum $S$. Write it forwards and backwards: $$ \begin{aligned} S &= a + (a+d) + \cdots + \big(a+(n-1)d\big),\\ S &= \big(a+(n-1)d\big) + \cdots + (a+d) + a. \end{aligned} $$ Add the two equations term by term. The $i$-th column is $\big(a + id\big) + \big(a + (n-1-i)d\big) = 2a + (n-1)d$, which is independent of $i$ — every column has the same total. There are $n$ columns, so $$2S = n\big(2a + (n-1)d\big), \qquad \text{hence} \qquad S = \frac{n\big(2a + (n-1)d\big)}{2}.$$ Recognizing $2a + (n-1)d = (\text{first term}) + (\text{last term})$ gives the memorable form $S = n \cdot \frac{\text{first} + \text{last}}{2}$: the number of terms times the average of the endpoints. $\blacksquare$

The special case $a = 1, d = 1$ recovers the identity you proved by induction in Chapter 6: $$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}.$$

Worked example. A program prints a triangular pattern: row $i$ contains $i$ asterisks, for $i = 1$ to $n$. How many asterisks total? That is the arithmetic series $1 + 2 + \cdots + n$ with first term $1$, last term $n$, and $n$ terms, so by the formula it is $n \cdot \frac{1 + n}{2} = \frac{n(n+1)}{2}$. For $n = 100$ rows the program prints $\frac{100 \cdot 101}{2} = 5050$ asterisks — and notice we did not loop; the closed form answered an "how much work" question in one multiplication. That is the recurring value of a closed form: it replaces an $O(n)$ count with an $O(1)$ formula. Watch for this in 11.6, where the same triangular sum turns out to be the running time of an entire class of nested loops.

🔗 Connection. In Chapter 6 we verified this formula by induction — we had to be handed the answer first. Here we derived it: the folding argument produces the formula from nothing. That is the difference the present chapter adds. Induction confirms a closed form you already suspect; the techniques of this chapter let you find it. Both skills matter, and they are theme four of this book — computation and proof, suggestion and certainty — in microcosm.

Geometric series

A geometric sequence multiplies by a fixed common ratio $r$ at each step: $a, ar, ar^2, \dots$. Its sum is a geometric series, and it is arguably the single most important sum in computer science: it governs the cost of anything that doubles (or halves) — binary trees, divide-and-conquer, dynamic arrays, exponential search spaces.

Definition (geometric series). The sum of the first $n$ terms of a geometric sequence with first term $a$ and common ratio $r$: $$\sum_{i=0}^{n-1} a r^i = a + ar + ar^2 + \cdots + ar^{n-1}.$$

The strategy first. The trick here is different and just as memorable: multiply the whole sum by the ratio $r$, then subtract. When you line up $S$ and $rS$, almost every term cancels against a twin, leaving only the first term of one and the last term of the other. Solving for $S$ gives the formula. Internalize the move — "multiply by $r$ and subtract" — and you never need to memorize the result.

Theorem (geometric series). For $r \ne 1$ and $n \ge 1$, $$\sum_{i=0}^{n-1} a r^i = a \cdot \frac{r^n - 1}{r - 1}.$$ (When $r = 1$ every term equals $a$, so the sum is simply $a n$.)

Proof. Let $S = a + ar + ar^2 + \cdots + ar^{n-1}$. Multiply both sides by $r$: $$rS = ar + ar^2 + \cdots + ar^{n-1} + ar^{n}.$$ Now subtract the first equation from the second. Every middle term $ar, ar^2, \dots, ar^{n-1}$ appears in both lines and cancels, leaving only $ar^n$ (from $rS$) and $a$ (from $S$): $$rS - S = ar^n - a, \qquad \text{so} \qquad (r-1)S = a(r^n - 1).$$ Since $r \ne 1$ we may divide by $r - 1$: $$S = a \cdot \frac{r^n - 1}{r - 1}. \qquad \blacksquare$$

Two consequences are worth committing to memory because they appear constantly:

• Powers of two. With $a = 1, r = 2$: $\displaystyle\sum_{i=0}^{n-1} 2^i = 2^n - 1.$ The sum of the first $n$ powers of two is one less than the next power — the reason an $n$-bit unsigned integer holds values $0$ through $2^n - 1$, and the reason a full binary tree of height $h$ has $2^{h+1} - 1$ nodes.
• Infinite geometric series. If $\lvert r \rvert < 1$, then $r^n \to 0$ as $n \to \infty$, and the series converges: $\displaystyle\sum_{i=0}^{\infty} a r^i = \frac{a}{1 - r}.$ (For example, $1 + \tfrac12 + \tfrac14 + \cdots = 2$.) This is the only infinite series you must know for algorithm analysis; it makes "the work halves each level" sum to a constant times the first level.

def geometric_sum(a, r, n):
    """Sum of a*r^0 + ... + a*r^(n-1). Direct loop, for checking the closed form."""
    return sum(a * r ** i for i in range(n))

# Check 1 + 2 + 4 + 8 + 16 == 2^5 - 1 == 31:
print(geometric_sum(1, 2, 5))
# Expected output:
# 31

💡 Intuition: Why is $\sum_{i=0}^{\infty} \tfrac{1}{2^i} = 2$ and not infinite? Each term is half the remaining distance to 2. You go to 1, then halfway from 1 to 2, then halfway again — you approach 2 forever but never overshoot. The "multiply and subtract" proof is the algebra behind that picture; the convergence condition $\lvert r \rvert < 1$ is the requirement that each step be a genuine fraction of what is left.

🔄 Check Your Understanding 1. Evaluate $\sum_{i=1}^{100} i$ using the arithmetic-series formula. 2. Evaluate $\sum_{i=0}^{9} 3^i$ using the geometric-series formula. 3. A savings plan pays 5% interest, so a deposit of \$1 becomes $1.05^k$ after $k$ years. What is the total value after depositing \$1 at the start of each of 3 years (i.e. $1.05^3 + 1.05^2 + 1.05^1$)? Set it up as a geometric series; you need not compute the decimal.

Answers

1. $\frac{100 \cdot 101}{2} = 5050$. 2. $\frac{3^{10} - 1}{3 - 1} = \frac{59049 - 1}{2} = 29524$.
2. This is $1.05 + 1.05^2 + 1.05^3 = 1.05 \cdot \frac{1.05^3 - 1}{1.05 - 1} = 1.05 \cdot \frac{1.05^3 - 1}{0.05} = 21(1.05^3 - 1)$. (Numerically about \$3.31, but the closed form is the point.)

11.4 Useful closed forms and telescoping

Beyond the two big families, a short table of closed forms covers most sums you will meet. Keep these where you can find them; deriving each from scratch is good practice but slow in the moment.

The last row is a warning as much as a fact: not every sum collapses to a tidy formula. The $n$-th harmonic number $H_n = 1 + \tfrac12 + \tfrac13 + \cdots + \tfrac1n$ grows like the natural logarithm $\ln n$ (the constant $\gamma \approx 0.577$ is the Euler–Mascheroni constant). $H_n$ shows up whenever each step costs $1/i$ — the average number of comparisons in quicksort, the expected length of certain searches — and the right thing to remember is its growth rate, $H_n = \Theta(\log n)$, not an exact value.

Telescoping: when almost everything cancels

There is one technique that derives closed forms (rather than verifying them) and deserves special attention, because it is the engine behind several of the formulas above and a favorite trick in algorithm analysis.

Definition (telescoping sum). A telescoping sum is one whose summand can be written as a difference of consecutive values of some sequence, $a_i = t_i - t_{i-1}$ (or $t_{i+1} - t_i$). In such a sum, each term's second half cancels the next term's first half, and the whole sum collapses to just the outer endpoints: $$\sum_{i=1}^{n} (t_i - t_{i-1}) = t_n - t_0.$$

The name comes from a collapsing telescope: the middle slides away and only the two ends remain. Here is the cancellation written out, so you can see it happen: $$ \sum_{i=1}^{n} (t_i - t_{i-1}) = (t_1 - t_0) + (t_2 - t_1) + (t_3 - t_2) + \cdots + (t_n - t_{n-1}). $$ Reading left to right: $-t_0$ survives; then $+t_1$ and $-t_1$ kill each other; $+t_2$ and $-t_2$ kill each other; and so on, until only the very first $-t_0$ and the very last $+t_n$ are left. Hence $t_n - t_0$.

The strategy first (deriving a closed form by telescoping). To find $\sum a_i$, look for a sequence $t_i$ whose consecutive difference $t_i - t_{i-1}$ equals your summand $a_i$. If you can find one, the sum is just $t_n - t_0$ — no induction needed. Finding $t_i$ is the discrete analogue of finding an antiderivative in calculus; the difference $t_i - t_{i-1}$ plays the role of the derivative.

Worked example: a partial-fractions telescope. Evaluate $\displaystyle\sum_{i=1}^{n} \frac{1}{i(i+1)}.$

Split the summand by partial fractions (verify by combining the right side over a common denominator): $$\frac{1}{i(i+1)} = \frac{1}{i} - \frac{1}{i+1}.$$ Now the sum telescopes with $t_i = -\frac{1}{i+1}$, i.e. each term is $\big(-\tfrac{1}{i+1}\big) - \big(-\tfrac{1}{i}\big)$: $$\sum_{i=1}^{n} \left(\frac{1}{i} - \frac{1}{i+1}\right) = \left(\frac11 - \frac12\right) + \left(\frac12 - \frac13\right) + \cdots + \left(\frac1n - \frac{1}{n+1}\right) = 1 - \frac{1}{n+1} = \frac{n}{n+1}.$$ Everything between the first $\frac11$ and the last $-\frac{1}{n+1}$ cancels in pairs. We obtained the closed form $\frac{n}{n+1}$ constructively — telescoping handed it to us, whereas induction would have required us to guess it first.

def telescoping_demo(n):
    """Sum 1/(i*(i+1)) for i=1..n; should equal n/(n+1) exactly (use Fraction)."""
    from fractions import Fraction
    return sum(Fraction(1, i * (i + 1)) for i in range(1, n + 1))

print(telescoping_demo(4))   # 1/(1*2)+1/(2*3)+1/(3*4)+1/(4*5)
# 1/2 + 1/6 + 1/12 + 1/20 = 30/60 + 10/60 + 5/60 + 3/60 = 48/60 = 4/5
# Expected output:
# 4/5

Deriving the sum of squares by telescoping. The table above lists $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ as a fact to memorize. Telescoping lets us derive it — and the derivation shows the general recipe for summing any power. The idea: find a telescoping sum whose collapse exposes the sum we want. Start from the difference of consecutive cubes and expand: $$i^3 - (i-1)^3 = i^3 - (i^3 - 3i^2 + 3i - 1) = 3i^2 - 3i + 1.$$ Sum both sides from $i = 1$ to $n$. The left side telescopes (with $t_i = i^3$) to $n^3 - 0 = n^3$. The right side splits by linearity: $$n^3 = \sum_{i=1}^{n}(3i^2 - 3i + 1) = 3\sum_{i=1}^{n} i^2 - 3\sum_{i=1}^{n} i + \sum_{i=1}^{n} 1.$$ We already know the last two sums: $\sum i = \frac{n(n+1)}{2}$ and $\sum 1 = n$. Substitute and solve for the unknown $\sum i^2$: $$3\sum_{i=1}^{n} i^2 = n^3 + 3\cdot\frac{n(n+1)}{2} - n.$$ A little algebra (put everything over 2, factor out $n$) gives $3\sum i^2 = \frac{n(n+1)(2n+1)}{2}$, and dividing by 3 yields $$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}.$$ No guessing, no induction — telescoping a cube difference produced the quadratic-sum formula. The same trick with fourth powers gives $\sum i^3$, and so on up the ladder. This is the discrete analogue of integration by parts, and it is why telescoping is a derivation tool, not merely a verification one.

🔗 Connection. Telescoping is the discrete twin of the Fundamental Theorem of Calculus: a sum of consecutive differences collapses to the endpoints, just as an integral of a derivative collapses to $F(b) - F(a)$. Concrete Mathematics (Graham, Knuth, and Patashnik) builds an entire "finite calculus" on this analogy. You do not need that machinery here, but the parallel is worth filing away — it is the same idea that makes telescoping feel inevitable once you see it.

🔄 Check Your Understanding 1. Use the sum-of-squares formula to compute $\sum_{i=1}^{5} i^2$, and check against $1+4+9+16+25$. 2. Telescope $\sum_{i=1}^{n} (2i - 1)$ by writing $2i - 1 = i^2 - (i-1)^2$. What closed form do you get, and which Chapter 6 result does it match? 3. Why does the harmonic sum $\sum_{i=1}^{n} \frac{1}{i}$ not telescope the way $\sum \frac{1}{i(i+1)}$ does?

Answers

1. $\frac{5 \cdot 6 \cdot 11}{6} = \frac{330}{6} = 55$, and $1+4+9+16+25 = 55$. ✓ 2. With $t_i = i^2$, the sum is $t_n - t_0 = n^2 - 0 = n^2$ — exactly the "sum of the first $n$ odd numbers is $n^2$" result from Chapter 6, now derived by telescoping instead of verified by induction. 3. Because $\frac1i$ is not a difference of consecutive terms of a simple sequence — there is no elementary $t_i$ with $t_i - t_{i-1} = \frac1i$. (That is precisely why $H_n$ has no elementary closed form and only an asymptotic one, $\approx \ln n$.)

11.5 Products and factorials

Everything we did for sums has a multiplicative twin. Where $\sum$ accumulates with +, the product notation $\prod$ accumulates with *.

Definition (product notation). Given a sequence $\{a_i\}$, $$\prod_{i=m}^{n} a_i = a_m \cdot a_{m+1} \cdots a_n$$ is the product of the terms from $m$ to $n$. By convention an empty product (when $m > n$) equals $1$ — the multiplicative identity, just as an empty sum equals $0$.

def product(seq):
    result = 1                 # empty product is 1
    for x in seq:
        result *= x
    return result

print(product(range(1, 6)))    # 1*2*3*4*5
# Expected output:
# 120

The single most important product in discrete mathematics is the factorial, which counts the number of ways to arrange $n$ distinct objects in order — a fact we will lean on heavily when we study counting in Part III.

Definition (factorial). For an integer $n \ge 0$, $n$ factorial is $$n! = \prod_{i=1}^{n} i = 1 \cdot 2 \cdot 3 \cdots n,$$ with the convention $0! = 1$ (the empty product). Equivalently, by recurrence: $0! = 1$ and $n! = n \cdot (n-1)!$ for $n \ge 1$.

💡 Intuition: Why is $0! = 1$ and not $0$? Two reasons, both pointing the same way. (1) It is the empty product, and an empty product is the multiplicative identity $1$ — the same logic that makes an empty sum $0$. (2) Combinatorially, $n!$ counts the orderings of $n$ objects; there is exactly one way to order zero objects (do nothing), so $0! = 1$. Defining $0! = 1$ keeps the recurrence $n! = n\cdot(n-1)!$ valid down to $n=1$ and keeps every counting formula from breaking at its boundary.

🔗 Connection. Factorials are the gateway to Chapter 16 (permutations and combinations), where $n!$ counts arrangements and the binomial coefficient $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ counts selections. They also drive the running time of brute-force algorithms that try every ordering — the traveling-salesman brute force is $\Theta(n!)$ — which is why the growth of $n!$ matters so much.

How fast does $n!$ grow?

Factorial growth is in a league of its own. Lining up the growth hierarchy you will formalize in Chapter 14: $$\text{constant} \prec \log n \prec n \prec n\log n \prec n^2 \prec 2^n \prec n! \prec n^n.$$ Factorial eventually outruns every exponential $c^n$ with a fixed base $c$: since $n! = 1\cdot 2 \cdots n$ and roughly half of those factors exceed $n/2$, we have $n! \ge (n/2)^{n/2}$, whose base $n/2$ keeps growing — unlike the fixed base of $2^n$. The practical upshot: an algorithm that enumerates all $n!$ orderings is hopeless beyond about $n = 12$ ($12! \approx 4.8 \times 10^8$ is already near a second of work; $20! \approx 2.4 \times 10^{18}$ is out of reach).

⚠️ Common Pitfall: factorial overflow. In languages with fixed-width integers, $n!$ overflows almost immediately — $13!$ already exceeds a signed 32-bit integer, and $21!$ exceeds 64 bits. Python integers are arbitrary-precision so they will not overflow, but they will get slow and huge. Whenever you see a factorial in a complexity bound, read it as "astronomically large, do not enumerate."

def factorial(n):
    """n! by recurrence; 0! = 1. Matches the definition in 11.5."""
    if n == 0:
        return 1
    return n * factorial(n - 1)

print([factorial(n) for n in range(7)])
# Expected output:
# [1, 1, 2, 6, 24, 120, 720]

🔄 Check Your Understanding 1. Compute $\prod_{i=2}^{5} i$ and $\frac{6!}{4!}$. Why is the second one fast to compute by hand? 2. Explain in one sentence why $0! = 1$ makes the recurrence $n! = n\cdot(n-1)!$ work at $n = 1$. 3. Roughly where does $n!$ overtake $2^n$? (You need not be exact — reason from the factors.)

Answers

1. $\prod_{i=2}^{5} i = 2\cdot3\cdot4\cdot5 = 120$; $\frac{6!}{4!} = \frac{720}{24} = 30 = 6\cdot5$ (the $4!$ cancels the tail, leaving just $6\cdot5$). 2. At $n=1$ the recurrence gives $1! = 1 \cdot 0! = 1\cdot1 = 1$, which is correct only because $0! = 1$. 3. Around $n = 4$: $4! = 24 > 16 = 2^4$ (and $3! = 6 < 8 = 2^3$), so $n!$ pulls ahead between $n=3$ and $n=4$ and never looks back, since each new factor $n$ exceeds the fixed factor $2$.

11.6 Sums in algorithm analysis: the cost of nested loops

Here is the chapter's destination — the reason a programmer learns all of the above. The running time of a loop is a sum: add up the work done on each pass. The running time of a nested loop is a sum of sums. Evaluate the sum in closed form, and you have the algorithm's cost as a formula in the input size $n$ — ready to be classified with Big-O in Chapter 14.

Let's analyze a concrete fragment. This is the comparison count of a naive selection-style double loop:

def count_inner_steps(n):
    steps = 0
    for i in range(n):           # i = 0, 1, ..., n-1
        for j in range(i + 1, n):  # j = i+1, ..., n-1
            steps += 1           # one unit of work
    return steps

How many times does steps += 1 run, as a function of $n$? For a fixed $i$, the inner loop runs for $j = i+1, \dots, n-1$, which is $n - 1 - i$ iterations. The total is the sum over all $i$: $$T(n) = \sum_{i=0}^{n-1} (n - 1 - i).$$

The strategy first. We meet a sum we do not instantly recognize. The move is to shift the index so it becomes one we do recognize — here, a plain sum of consecutive integers. Substitute $k = n - 1 - i$: as $i$ runs $0 \to n-1$, $k$ runs $n-1 \to 0$, hitting every integer in between. So the sum is just $\sum_{k=0}^{n-1} k$ in disguise.

Carrying it out: $$T(n) = \sum_{i=0}^{n-1} (n-1-i) = \sum_{k=0}^{n-1} k = \frac{(n-1)n}{2} = \frac{n^2 - n}{2}.$$ The first equality is the index shift; the third is the arithmetic-series formula (summing $0$ through $n-1$). So this fragment does exactly $\frac{n^2 - n}{2}$ units of work — and we obtained that exactly, by hand, without running anything.

Now the connection to complexity. The leading term is $\frac{n^2}{2}$; the $-\frac{n}{2}$ and the constant $\frac12$ are lower-order and constant factors that Big-O notation will discard. So $T(n) = \Theta(n^2)$: the running time grows quadratically. That is why this pattern — "for each $i$, do something for the elements after it" — is the signature of an $O(n^2)$ algorithm, and why you learn to recognize it on sight.

💡 Intuition: The double loop touches every unordered pair $\{i, j\}$ exactly once. The number of such pairs from $n$ items is $\binom{n}{2} = \frac{n(n-1)}{2}$ — the very value we just summed. Counting (Chapter 16) and summing are two roads to the same closed form; when both arrive, you can be confident. This is theme four again: a count suggests the answer, a summation derives it.

A geometric example: why doubling is cheap

Not every loop is quadratic. Consider a loop whose counter doubles:

def doubling_loop(n):
    steps = 0
    i = 1
    while i < n:
        steps += 1
        i *= 2               # i = 1, 2, 4, 8, ...
    return steps

The values of i are $1, 2, 4, \dots, 2^{k-1}$, and the loop stops once $i \ge n$. It runs while $2^{k-1} < n$, i.e. about $k \approx \log_2 n$ times. The total work if each pass did $i$ units (say, processing a block of size i) would be a geometric series: $$\sum_{j=0}^{k-1} 2^j = 2^k - 1 < 2n,$$ using the powers-of-two closed form. The punchline is striking: even though the last pass alone does about $n$ units of work, the entire loop does less than $2n$ — because a geometric series is dominated by its largest term. This single fact, $\sum 2^j = 2^{k}-1$, is why dynamic-array resizing, heap construction, and many divide-and-conquer algorithms are linear rather than worse. We will reuse it constantly.

A mixed example: $\Theta(n \log n)$

The two patterns combine. Consider an outer loop that runs $n$ times, each pass doing a doubling loop:

def n_log_n_loop(n):
    steps = 0
    for i in range(n):           # n outer passes
        j = 1
        while j < n:             # inner: doubling, ~log2(n) passes
            steps += 1
            j *= 2
    return steps

The inner loop does about $\log_2 n$ steps (the doubling analysis from a moment ago), and the outer loop repeats it $n$ times. As a sum: $$T(n) = \sum_{i=0}^{n-1} \log_2 n = n \log_2 n,$$ because the summand $\log_2 n$ does not depend on $i$ — it is a constant pulled out by linearity, summed $n$ times. So $T(n) = \Theta(n \log n)$, the running time of efficient sorting and of "do a logarithmic operation once per element." Now you can recognize all three signatures on sight: a nested loop over pairs is $\Theta(n^2)$; a doubling loop is $\Theta(\log n)$; an outer linear loop wrapping a logarithmic inner loop is $\Theta(n \log n)$.

🔗 Connection. This is exactly the analysis you will formalize in Chapter 14 (asymptotic notation) and apply to divide-and-conquer recurrences in Chapter 18. The three sums of this section — the arithmetic $\Theta(n^2)$ from a triangular double loop, the geometric $\Theta(n)$ from a doubling loop, and the $\Theta(n\log n)$ from a linear loop over a logarithmic one — are the patterns you will reach for most often when reading code for its cost. The ability to write a loop's work as a sum and collapse it is the whole game.

🔄 Check Your Understanding 1. A double loop runs for i in range(n): for j in range(n):. Write its step count as a sum and evaluate it. Is it $\Theta(n^2)$? 2. In the doubling loop, why is the total work less than twice the work of the final pass? 3. A loop runs for i in range(n): for j in range(i):. How many total steps, in closed form?

Answers

1. $\sum_{i=0}^{n-1}\sum_{j=0}^{n-1} 1 = \sum_{i=0}^{n-1} n = n \cdot n = n^2$. Yes, $\Theta(n^2)$.
2. Because the work forms a geometric series with ratio 2, whose sum $2^k - 1$ is less than twice its largest term $2^{k-1}$; the entire history of smaller passes adds up to less than one more copy of the last pass. 3. $\sum_{i=0}^{n-1} i = \frac{(n-1)n}{2} = \frac{n^2-n}{2}$, again $\Theta(n^2)$ — the same triangular sum as the worked example, just indexed from $0$ to $i-1$.

Project Checkpoint: summation tools for the Toolkit

Chapter 6 began dmtoolkit/recurrences.py with check_identity (a conjecture tester) and a naive fib. This chapter is about closed forms, so we add tools that compute and verify them — the natural companions to check_identity. We are not yet touching the solve_linear and matrix fib reserved for Chapters 18–19; we are adding small, stable helpers that the later code can rely on.

Add these to dmtoolkit/recurrences.py:

def summation(term, lo, hi):
    """Evaluate sum_{i=lo}^{hi} term(i), inclusive of hi. Empty sum (lo>hi) is 0."""
    return sum(term(i) for i in range(lo, hi + 1))

def arithmetic_sum(first, diff, n):
    """Closed form for n terms: first + (first+diff) + ... ; n*(2*first+(n-1)*diff)//2."""
    return n * (2 * first + (n - 1) * diff) // 2

def geometric_sum(first, ratio, n):
    """Closed form for first + first*ratio + ... + first*ratio^(n-1), ratio != 1."""
    if ratio == 1:
        return first * n
    return first * (ratio ** n - 1) // (ratio - 1)

Each closed form should agree with the direct summation for every $n$. That agreement is exactly what check_identity from Chapter 6 was built to test, and wiring them together is the point:

# Verify the geometric closed form against the brute-force sum, for powers of 3:
brute = lambda n: summation(lambda i: 3 ** i, 0, n - 1)
closed = lambda n: geometric_sum(1, 3, n)
print(check_identity(brute, closed, upto=8, start=1))
# Expected output:
# None

The None means no counterexample up to $n = 8$ — and because we proved the geometric formula in 11.3, we know it holds for all $n$. This is the chapter's theme in code: a closed form turns a loop (summation, $O(n)$ work) into a single arithmetic expression (geometric_sum, $O(1)$ work after the power), and a tester gives you fast confidence before you trust it.

Toolkit so far: logic.py (Chapters 1–3); recurrences.py now holds check_identity, fib, summation, arithmetic_sum, and geometric_sum. Chapters 18–19 will add solve_linear and a fast matrix fib to the same module, and the capstone will use these closed-form helpers to predict running times before measuring them.

Summary

A sequence is a function on the integers; we describe it by a closed form (direct rule, random access) or a recurrence (each term from its predecessors, sequential access). A series is the sum of a sequence. The reference results:

Key techniques, each reducible to one sentence:

• Arithmetic series: write forwards and backwards, add — every column is first + last.
• Geometric series: multiply by the ratio and subtract — the middle cancels.
• Telescoping: rewrite the summand as a consecutive difference; only the endpoints survive.
• Algorithm analysis: write the loop's work as a (possibly nested) sum, shift the index to a known form, collapse, then read off the leading term as the growth rate.
• Factorial: grows faster than every fixed-base exponential; never enumerate $n!$ things for $n \gtrsim 12$.

Spaced Review

Retrieval strengthens memory. Answer from memory before expanding the solutions.

1. (Ch. 9) A sequence is "really" a function. State its domain and codomain, and say which kind of function (injective? surjective?) the squares sequence $a_n = n^2$ on $\mathbb{N}$ is, with a one-line reason.
2. (Ch. 9) The factorial function $n \mapsto n!$ from $\mathbb{N}$ to the positive integers — is it injective on $n \ge 1$? Is it surjective onto the positive integers? Justify briefly.
3. (Ch. 6) We derived $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ here by folding. Sketch the inductive proof of the same identity: state the base case and the one algebraic move in the inductive step.
4. (Ch. 6) The identity $\sum_{i=1}^{n} F_i = F_{n+2} - 1$ was proved by induction in Chapter 6. Which fact about the Fibonacci sequence does its inductive step rely on?

Answers

1. Domain $\mathbb{N} = \{0,1,2,\dots\}$, codomain whatever we declare (say $\mathbb{N}$ or $\mathbb{R}$). As a map $\mathbb{N} \to \mathbb{N}$, $n \mapsto n^2$ is injective (distinct non-negative $n$ give distinct squares) but not surjective (e.g. $2$ and $3$ are never hit).
2. Injective on $n \ge 1$? Yes for $n \ge 1$, since $n!$ is strictly increasing there — though note $0! = 1! = 1$, so it fails injectivity if you include $0$. Surjective onto the positive integers? No — $5$, for instance, is never a factorial. 3. Base case $n=1$: $\sum_{i=1}^{1} i = 1 = \frac{1\cdot2}{2}$. Inductive step: assume $\sum_{i=1}^{k} i = \frac{k(k+1)}{2}$, add $(k+1)$ to both sides, and simplify $\frac{k(k+1)}{2} + (k+1) = \frac{(k+1)(k+2)}{2}$ — "peel off the last term, apply the hypothesis." 4. It relies on the defining recurrence $F_{k+1} + F_{k+2} = F_{k+3}$, used to recombine $(F_{k+2} - 1) + F_{k+1}$ into $F_{k+3} - 1$.

What's Next

You can now write the cost of a loop as a sum and collapse it into a formula — but we have been casual about what those formulas mean. Is $\frac{n^2 - n}{2}$ "the same as" $n^2$ for the purpose of comparing algorithms? When we say a doubling loop is "linear," exactly which lower-order terms and constants are we entitled to ignore? Chapter 14 answers this by making the growth-rate hierarchy precise with Big-O, Big-$\Omega$, and Big-$\Theta$ notation — turning the sums of this chapter into the formal language of algorithm analysis. And the recurrences we kept meeting — Fibonacci above all — get their own treatment in Chapter 18, where we finally solve them in closed form. The sequence has been defined; next we learn to measure it.