Exercises: Sequences and Summations

These build from mechanical warm-ups to derivations, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; try them before you peek. Every sum in this set uses the book's conventions: the upper limit is inclusive, an empty sum is $0$, and an empty product is $1$.

Part A — Warm-ups (⭐)

11.1 † For the sequence $3, 7, 11, 15, 19, \dots$ (indexed from $n = 0$), write both a closed form $a_n$ and a recurrence (equation plus initial condition).

11.2 How many terms are in each sum? (a) $\sum_{i=1}^{n} a_i$, (b) $\sum_{i=5}^{50} a_i$, (c) $\sum_{i=0}^{n-1} a_i$, (d) $\sum_{i=k}^{2k} a_i$.

11.3 † Write out $\sum_{i=2}^{5} (2i - 1)$ term by term, then evaluate it.

11.4 Evaluate by hand: (a) $\prod_{i=1}^{4} i$, (b) $\dfrac{7!}{5!}$, (c) $\sum_{i=1}^{6} i$ using the arithmetic-series formula, (d) $\sum_{i=0}^{4} 2^i$ using the powers-of-two formula.

11.5 † State the value of the empty sum $\sum_{i=3}^{2} a_i$ and the empty product $\prod_{i=3}^{2} a_i$, and explain in one sentence why each value (not the other) is the natural choice.

11.6 The recurrence $a_0 = 5$, $a_n = 3 a_{n-1}$ defines which kind of sequence (arithmetic or geometric)? Give its closed form $a_n$.

Part B — Computation (⭐⭐)

11.7 † Use linearity and the closed forms $\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$ and $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ to evaluate $\sum_{i=1}^{n} (6i^2 - 4i + 5)$ in closed form.

11.8 Evaluate $\sum_{i=0}^{9} 5 \cdot 2^i$ using the geometric-series formula, then check your answer against the powers-of-two identity.

11.9 † Rewrite $\sum_{i=3}^{n} a_i$ as a sum whose index starts at $0$, adjusting the summand to keep the same terms.

11.10 A program prints a triangle: row $i$ has $i$ characters, for $i = 1$ to $200$. Using a closed form (no loop), how many characters does it print in total?

11.11 † Evaluate the telescoping sum $\sum_{i=1}^{n} \left(\dfrac{1}{i} - \dfrac{1}{i+1}\right)$ in closed form by writing out the cancellation, and state its value as $n \to \infty$.

11.12 Compute $\sum_{i=1}^{8} i^3$ two ways: directly term by term, and with the closed form $\left(\frac{n(n+1)}{2}\right)^2$. Confirm they agree.

Part C — Prove it, with scaffolding (⭐⭐)

11.13 † (Fill in the missing steps.) Derive the arithmetic-series formula for $S = \sum_{i=0}^{n-1}(a + id)$ by the "forwards and backwards" method. Fill the blanks: - Write $S$ forwards: $S = a + (a+d) + \cdots + \big(a + (n-1)d\big)$. - Write $S$ backwards: $S = \big(a + (n-1)d\big) + \cdots + (a+d) + a$. - Add the two equations column by column. The $i$-th column sums to $\underline{\hphantom{xxxxx}}$, which is independent of $i$. - There are $\underline{\hphantom{xx}}$ columns, so $2S = \underline{\hphantom{xxxxx}}$, giving $S = \underline{\hphantom{xxxxx}}$.

11.14 (Fill in the missing steps.) Derive the geometric-series formula for $S = \sum_{i=0}^{n-1} a r^i$ (with $r \ne 1$) by the "multiply and subtract" method. Fill the blanks: - $rS = \underline{\hphantom{xxxxxxxx}}$ (multiply every term by $r$). - Subtract $S$ from $rS$. The terms $ar, ar^2, \dots, ar^{n-1}$ all $\underline{\hphantom{xxxxx}}$, leaving $rS - S = \underline{\hphantom{xxxxx}}$. - Factor the left side: $(r-1)S = \underline{\hphantom{xxxxx}}$. Divide by $r - 1$ (legal because $\underline{\hphantom{xxxxx}}$) to get $S = a\,\dfrac{r^n - 1}{r - 1}$.

