AOCP/Infinite Series

Knuth Volume 1: Fundamental Algorithms

Chapter 1: Basic Concepts: Infinite Series

Definitions

An infinite series is a sum of infinitely many terms:

$ \sum_{k=0}^{\infty} a_k = a_0 + a_1 + a_2 + \dots $

The infinite series is defined as the limit of its partial sums:

$ S_n = \sum_{k=0}^{n} a_k $

If $ \lim_{n \to \infty} S_n = S $ exists and is finite, the series converges to $ S $. Otherwise, it diverges.

In Knuth's treatment, infinite series appear throughout the mathematical preliminaries: in sums and products (Section 1.2.3), harmonic numbers (Section 1.2.7), Fibonacci numbers (Section 1.2.8), generating functions (Section 1.2.9), and the analysis of algorithms (Section 1.2.10).

Absolute and Conditional Convergence

A series $ \sum a_k $ is absolutely convergent if $ \sum |a_k| $ converges.

If a series converges but is not absolutely convergent, it is conditionally convergent.

Knuth notes that absolutely convergent series can be manipulated much more freely than conditionally convergent series. For absolutely convergent series, we can:

• Rearrange terms arbitrarily
• Multiply series together
• Group terms in any way

Conditionally convergent series require more care: rearranging terms can change the sum, or even cause divergence.

The Geometric Series

The geometric series is the most fundamental infinite series:

$ \sum_{k=0}^{\infty} x^k = 1 + x + x^2 + x^3 + \dots = \dfrac{1}{1-x} \qquad |x| < 1 $

This is derived by considering the partial sum:

$ S_n = \sum_{k=0}^{n} x^k $

Multiplying by $ (1-x) $ yields the telescoping sum:

$ (1-x) S_n = (1 + x + x^2 + \dots + x^n) - (x + x^2 + \dots + x^{n+1}) = 1 - x^{n+1} $

Thus:

$ S_n = \dfrac{1 - x^{n+1}}{1 - x} $

When $ |x| < 1 $, $ x^{n+1} \to 0 $ as $ n \to \infty $, giving the closed form:

$ \sum_{k=0}^{\infty} x^k = \dfrac{1}{1-x} $

A closely related form generalizes this:

$ \sum_{k=0}^{\infty} a x^k = \dfrac{a}{1 - x} \qquad |x| < 1 $

and more generally:

$ \sum_{k=0}^{\infty} (a x^k) = \dfrac{a}{1 - x} $

and:

$ \sum_{k=0}^{\infty} x^{k} (a) = a \dfrac{1}{1-x} $

For the shifted series:

$ \sum_{k=m}^{\infty} x^k = \dfrac{x^m}{1 - x} \qquad |x| < 1 $

The Finite Geometric Sum

Before taking limits, the finite geometric sum is:

$ \sum_{k=0}^{n} x^k = \dfrac{1 - x^{n+1}}{1 - x} \qquad x \neq 1 $

When $ x = 1 $, each term contributes 1, so:

$ \sum_{k=0}^{n} 1 = n + 1 $

The Harmonic Series

The harmonic series is defined as:

$ H_{\infty} = \sum_{k=1}^{\infty} \dfrac{1}{k} = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dots $

This series diverges, though it does so very slowly. The partial sums are the harmonic numbers (see AOCP/Harmonic Numbers):

$ H_n = \sum_{k=1}^{n} \dfrac{1}{k} $

Knuth proves divergence by showing:

$ H_{2^m} \geq 1 + \dfrac{m}{2} $

which grows without bound as $ m \to \infty $.

The harmonic series is important in the analysis of algorithms, where it frequently appears in the form $ H_n \approx \ln n + \gamma $, with $ \gamma $ being the Euler-Mascheroni Constant.

The Exponential Series

The exponential series defines the constant $ e $:

$ e^z = \sum_{k=0}^{\infty} \dfrac{z^k}{k!} = 1 + z + \dfrac{z^2}{2!} + \dfrac{z^3}{3!} + \dots $

This series converges for all real and complex $ z $. In particular:

$ e = \sum_{k=0}^{\infty} \dfrac{1}{k!} = 1 + 1 + \dfrac{1}{2} + \dfrac{1}{6} + \dfrac{1}{24} + \dots $

The exponential generating function $ \sum a_k \frac{z^k}{k!} $ is a key tool in combinatorics, discussed extensively in Section 1.2.9.

