• Overview
• Details
• Exercises

Summations compactly represent finite sums, while series extend to infinite sums. In algorithms, closed-form summations and growth rates are used to analyze runtimes and counts.

• Notation: \( \sum_{i=a}^{b} f(i) \), index shifts, splitting, linearity
• Common sums: arithmetic (n(n+1)/2), geometric ((1-r^{n})/(1-r)), squares (n(n+1)(2n+1)/6)
• Telescoping techniques and change of variables
• Asymptotics: harmonic numbers H_n = \Theta(\log n), geometric tail bounds
• Infinite series basics: convergence tests (ratio, comparison), geometric series \sum r^k = 1/(1-r) for |r|<1

1. Prove \(\sum_{i=1}^{n} i = n(n+1)/2\) by induction and via pairing.
2. Evaluate \(\sum_{k=0}^{n} 2^k\) and give a tight \Theta(\cdot) bound.
3. Show that H_n = \sum_{k=1}^{n} 1/k = \Theta(\log n) using integral bounds.