Day 21 — Summation notation

Updated

July 30, 2026

Day 21 — Summation notation

Stage II · concept day
Goal: Read and manipulate \(\sum\) notation; shift indices; use linearity; know closed forms for \(\sum i\), \(\sum i^2\), and geometric series; recognize telescoping sums; introduce double sums; connect to nested loops.

Why this matters

Summation is the language of loop costs, discrete averages, series, and algorithm analysis. Closed forms turn \(O(1)+O(2)+\cdots+O(n)\) into \(\Theta(n^2)\). Telescoping appears in potential-method amortized analysis (idea). Double sums are nested loops.

Theory

Notation

\[\sum_{i=a}^{b} f(i)=f(a)+f(a+1)+\cdots+f(b)\] when \(a,b\in\mathbb{Z}\) and \(a\le b\). If \(a>b\), the sum is empty \(=0\) by convention.

  • \(i\) is the index (dummy variable).
  • \(a\) lower limit, \(b\) upper limit.
  • \(f(i)\) summand.

\[\sum_{i=1}^{n} i = 1+2+\cdots+n.\]

Index shifts

\[\sum_{i=1}^{n} f(i)=\sum_{k=0}^{n-1} f(k+1)=\sum_{j=2}^{n+1} f(j-1).\]

Reindex carefully: when \(i\to i+1\), limits shift by the same amount.

Linearity

For constants \(\alpha,\beta\): \[\sum_{i=a}^{b}\bigl(\alpha f(i)+\beta g(i)\bigr)=\alpha\sum_{i=a}^{b} f(i)+\beta\sum_{i=a}^{b} g(i).\]

Proof. Distribute addition in the finite expanded sum. \(\square\)

Also: \(\sum_{i=a}^{b} c = c\cdot (b-a+1)\) for constant \(c\) (number of terms).

Closed form: \(\sum i\)

Theorem. \[\sum_{i=1}^{n} i=\frac{n(n+1)}{2}.\]

Proof (Gauss pairing). \((1+n)+(2+(n-1))+\cdots\) gives \(n/2\) pairs each summing to \(n+1\) if \(n\) even; similar if odd.

Proof (induction). Base \(n=1\): \(1=1\). Inductive: \(\frac{n(n+1)}{2}+(n+1)=\frac{(n+1)(n+2)}{2}\). \(\square\)

Closed form: \(\sum i^2\)

Theorem. \[\sum_{i=1}^{n} i^2=\frac{n(n+1)(2n+1)}{6}.\]

Proof. Induction, or from \((i+1)^3-i^3=3i^2+3i+1\) summed (telescoping cubic). \(\square\)

Geometric series

For \(r\neq 1\): \[\sum_{i=0}^{n} r^{i}=\frac{r^{n+1}-1}{r-1}=\frac{1-r^{n+1}}{1-r}.\]

Proof. Let \(S=\sum_{i=0}^{n} r^{i}\). Then \(rS=\sum_{i=1}^{n+1} r^{i}\), so \(S-rS=1-r^{n+1}\). \(\square\)

If \(|r|<1\), infinite sum \(\sum_{i=0}^{\infty} r^{i}=\frac{1}{1-r}\) (Stage later); finite form always primary today.

Special: \(\sum_{i=0}^{n} 2^{i}=2^{n+1}-1\).

Telescoping sums

If summand is a difference \(f(i)-f(i+1)\) or \(f(i+1)-f(i)\): \[\sum_{i=1}^{n}\bigl(f(i)-f(i+1)\bigr)=f(1)-f(n+1).\]

Classic: \(\dfrac{1}{i(i+1)}=\dfrac{1}{i}-\dfrac{1}{i+1}\) (partial fractions Day 17).

\[\sum_{i=1}^{n}\frac{1}{i(i+1)}=1-\frac{1}{n+1}=\frac{n}{n+1}.\]

Double sums

\[\sum_{i=1}^{m}\sum_{j=1}^{n} a_{ij}=\sum_{j=1}^{n}\sum_{i=1}^{m} a_{ij}\] for finite sums (absolute convergence automatic for finite).

If \(a_{ij}=f(i)g(j)\) separates: \(\bigl(\sum_i f(i)\bigr)\bigl(\sum_j g(j)\bigr)\).

Region sums: \(\sum_{i=1}^{n}\sum_{j=1}^{i} 1=\sum_{i=1}^{n} i=\frac{n(n+1)}{2}\) — triangle of pairs \((i,j)\) with \(1\le j\le i\le n\).

Connection to nested loops

count = 0
for i = 1..n:
  for j = 1..i:
    count += 1