The Logarithm Series

Knuth gives two important logarithm series:

$ \ln(1+z) = \sum_{k=1}^{\infty} \dfrac{(-1)^{k+1}}{k} z^k = z - \dfrac{z^2}{2} + \dfrac{z^3}{3} - \dfrac{z^4}{4} + \dots \qquad |z| < 1 $

$ \ln \left( \dfrac{1}{1-z} \right) = \sum_{k=1}^{\infty} \dfrac{z^k}{k} = z + \dfrac{z^2}{2} + \dfrac{z^3}{3} + \dfrac{z^4}{4} + \dots \qquad |z| < 1 $

Note the connection to harmonic numbers: the coefficients of the second series are $ \frac{1}{k} $, which are the terms of the harmonic series.

The Binomial Series

The binomial theorem extends to infinite series when the exponent is not a nonnegative integer:

$ (1 + z)^r = \sum_{k=0}^{\infty} \binom{r}{k} z^k $

This converges for $ |z| < 1 $ when $ r $ is arbitrary, and for all $ z $ when $ r $ is a nonnegative integer (in which case it terminates).

When $ r $ is a negative integer, we obtain an important special case:

$ \dfrac{1}{(1-z)^{n+1}} = \sum_{k=0}^{\infty} \binom{n+k}{n} z^k $

For example, when $ n = 0 $:

$ \dfrac{1}{1-z} = \sum_{k=0}^{\infty} z^k $

which is the geometric series.

Differentiation and Integration of Series

For a generating function $ G(z) = a_0 + a_1 z + a_2 z^2 + \dots $, we can differentiate:

$ G'(z) = a_1 + 2 a_2 z + 3 a_3 z^2 + \dots = \sum_{k \geq 0} (k+1) a_{k+1} z^k $

and integrate:

$ \int_{0}^{z} G(t) dt = a_0 z + \dfrac{1}{2} a_1 z^2 + \dfrac{1}{3} a_2 z^3 + \dots = \sum_{k \geq 1} \dfrac{1}{k} a_{k-1} z^k $

These operations, applied to known series, generate new ones. For example, differentiating the geometric series:

$ \dfrac{d}{dz} \left( \dfrac{1}{1-z} \right) = \dfrac{1}{(1-z)^2} = \sum_{k \geq 0} (k+1) z^k = 1 + 2z + 3z^2 + 4z^3 + \dots $

Integrating the geometric series gives:

$ \int_{0}^{z} \dfrac{dt}{1-t} = \ln \left( \dfrac{1}{1-z} \right) = \sum_{k \geq 1} \dfrac{z^k}{k} $

Telescoping Series

A telescoping series is one in which most terms cancel. The general form is:

$ \sum_{k=0}^{n} (b_{k+1} - b_k) = b_{n+1} - b_0 $

For an infinite telescoping series, if $ \lim_{n \to \infty} b_n = L $, then:

$ \sum_{k=0}^{\infty} (b_{k+1} - b_k) = L - b_0 $

This technique is used throughout Knuth's text, particularly in Section 1.2.3 (Sums and Products). A classic example:

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

Taking the limit as $ n \to \infty $:

$ \sum_{k=1}^{\infty} \dfrac{1}{k(k+1)} = 1 $

Alternating Series

An alternating series has terms that alternate in sign:

$ \sum_{k=0}^{\infty} (-1)^k a_k = a_0 - a_1 + a_2 - a_3 + \dots $

The alternating harmonic series converges (conditionally):

$ \sum_{k=1}^{\infty} \dfrac{(-1)^{k+1}}{k} = 1 - \dfrac{1}{2} + \dfrac{1}{3} - \dfrac{1}{4} + \dots = \ln 2 $

Knuth uses alternating series in several identities, such as:

$ \sum_{k} \binom{n}{k} (-1)^k = (1-1)^n = 0^n $

which equals $ 1 $ when $ n = 0 $ and $ 0 $ when $ n > 0 $.

Infinite Series in Generating Functions

A generating function $ G(z) $ for a sequence $ \langle a_n \rangle $ is the infinite series:

$ G(z) = a_0 + a_1 z + a_2 z^2 + a_3 z^3 + \dots = \sum_{k \geq 0} a_k z^k $

Knuth treats these as formal power series: the question of convergence is often set aside, and operations on the series are justified algebraically. When convergence matters, the series is considered within its radius of convergence.

