Appendix A: Summations

When an algorithm contains an iterative control construct such as a while or for loop, we can express its running time as the sum of the times spent on each execution of the body of the loop. Knowing how to manipulate and bound summations is essential for analyzing algorithms.

---

A.1 Summation Formulas and Properties

Given a sequence a₁, a₂, …, aₙ of numbers (where n is a nonnegative integer), the finite sum is written as:

$$\sum_{k=1}^{n} a_k$$

• If n = 0, the value of the summation is defined to be 0.
• The value of a finite series is always well defined, and terms can be added in any order.

For an infinite series:

$$\sum_{k=1}^{\infty} a_k = \lim_{n \to \infty} \sum_{k=1}^{n} a_k$$

• If the limit does not exist, the series diverges; otherwise, it converges.
• Terms of a convergent series cannot always be rearranged freely.
• Terms of an absolutely convergent series (where ∑|aₖ| also converges) can be rearranged in any order.

---

Linearity

For any real number c and any finite sequences a₁, a₂, …, aₙ and b₁, b₂, …, bₙ:

$$\sum_{k=1}^{n} (ca_k + b_k) = c \sum_{k=1}^{n} a_k + \sum_{k=1}^{n} b_k$$

• Linearity also applies to infinite convergent series.
• Linearity can be exploited with asymptotic notation:

$$\sum_{k=1}^{n} \Theta(f(k)) = \Theta!\left(\sum_{k=1}^{n} f(k)\right)$$

(Θ on the left applies to variable k; on the right, it applies to n.)

---

Arithmetic Series

The summation of the first n positive integers:

$$\sum_{k=1}^{n} k = 1 + 2 + \cdots + n = \frac{n(n+1)}{2} = \Theta(n^2)$$

This is the arithmetic series — one of the most fundamental summation formulas. (A.1, A.2)

---

Sums of Squares and Cubes

• Sum of squares:

$$\sum_{k=0}^{n} k^2 = \frac{n(n+1)(2n+1)}{6} \quad \text{(A.3)}$$

• Sum of cubes:

$$\sum_{k=0}^{n} k^3 = \frac{n^2(n+1)^2}{4} \quad \text{(A.4)}$$

---

Geometric Series

For real x ≠ 1, the geometric (exponential) series is:

$$\sum_{k=0}^{n} x^k = 1 + x + x^2 + \cdots + x^n = \frac{x^{n+1} - 1}{x - 1} \quad \text{(A.5)}$$

For the infinite decreasing geometric series (|x| < 1):

$$\sum_{k=0}^{\infty} x^k = \frac{1}{1 - x} \quad \text{(A.6)}$$

• These formulas apply even when x = 0 (since 0⁰ = 1 by convention).

---

Harmonic Series

The nth harmonic number is:

$$H_n = 1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \cdots + \frac{1}{n} = \sum_{k=1}^{n} \frac{1}{k} = \ln n + O(1) \quad \text{(A.7)}$$

• The harmonic series grows logarithmically.

---

Integrating and Differentiating Series

Additional formulas arise by differentiating or integrating known series. For example, differentiating the infinite geometric series (A.6) and multiplying by x gives:

$$\sum_{k=0}^{\infty} kx^k = \frac{x}{(1-x)^2} \quad \text{for } |x| < 1 \quad \text{(A.8)}$$

---

Telescoping Series

For any sequence a₀, a₁, …, aₙ:

$$\sum_{k=1}^{n} (a_k - a_{k-1}) = a_n - a_0 \quad \text{(A.9)}$$

• Each intermediate term a₁, a₂, …, aₙ₋₁ is added once and subtracted once — the sum telescopes.
• Equivalently: ∑_{k=0}^{n-1} (aₖ − aₖ₊₁) = a₀ − aₙ

Example: Evaluate ∑_{k=1}^{n-1} 1/(k(k+1)).

1. Rewrite each term using partial fractions: 1/(k(k+1)) = 1/k − 1/(k+1)
2. The sum telescopes:

$$\sum_{k=1}^{n-1} \frac{1}{k(k+1)} = \sum_{k=1}^{n-1}\left(\frac{1}{k} - \frac{1}{k+1}\right) = 1 - \frac{1}{n}$$

---

Products

The finite product a₁ · a₂ · … · aₙ is written as:

$$\prod_{k=1}^{n} a_k$$

• If n = 0, the product is defined to be 1.
• Products can be converted to summations via logarithms:

$$\lg!\left(\prod_{k=1}^{n} a_k\right) = \sum_{k=1}^{n} \lg a_k$$

---

A.2 Bounding Summations

Several techniques exist for bounding summations that describe algorithm running times.

---

Mathematical Induction

The most basic way to evaluate a series is mathematical induction.

Example — Arithmetic series: Prove ∑_{k=1}^{n} k = n(n+1)/2.

1. Base case: n = 1 → 1 = 1·2/2 ✓
2. Inductive step: Assume it holds for n. Then for n+1:

$$\sum_{k=1}^{n+1} k = \sum_{k=1}^{n} k + (n+1) = \frac{n(n+1)}{2} + (n+1) = \frac{(n+1)(n+2)}{2}$$

Induction can also prove bounds (not just exact values):

