Chapter 11 — Key Takeaways

A one-page, exam-prep reference for Sequences and Summations. Skim it; the prose is in index.md.

Core definitions

Term Definition (compact)
Sequence $\{a_n\}$ A function from consecutive integers to numbers; $a_n$ = term at index $n$.
Closed form A direct rule for $a_n$ (random access — compute term $n$ alone).
Recurrence $a_n$ defined from earlier terms + initial condition(s) (sequential access).
Series The sum of a sequence; $\sum_{i=m}^{\infty}$ is an infinite series (must converge).
Summation $\sum_{i=m}^{n} a_i$ $a_m + \cdots + a_n$; inclusive of $n$; $n-m+1$ terms; empty sum $=0$.
Product $\prod_{i=m}^{n} a_i$ $a_m \cdots a_n$; empty product $=1$.
Factorial $n!$ $\prod_{i=1}^{n} i = 1\cdot2\cdots n$; $0! = 1$; recurrence $n! = n\,(n-1)!$.
Telescoping sum Summand is a consecutive difference $t_i - t_{i-1}$; collapses to endpoints.

Summation laws (memorize — these are the algebra of sums)

Law Statement
Constant factor $\displaystyle\sum_{i=m}^{n} c\,a_i = c\sum_{i=m}^{n} a_i$
Sum of sums $\displaystyle\sum_{i=m}^{n}(a_i+b_i) = \sum a_i + \sum b_i$
Linearity the two above combined — the key property of $\sum$
Constant summand $\displaystyle\sum_{i=m}^{n} c = c\,(n-m+1)$ ← summed once per term
Split the range $\displaystyle\sum_{i=m}^{n} = \sum_{i=m}^{p} + \sum_{i=p+1}^{n}$
Index shift $\displaystyle\sum_{i=1}^{n} a_i = \sum_{j=0}^{n-1} a_{j+1}$ (rename + re-base)

Closed-form catalog (the ones worth knowing cold)

Sum Closed form When it shows up
$\displaystyle\sum_{i=1}^{n} 1$ $n$ counting iterations
$\displaystyle\sum_{i=1}^{n} i$ $\dfrac{n(n+1)}{2}$ triangular double loops → $\Theta(n^2)$
$\displaystyle\sum_{i=1}^{n} i^2$ $\dfrac{n(n+1)(2n+1)}{6}$ triple-nested counting
$\displaystyle\sum_{i=1}^{n} i^3$ $\left(\dfrac{n(n+1)}{2}\right)^2$ $= \big(\sum i\big)^2$
$\displaystyle\sum_{i=0}^{n-1} a r^i$ $a\,\dfrac{r^n-1}{r-1}\ (r\ne1)$ anything that doubles/halves
$\displaystyle\sum_{i=0}^{n-1} 2^i$ $2^n - 1$ bits, full binary trees, amortized resizing
$\displaystyle\sum_{i=0}^{\infty} a r^i$ $\dfrac{a}{1-r}\ (\lvert r\rvert<1)$ "work halves each level" → constant total
$\displaystyle\sum_{i=1}^{n}\dfrac1i = H_n$ $\Theta(\log n)$ (≈ $\ln n + 0.577$) quicksort avg, harmonic costs — no elementary form
$\displaystyle\sum_{i=1}^{n}\dfrac{1}{i(i+1)}$ $\dfrac{n}{n+1}$ telescoping showcase

Series families at a glance

Arithmetic Geometric
Step rule add $d$ (common difference) multiply by $r$ (common ratio)
Term $a + i d$ $a r^i$
Sum of $n$ terms $n\cdot\dfrac{\text{first}+\text{last}}{2}$ $a\,\dfrac{r^n-1}{r-1}$
Derivation trick write forwards+backwards, add multiply by $r$, subtract
Infinite version diverges (unless $d=0$) converges iff $\lvert r\rvert<1$, to $\dfrac{a}{1-r}$