runs \(\sum_{i=1}^{n} i = n(n+1)/2\) times.

Outer \(n\), inner \(m\) independent: \(nm\) iterations \(=\sum_{i=1}^{n}\sum_{j=1}^{m} 1\).

Worked examples

Example 1 — Expand

\(\sum_{k=3}^{6} (2k-1)=5+7+9+11=32\).

Example 2 — Linearity

\(\sum_{i=1}^{n}(3i+2)=3\cdot\frac{n(n+1)}{2}+2n=\frac{3n(n+1)+4n}{2}\).

Example 3 — Shift

\(\sum_{i=2}^{n} i=\bigl(\sum_{i=1}^{n} i\bigr)-1=\frac{n(n+1)}{2}-1\).

Example 4 — Geometric

\(\sum_{i=0}^{5} 3^{i}=\frac{3^{6}-1}{3-1}=\frac{729-1}{2}=364\).

Example 5 — Geometric factor

\(\sum_{i=1}^{n} 2^{i}=2\frac{2^{n}-1}{2-1}=2^{n+1}-2\).

Example 6 — Telescoping

\(\sum_{i=1}^{n}\bigl(\frac{1}{i}-\frac{1}{i+1}\bigr)=1-\frac{1}{n+1}\).

Example 7 — \(i^2\)

\(\sum_{i=1}^{10} i^2=\frac{10\cdot 11\cdot 21}{6}=385\).

Example 8 — Double

\(\sum_{i=1}^{2}\sum_{j=1}^{3} (i+j)=\sum_{i=1}^{2}\bigl((i+1)+(i+2)+(i+3)\bigr)=\sum_{i=1}^{2}(3i+6)=3\sum i+12=9+12=21\) for \(i\) to \(2\): \(3(1+2)+2\cdot 6=9+12=21\).

Example 9 — Triangle

\(\sum_{i=1}^{n}\sum_{j=1}^{i} j=\sum_{i=1}^{n}\frac{i(i+1)}{2}=\frac{1}{2}\sum(i^2+i)=\frac{1}{2}\bigl(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\bigr)\).

Example 10 — Factor out

\(\sum_{i=1}^{n} 5=5n\).

Example 11 — Change index

\(\sum_{k=0}^{n-1} (k+1)=\sum_{i=1}^{n} i=\frac{n(n+1)}{2}\).

Example 12 — Loop cost

for i in 1..n: for j in 1..n: O(1) → \(n^2\) ops.
for i in 1..n: for j in 1..i: O(1) → \(n(n+1)/2\).

Example 13 — Arithmetic series

\(\sum_{i=0}^{n-1} (a+id)=n a + d\frac{(n-1)n}{2}\).

Example 14 — Finite geometric decay

\(\sum_{i=0}^{n} \bigl(\frac{1}{2}\bigr)^{i}=\frac{1-(1/2)^{n+1}}{1-1/2}=2\bigl(1-2^{-(n+1)}\bigr)<2\).

Exercises

Easy

  1. Expand \(\sum_{i=1}^{4} i^{2}\).
  2. Compute \(\sum_{i=1}^{100} 1\).
  3. Compute \(\sum_{i=1}^{n} 4\) in closed form.
  4. Evaluate \(\sum_{i=0}^{3} 2^{i}\).
  5. Write \(1+3+5+7\) in \(\sum\) notation.

Medium

  1. Prove \(\sum_{i=1}^{n} i=\frac{n(n+1)}{2}\) by induction.
  2. Compute \(\sum_{i=1}^{n} (2i-1)\) (odd numbers); simplify closed form.
  3. Compute \(\sum_{i=0}^{n} 5\cdot 3^{i}\).
  4. Reindex \(\sum_{i=3}^{n} (i-2)\) to start at \(j=1\).
  5. Telescoping: \(\sum_{i=1}^{n}\bigl(\frac{1}{2i-1}-\frac{1}{2i+1}\bigr)\).
  6. Double sum \(\sum_{i=1}^{n}\sum_{j=1}^{m} 1\).
  7. \(\sum_{i=1}^{n}\sum_{j=1}^{i} 1\).
  8. Use \(\sum i^{2}\) to get \(\sum_{i=1}^{n} (i+1)^{2}\) with a shift.