11.15 † (Derive by telescoping.) Evaluate $\sum_{i=1}^{n} \dfrac{1}{(2i-1)(2i+1)}$ in closed form. Hint: show $\dfrac{1}{(2i-1)(2i+1)} = \dfrac{1}{2}\left(\dfrac{1}{2i-1} - \dfrac{1}{2i+1}\right)$ by combining the right side over a common denominator, then telescope.

11.16 Derive the closed form for $\sum_{i=1}^{n} i \cdot 2^i$ by the "multiply and subtract" trick: let $S$ be the sum, compute $2S$, line them up shifted by one position, and subtract. (You will meet a plain geometric series in the leftovers.)

Part D — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Keep each function short.

11.17 † Write a function triangular(n) that returns $\sum_{i=1}^{n} i$ using the closed form (one arithmetic expression, no loop), and a second function triangular_loop(n) that computes the same sum with an explicit loop. State the loop invariant for the second one.

11.18 Write geometric_sum(a, r, n) returning $a + ar + \cdots + ar^{n-1}$ in closed form, handling the $r = 1$ case separately. Explain in a comment why the special case is necessary.

11.19 † Write factorial(n) recursively, matching the chapter's definition ($0! = 1$ and $n! = n \cdot (n-1)!$). Then add one line that prints the list $[0!, 1!, \dots, 6!]$.

11.20 Write count_pairs(n) that returns the number of times steps += 1 executes in the double loop for i in range(n): for j in range(i + 1, n):. Return the value using the closed form you derived for that loop in §11.6, not by running the loops.

Part E — Find the error (⭐⭐)

Each item below contains a flawed manipulation or claim. State precisely which step fails and why, then give the correct result.

11.21 † Claim. $\displaystyle\sum_{i=1}^{n} (5i - 3) = 5\sum_{i=1}^{n} i - 3.$ "Justification": "linearity pulls out the $5$ and the $-3$." Find the flaw and write the correct closed form.

11.22 Claim. "Since $\sum_{i=0}^{\infty} r^i = \frac{1}{1-r}$, we have $\sum_{i=0}^{\infty} 2^i = \frac{1}{1-2} = -1$." A student concludes that adding infinitely many positive powers of two gives $-1$. Identify the error (what condition was ignored?) and say what is actually true about $\sum_{i=0}^{\infty} 2^i$.

11.23 † Claim. "$\sum_{i=1}^{n} i = \frac{n(n+1)}{2}$, so to shift the index to start at $0$ we write $\sum_{i=0}^{n} i = \frac{n(n+1)}{2}$ as well, since adding the $i = 0$ term changes nothing." There is a real subtlety here and a real error. Is the equation the student wrote true or false, and is their reasoning valid? Explain.

11.24 Claim (a flawed telescoping). A student writes $\displaystyle\sum_{i=1}^{n} \frac{1}{i(i+1)} = \sum_{i=1}^{n}\left(\frac{1}{i} - \frac{1}{i+1}\right) = \frac{1}{1} - \frac{1}{n} = \frac{n-1}{n}.$ The partial-fraction split is correct but the final collapse is wrong. Find the mistake in the cancellation and give the right closed form.

Part F — Model it & Conjecture and test (⭐⭐⭐)

11.25 † (Model it.) A social media post is shared in "generations": you share it with $3$ people on day 0; each of those shares it with $3$ new people the next day; and so on, each generation $3$ times the size of the last. Model the number of people who see the post on day $k$ as a sequence, and the total number who have seen it through day $n$ as a sum. Give a closed form for the total, and use it to find the total through day $5$.