• Example: Prove ∑{k=0}^{n} 3^k = O(3^n), i.e., ∑{k=0}^{n} 3^k ≤ c·3^n for some constant c.
  • Base: 1 ≤ c·1 when c ≥ 1.
  • Inductive step: ∑_{k=0}^{n+1} 3^k ≤ c·3^n + 3^{n+1} = (1/3 + 1/c)·c·3^{n+1} ≤ c·3^{n+1} when c ≥ 3/2.

Common pitfall with asymptotic induction: Be careful that the hidden constant in O-notation does not grow with n. A fallacious proof that ∑_{k=1}^{n} k = O(n) fails because the constant hidden by big-O grows with n — the same constant must work for all n.

---

Bounding the Terms

Bound each term of the series by the largest term:

$$\sum_{k=1}^{n} a_k \leq n \cdot a_{\max} \quad \text{where } a_{\max} = \max_{1 \leq k \leq n} a_k$$

Example: ∑{k=1}^{n} k ≤ ∑{k=1}^{n} n = n² (a quick but loose upper bound).

Bounding by a geometric series (tighter method):

• If aₖ₊₁/aₖ ≤ r for all k ≥ 0, where 0 < r < 1 is a constant, then aₖ ≤ a₀·rᵏ, and:

$$\sum_{k=0}^{n} a_k \leq \sum_{k=0}^{\infty} a_0 r^k = \frac{a_0}{1 - r}$$

Example: ∑_{k=1}^{∞} k/3^k

• Rewrite as ∑_{k=0}^{∞} (k+1)/3^{k+1}, so a₀ = 1/3.
• Ratio of consecutive terms: (k+2)/(3(k+1)) ≤ 2/3 for all k ≥ 0.
• Therefore: ∑ ≤ (1/3)·(1/(1−2/3)) = 1.

Important warning: Showing that the ratio of consecutive terms is less than 1 is not sufficient. You must show the ratio is bounded by a constant r < 1. The harmonic series has ratio k/(k+1) < 1 but still diverges because no fixed r < 1 bounds all ratios.

---

Splitting Summations

Express a series as the sum of two or more series by partitioning the index range, then bound each part separately.

Example — Lower bound on arithmetic series:

$$\sum_{k=1}^{n} k = \sum_{k=1}^{n/2} k + \sum_{k=n/2+1}^{n} k \geq 0 + \sum_{k=n/2+1}^{n} \frac{n}{2} = \frac{n^2}{4} = \Omega(n^2)$$

Combined with the O(n²) upper bound, this gives Θ(n²).

Ignoring initial constant terms: For ∑_{k=0}^{n} aₖ where each aₖ is independent of n:

$$\sum_{k=0}^{n} a_k = \underbrace{\sum_{k=0}^{k_0-1} a_k}{\Theta(1)} + \sum{k=k_0}^{n} a_k$$

Then apply other methods to the remaining sum.

Example: Bound ∑_{k=0}^{∞} k²/2^k.

• For k ≥ 3, the ratio of consecutive terms is (k+1)²/(2k²) ≤ 8/9.
• Split: ∑{k=0}^{2} k²/2^k + ∑{k=3}^{∞} k²/2^k ≤ O(1) + (9/8)·∑(8/9)^k = O(1).

Bounding the harmonic series by splitting:

Split the range 1 to n into ⌊lg n⌋ + 1 pieces, where the i-th piece covers indices from 2^i to 2^{i+1} − 1. Each piece contributes at most 1 to the sum:

$$H_n = \sum_{k=1}^{n} \frac{1}{k} \leq \sum_{i=0}^{\lfloor \lg n \rfloor} \sum_{j=0}^{2^i - 1} \frac{1}{2^i} = \sum_{i=0}^{\lfloor \lg n \rfloor} 1 \leq \lg n + 1 \quad \text{(A.10)}$$

---

Approximation by Integrals

When a summation has the form ∑_{k=m}^{n} f(k) and f(k) is monotonic, we can approximate it with integrals.

For monotonically increasing f(k):

$$\int_{m-1}^{n} f(x),dx \leq \sum_{k=m}^{n} f(k) \leq \int_{m}^{n+1} f(x),dx \quad \text{(A.11)}$$

For monotonically decreasing f(k):

$$\int_{m}^{n+1} f(x),dx \leq \sum_{k=m}^{n} f(k) \leq \int_{m-1}^{n} f(x),dx \quad \text{(A.12)}$$

The idea: the summation represents the area of unit-width rectangles, while the integral is the area under the curve. Shifting the rectangles left or right relative to the curve yields the lower and upper bounds.

Example — Tight bounds on the harmonic series:

• Lower bound (using A.12 for decreasing f(k) = 1/k):

$$\sum_{k=1}^{n} \frac{1}{k} \geq \int_{1}^{n+1} \frac{dx}{x} = \ln(n+1) \quad \text{(A.13)}$$

• Upper bound:

$$\sum_{k=2}^{n} \frac{1}{k} \leq \int_{1}^{n} \frac{dx}{x} = \ln n$$

Adding the k = 1 term back:

$$\sum_{k=1}^{n} \frac{1}{k} \leq \ln n + 1 \quad \text{(A.14)}$$

Together: ln(n+1) ≤ Hₙ ≤ ln n + 1, confirming Hₙ = ln n + Θ(1).

---

Summary of Key Formulas

Summary of Bounding Techniques