The key operations on generating functions (addition, shifting, multiplication, differentiation, integration) all correspond to operations on the underlying infinite series. See AOCP/Generating Functions.

Sum of a Sequence via Generating Functions

If $ G(z) = \sum_{k \geq 0} a_k z^k $ is the generating function for $ \langle a_n \rangle $, then the generating function for the partial sums is:

$ \dfrac{1}{1-z} G(z) = \sum_{n \geq 0} \left( \sum_{k=0}^{n} a_k \right) z^n $

This follows from multiplying $ G(z) $ by the geometric series $ \frac{1}{1-z} = \sum_{k \geq 0} z^k $.

Convergence Tests

Knuth mentions several tests for convergence, including:

Ratio Test: For a series $ \sum a_k $ with positive terms, if:

$ \lim_{k \to \infty} \left| \dfrac{a_{k+1}}{a_k} \right| = L $

then the series converges absolutely if $ L < 1 $ and diverges if $ L > 1 $.

Comparison Test: If $ 0 \leq a_k \leq b_k $ for all sufficiently large $ k $, and $ \sum b_k $ converges, then $ \sum a_k $ converges. Conversely, if $ \sum a_k $ diverges, so does $ \sum b_k $.

Infinite Series for Algorithm Analysis

In Section 1.2.10, Knuth applies infinite series to analyze the performance of algorithms. A typical application involves bounding the running time of an algorithm by an infinite series that converges to a known value.

For example, when analyzing the expected number of local maxima in a random permutation, Knuth encounters series that can be summed in closed form using the techniques developed in earlier sections.

The key insight is that many algorithm analyses lead to sums of the form:

$ \sum_{k} \dfrac{1}{k}, \quad \sum_{k} \dfrac{1}{k^2}, \quad \sum_{k} \dfrac{k}{2^k}, \quad \sum_{k} \binom{n}{k} \dfrac{1}{2^k} $

all of which can be evaluated using the infinite series techniques described above.

Example Problems

Knuth AOCP Section 1.2.7 Problem 1

Problem 1. (M00 difficulty) What is $ H_0 $?

Solution

By definition:

$ H_n = \sum_{k=1}^{n} \dfrac{1}{k} $

The empty sum is zero, so:

$ H_0 = 0 $

Knuth AOCP Section 1.2.9 Exercise 1

Exercise 1. What is the generating function for $ \langle 2^n + 3^n \rangle = \{ 2, 5, 13, 35, \dots \} $?

Solution

The generating function for $ 2^n $ is:

$ G_{2^n}(z) = \sum_{k \geq 0} 2^k z^k = \dfrac{1}{1 - 2z} $

The generating function for $ 3^n $ is:

$ G_{3^n}(z) = \dfrac{1}{1 - 3z} $

By the addition property of infinite series (and generating functions), the generating function for the sum is the sum of the generating functions:

$ G(z) = \dfrac{1}{1-2z} + \dfrac{1}{1-3z} = \dfrac{2 - 5z}{1 - 5z + 6z^2} $

The coefficient of $ z^n $ in the Taylor expansion of $ G(z) $ is $ 2^n + 3^n $.

Sum of Inverse Squares

The infinite series:

$ \sum_{k=1}^{\infty} \dfrac{1}{k^2} = 1 + \dfrac{1}{4} + \dfrac{1}{9} + \dfrac{1}{16} + \dots = \dfrac{\pi^2}{6} $

This is the Basel problem, solved by Euler. While not covered extensively in Knuth's Volume 1, this series is a classic example of a convergent series related to the harmonic series.

Compare with the harmonic series (divergent):

$ \sum_{k=1}^{\infty} \dfrac{1}{k} \to \infty $

and the series of inverse cubes (convergent, but no simple closed form):

$ \sum_{k=1}^{\infty} \dfrac{1}{k^3} = \zeta(3) \approx 1.2020569\dots $

Related

AOCP/Binomial Coefficients - the binomial theorem and binomial series

AOCP/Fibonacci Numbers - generating function for Fibonacci numbers

AOCP/Generating Functions - formal power series and operations

AOCP/Harmonic Numbers - harmonic series and harmonic numbers

AOCP/Power Series Manipulation - algorithms for manipulating power series (Volume 2)

AOCP/Multinomial Coefficients

Generating Functions - alternate coverage with additional examples

Euler-Mascheroni Constant - the constant $ \gamma $ related to harmonic series