11.26 (Model it.) A dynamic array starts with capacity $1$ and doubles its capacity each time it fills, copying all existing elements into the new buffer. Suppose inserting $n = 2^k$ elements triggers resizes at sizes $1, 2, 4, \dots, 2^{k-1}$, and a resize from size $m$ copies $m$ elements. Write the total number of element copies across all resizes as a sum, evaluate it in closed form using the powers-of-two identity, and explain why this makes the average copy-cost per insertion a constant. (This is the amortized-cost argument behind Python's list.)

11.27 † (Conjecture and test, then prove.) Define $S(n) = \sum_{i=1}^{n} (2i - 1)$ (the sum of the first $n$ odd numbers). Use the Toolkit's summation to compute $S(1), S(2), \dots, S(8)$, write down the sequence of results, conjecture a closed form, and then prove your conjecture by telescoping (write $2i - 1 = i^2 - (i-1)^2$). Which Chapter 6 result does your closed form match?

11.28 (Conjecture and test, then prove or disprove.) Conjecture: "for all $n \ge 1$, $\sum_{i=1}^{n} i^2 = \frac{(\sum_{i=1}^{n} i)^2}{?}$ for some fixed constant." Use summation to compute both $\sum i^2$ and $\left(\sum i\right)^2$ for $n = 1, \dots, 6$, form their ratios, and decide whether a single constant works. Report what you find and explain it using the closed forms from the chapter's table. (Contrast with $\sum i^3 = (\sum i)^2$, which does hold exactly.)

11.29 † (Conjecture and test, then prove.) For the harmonic numbers $H_n = \sum_{i=1}^{n} \frac{1}{i}$, conjecture and test the inequality $H_{2^k} \ge 1 + \frac{k}{2}$ for $k = 0, 1, 2, 3, 4$ using summation with Fraction. Then prove it by grouping the terms of $H_{2^k}$ into blocks $\left(\frac{1}{2^{j-1}+1} + \cdots + \frac{1}{2^j}\right)$ and bounding each block below by $\frac12$. What does this tell you about how $H_n$ grows?

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

11.30 † (Ch. 9 + 11.) A sequence is a function $a\colon \mathbb{N} \to \mathbb{R}$. For the factorial sequence $n \mapsto n!$, state its domain and codomain, and decide whether it is injective and whether it is surjective onto the positive integers. Justify each answer in one line. (Watch the values at $n = 0$ and $n = 1$.)

11.31 (Ch. 6 + 11.) We derived $\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6}$ in §11.4 by telescoping a cube difference. Now prove the same identity by induction (Chapter 6's method): state the base case and the one algebraic move in the inductive step. In one sentence, say which method would have let you discover the formula and which only verifies it.

11.32 † (Ch. 6 + 11.) Prove by induction that $\sum_{i=0}^{n-1} 2^i = 2^n - 1$ for all $n \ge 1$, then state how the same result follows in one line from the geometric-series formula of §11.3. (This is theme four: two roads, one destination.)

11.33 (Ch. 9 + 11.) The map $j = i - 1$ used to shift a summation index is a function from one index set to another. For the shift $\sum_{i=1}^{n} a_i = \sum_{j=0}^{n-1} a_{j+1}$, identify the domain and codomain of $j = i - 1$ and explain why this map being a bijection between the two index sets is exactly what guarantees the two sums have the same terms.

11.34 (Deep Dive.) The chapter notes that telescoping a difference of cubes produces the formula for $\sum i^2$, a difference of fourth powers produces $\sum i^3$, and so on. Carry out the fourth-power case: expand $i^4 - (i-1)^4$, sum both sides from $1$ to $n$, use the known closed forms for $\sum i^2$ and $\sum i$, and solve for $\sum_{i=1}^{n} i^3$. Confirm you recover $\left(\frac{n(n+1)}{2}\right)^2$.

11.35 (Deep Dive, Ch. 6 + 11.) The doubling loop in §11.6 runs about $\log_2 n$ times. Make this precise: prove by induction (or a clean counting argument) that the loop i = 1; while i < n: i *= 2 executes its body exactly $\lceil \log_2 n \rceil$ times for $n \ge 1$. Connect your answer to the geometric-series bound $\sum_{j=0}^{k-1} 2^j = 2^k - 1$ that makes the total work linear.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each derivation, the rubric rewards: correct use of the summation laws (especially that a constant added inside the summand is summed once per term), a stated strategy before the algebra, agreement of any closed form with the first few terms, and — for the telescoping problems — an explicit display of what cancels and what survives.