Hard / proof

  1. Prove the geometric sum formula for \(r\neq 1\).
  2. Prove \(\sum_{i=1}^{n} i^{2}=\frac{n(n+1)(2n+1)}{6}\) by induction.
  3. From \((i+1)^{3}-i^{3}=3i^{2}+3i+1\), sum and derive the \(i^{2}\) formula (assuming \(\sum i\) known).
  4. Show \(\sum_{i=1}^{n}\frac{1}{i(i+1)}=\frac{n}{n+1}\).
  5. Prove linearity for finite sums from definition.
  6. Evaluate \(\sum_{1\le j\le i\le n} 1\) two ways.
  7. Find closed form \(\sum_{i=1}^{n} i\cdot r^{i}\) for \(r\neq 1\) (differentiate geometric or formula \(r\frac{1-(n+1)r^{n}+nr^{n+1}}{(1-r)^{2}}\)).

Challenge / CS-flavored

  1. Nested loops: \(i=0..n-1\), \(j=i..n-1\) — express iteration count as a sum and closed form.
  2. Cost \(\sum_{i=1}^{n} \Theta(i)=\Theta(n^{2})\) — justify using sum bounds (optional sandwich).
  3. Binary heap height ideas: \(\sum_{k=0}^{h} 2^{k}=2^{h+1}-1\) nodes in perfect tree.
  4. Prefix sums: \(S_k=\sum_{i=1}^{k} a_i\) — write \(a_k\) as telescoping \(S_k-S_{k-1}\).
  5. Compare \(\sum_{i=1}^{n} \log i\) vs \(n\log n\) qualitatively (integral intuition OK).

Summation bounds (algorithm analysis seed)

For increasing \(f\), \[\int_{0}^{n} f(x)\,dx \le \sum_{i=1}^{n} f(i) \le f(n)+\int_{0}^{n-1} f(x)\,dx\] (integral test pictures)—optional calculus. Cruder: \(n\cdot \min f \le \sum f \le n\cdot\max f\) on finite ranges.

Arithmetic series general

First term \(a\), common difference \(d\), \(n\) terms: \[S=\frac{n}{2}\bigl(2a+(n-1)d\bigr)=\frac{n}{2}(\text{first}+\text{last}).\]

Empty and singleton sums

\(\sum_{i=1}^{0}=0\) empty. \(\sum_{i=5}^{5} f(i)=f(5)\).

Changing order in dependent double sums

\(\sum_{i=1}^{n}\sum_{j=1}^{i} a_{ij}=\sum_{j=1}^{n}\sum_{i=j}^{n} a_{ij}\) by switching the triangle region \(1\le j\le i\le n\).

Extra exercises

  1. Prove arithmetic series formula by pairing or induction.
  2. Evaluate \(\sum_{i=1}^{n} (i^{2}-i)\).
  3. Switch order: \(\sum_{i=1}^{n}\sum_{j=i}^{n} 1\).
  4. Closed form \(\sum_{i=0}^{n} (2i+1)= (n+1)^{2}\) (odds).
  5. Cost of for i=1..n: for j=1..i: for k=1..j: O(1) as a triple sum; simplify to \(\binom{n+2}{3}\) or \(\frac{n(n+1)(n+2)}{6}\).

CS connection

Runtime of nested loops is double sums. Series closed forms give exact operation counts. Geometric sums model binary trees, geometric backoff totals, and residual geometric series in hashing analyses. Telescoping is the discrete fundamental theorem of calculus.

Common pitfalls

Pitfall What to do instead
Off-by-one limits Count terms: \(b-a+1\)
Forgetting \(i=0\) term in geometric Check lower limit
\(\sum i = n^{2}/2\) without \(+n/2\) Use \(\frac{n(n+1)}{2}\)
Moving index without shifting limits Always adjust bounds
Infinite geometric with \(|r|\ge 1\) Finite formula only unless \(|r|<1\)
Nested loop both to \(n\) as \(n\) not \(n^{2}\) Independent loops multiply

Fully worked extra examples

E15 — Linearity combo.
\(\sum_{i=1}^{n}(i^{2}+3i+2)=\frac{n(n+1)(2n+1)}{6}+3\cdot\frac{n(n+1)}{2}+2n\). Factor \(n\) if desired.

E16 — Geometric application.
Binary tree nodes levels \(0..h\): \(\sum_{k=0}^{h}2^{k}=2^{h+1}-1\).

E17 — Telescoping partial fractions.
\(\sum_{i=1}^{n}\frac{1}{i(i+1)}=\sum_{i=1}^{n}\bigl(\frac{1}{i}-\frac{1}{i+1}\bigr)=1-\frac{1}{n+1}\).

E18 — Double sum separate.
\(\sum_{i=1}^{m}\sum_{j=1}^{n} ij=\bigl(\sum_{i=1}^{m} i\bigr)\bigl(\sum_{j=1}^{n} j\bigr)=\frac{m(m+1)}{2}\cdot\frac{n(n+1)}{2}\).