Decision aid — "how do I evaluate this sum?"

  1. Is the summand constant? → $c\,(n-m+1)$. Done.
  2. Linear in $i$ ($a+id$)? → arithmetic series: $n\cdot\frac{\text{first}+\text{last}}{2}$.
  3. Of the form $a r^i$? → geometric series: $a\frac{r^n-1}{r-1}$ (watch for $r=1$ → $an$).
  4. A power $i^k$? → use the catalog (or derive via telescoping a $(k{+}1)$-power difference).
  5. Summand a consecutive difference $t_i - t_{i-1}$? → telescope to $t_n - t_0$.
  6. None of the above? → split by linearity into pieces you do know, then reassemble.
  7. Still stuck / need a bound? → recognize $\sum 1/i = H_n = \Theta(\log n)$, or estimate growth.

Algorithm-analysis patterns (the CS payoff)

Loop shape Step-count sum Closed form Growth
for i in range(n): for j in range(n): $\sum_{i=0}^{n-1} n$ $n^2$ $\Theta(n^2)$
for i in range(n): for j in range(i+1,n): $\sum_{i=0}^{n-1}(n{-}1{-}i)$ $\frac{n^2-n}{2}$ $\Theta(n^2)$
i=1; while i<n: i*=2 $\sum_{j=0}^{k-1} 1,\ k\approx\log_2 n$ $\log_2 n$ $\Theta(\log n)$
doubling work per pass $\sum_{j=0}^{k-1} 2^j$ $2^k-1 < 2n$ $\Theta(n)$
linear loop × logarithmic loop $\sum_{i=0}^{n-1}\log_2 n$ $n\log_2 n$ $\Theta(n\log n)$

Master move: running time = sum of per-pass work → shift the index to a known sum → collapse → keep the leading term (Big-O discards constants and lower-order terms — formalized in Chapter 14).

Factorial growth (read as "astronomically large")

$$\text{const} \prec \log n \prec n \prec n\log n \prec n^2 \prec 2^n \prec n! \prec n^n$$

  • $n!$ overtakes $2^n$ between $n=3$ and $n=4$; it beats every fixed-base $c^n$ eventually (since $n! \ge (n/2)^{n/2}$, a growing base).
  • Never enumerate $n!$ things for $n \gtrsim 12$: $12!\approx4.8\times10^8$, $20!\approx2.4\times10^{18}$.
  • Overflow: $13!$ exceeds signed 32-bit; $21!$ exceeds 64-bit. (Python ints are arbitrary-precision but still slow/huge.)

Common pitfalls

Pitfall Fix
Translating $\sum_{i=m}^{n}$ as range(m, n) Use range(m, n + 1) — upper limit is inclusive.
$\sum_{i=1}^{n} c = c$ It's $c\,n$ — a constant is summed once per term.
Forgetting the starting index Always state it; verify a closed form against the first 2–3 terms.
$0! = 0$ $0! = 1$ (empty product / one way to order nothing).
Using geometric formula when $r=1$ Division by zero; handle $r=1$ separately ($\sum = an$).
Expecting every sum to have a tidy closed form $H_n$ doesn't — know its growth $\Theta(\log n)$ instead.
Index-shift without compensating Shift limits and rewrite the summand; the terms must not change.

Toolkit additions (dmtoolkit/recurrences.py, continued from Ch. 6)

summation(term, lo, hi)        # sum_{i=lo}^{hi} term(i), inclusive; empty -> 0
arithmetic_sum(first, diff, n) # n*(2*first + (n-1)*diff)//2
geometric_sum(first, ratio, n) # first*(ratio**n - 1)//(ratio - 1), ratio != 1

Pair each closed form with check_identity (Ch. 6) against summation to test it before trusting it — evidence, then (via the proofs in 11.3) certainty.

One-sentence techniques to carry forward

  • Arithmetic: fold the sum onto itself (forwards + backwards), every column is first + last.
  • Geometric: multiply by $r$ and subtract; the middle cancels.
  • Telescoping: rewrite the summand as a consecutive difference; only the endpoints survive — and this derives power-sum formulas, it doesn't just verify them.
  • Closed form vs. recurrence: the same sequence; closed form is $O(1)$ random access, a recurrence is $O(n)$ sequential — converting one to the other is the work of Chapters 18–19.