E19 — Triangle count two ways.
Number of pairs \(1\le j\le i\le n\) equals \(\sum_{i=1}^{n} i=\binom{n+1}{2}\).

End-of-day synthesis problems

S1. Prove \(\sum_{i=1}^{n} i=\frac{n(n+1)}{2}\) by induction with base and inductive step written fully.

S2. Closed form \(\sum_{i=1}^{n} (4i-1)\).

S3. Geometric \(\sum_{i=0}^{n} (\frac{1}{3})^{i}\).

S4. Telescoping \(\sum_{i=1}^{n} \bigl(\frac{1}{i}-\frac{1}{i+2}\bigr)\) (partial expand first terms/last).

S5. Double: \(\sum_{i=1}^{n}\sum_{j=1}^{i} j\) simplified.

S6. Loop for i=1..n: for j=i..n: cost 1 — exact count.

S7. Reindex \(\sum_{i=0}^{n-1} (i+1)^{2}\) into a sum starting at \(1\).

S8. Prove geometric sum formula via \(S-rS\).

Checkpoint

  • Expand and reindex sums
  • Apply linearity and constant sums
  • Use \(\sum i\), \(\sum i^{2}\), geometric closed forms
  • Recognize and evaluate telescoping sums
  • Translate nested loops into double sums
  • S1 and S8 as must-pass proofs

Write two takeaways in your own words.

Deep dive — sums, closed forms, double sums, loops

D1 — Induction for \(\sum i\) fully written.
Claim \(P(n):\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\).
Base \(n=1\): \(1=1\).
Inductive: assume \(P(n)\); then \(\sum_{i=1}^{n+1}i=\frac{n(n+1)}{2}+(n+1)=\frac{n(n+1)+2(n+1)}{2}=\frac{(n+1)(n+2)}{2}\).

D2 — Linearity combo closed form.
\(\sum_{i=1}^{n}(4i-1)=4\cdot\frac{n(n+1)}{2}-n=2n(n+1)-n=n(2n+2-1)=n(2n+1)\).

D3 — Geometric sum via \(S-rS\).
\(S=\sum_{i=0}^{n}r^{i}\), \(rS=\sum_{i=1}^{n+1}r^{i}\), \(S-rS=1-r^{n+1}\), so \(S=\frac{1-r^{n+1}}{1-r}\) for \(r\neq 1\).
Special: \(\sum_{i=0}^{n}2^{i}=2^{n+1}-1\).

D4 — Telescoping with gap \(2\).
\(\sum_{i=1}^{n}\bigl(\frac{1}{i}-\frac{1}{i+2}\bigr)=\bigl(1+\frac12+\frac13+\cdots+\frac{1}{n}\bigr)-\bigl(\frac{1}{3}+\cdots+\frac{1}{n+2}\bigr)=1+\frac12-\frac{1}{n+1}-\frac{1}{n+2}\).

D5 — Triangle double sum.
\(\sum_{i=1}^{n}\sum_{j=1}^{i}1=\sum_{i=1}^{n}i=\frac{n(n+1)}{2}\).
\(\sum_{i=1}^{n}\sum_{j=1}^{i}j=\sum_{i=1}^{n}\frac{i(i+1)}{2}=\frac12\sum(i^{2}+i)=\frac12\Bigl(\frac{n(n+1)(2n+1)}{6}+\frac{n(n+1)}{2}\Bigr)\).

D6 — Nested loop exact counts.
for i=1..n: for j=1..n → \(n^{2}\).
for i=1..n: for j=1..i → \(n(n+1)/2\).
for i=1..n: for j=i..n → also \(n(n+1)/2\) (same triangle, reindexed).

D7 — Separable double sum.
\(\sum_{i=1}^{m}\sum_{j=1}^{n}ij=\bigl(\sum_{i=1}^{m}i\bigr)\bigl(\sum_{j=1}^{n}j\bigr)=\frac{m(m+1)n(n+1)}{4}\).

Extra practice set

  1. Closed form \(\sum_{i=1}^{n}(i^{2}+3i+2)\).
  2. Evaluate \(\sum_{i=0}^{n}(\frac13)^{i}\).
  3. Switch order: \(\sum_{i=1}^{n}\sum_{j=i}^{n}1\); simplify.
  4. Prove geometric formula for \(r\neq 1\) from scratch.
  5. Triple loop i=1..n, j=1..i, k=1..j: write as a sum; recognize \(\frac{n(n+1)(n+2)}{6}\).

Tomorrow

Day 22 — Gate II. Mixed algebra/functions/\(\sum\) portfolio; include a \(2\times 2\) matrix system and a \(\sum\) closed form; sections with answer keys for half.