Admin: Create AOCP/Infinite Series page covering infinite series topics from Knuth's Volume 1 (via create-page on MediaWiki MCP Server)

2026-06-20T04:55:51Z

Create AOCP/Infinite Series page covering infinite series topics from Knuth's Volume 1 (via create-page on MediaWiki MCP Server)

New page

=Knuth Volume 1: Fundamental Algorithms=

==Chapter 1: Basic Concepts: Infinite Series==

===Definitions===

An infinite series is a sum of infinitely many terms:

<math>
\sum_{k=0}^{\infty} a_k = a_0 + a_1 + a_2 + \dots
</math>

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

<math>
S_n = \sum_{k=0}^{n} a_k
</math>

If <math>\lim_{n \to \infty} S_n = S</math> exists and is finite, the series converges to <math>S</math>. 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 <math>\sum a_k</math> is '''absolutely convergent''' if <math>\sum |a_k|</math> 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:

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

This is derived by considering the partial sum:

<math>
S_n = \sum_{k=0}^{n} x^k
</math>

Multiplying by <math>(1-x)</math> yields the telescoping sum:

<math>
(1-x) S_n = (1 + x + x^2 + \dots + x^n) - (x + x^2 + \dots + x^{n+1}) = 1 - x^{n+1}
</math>

Thus:

<math>
S_n = \dfrac{1 - x^{n+1}}{1 - x}
</math>

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

<math>
\sum_{k=0}^{\infty} x^k = \dfrac{1}{1-x}
</math>

A closely related form generalizes this:

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

and more generally:

<math>
\sum_{k=0}^{\infty} (a x^k) = \dfrac{a}{1 - x}
</math>

and:

<math>
\sum_{k=0}^{\infty} x^{k} (a) = a \dfrac{1}{1-x}
</math>

For the shifted series:

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

===The Finite Geometric Sum===

Before taking limits, the finite geometric sum is:

<math>
\sum_{k=0}^{n} x^k = \dfrac{1 - x^{n+1}}{1 - x} \qquad x \neq 1
</math>

When <math>x = 1</math>, each term contributes 1, so:

<math>
\sum_{k=0}^{n} 1 = n + 1
</math>

===The Harmonic Series===

The harmonic series is defined as:

<math>
H_{\infty} = \sum_{k=1}^{\infty} \dfrac{1}{k} = 1 + \dfrac{1}{2} + \dfrac{1}{3} + \dfrac{1}{4} + \dots
</math>

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

<math>
H_n = \sum_{k=1}^{n} \dfrac{1}{k}
</math>

Knuth proves divergence by showing:

<math>
H_{2^m} \geq 1 + \dfrac{m}{2}
</math>

which grows without bound as <math>m \to \infty</math>.

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

===The Exponential Series===

The exponential series defines the constant <math>e</math>:

<math>
e^z = \sum_{k=0}^{\infty} \dfrac{z^k}{k!} = 1 + z + \dfrac{z^2}{2!} + \dfrac{z^3}{3!} + \dots
</math>

This series converges for all real and complex <math>z</math>. In particular:

<math>
e = \sum_{k=0}^{\infty} \dfrac{1}{k!} = 1 + 1 + \dfrac{1}{2} + \dfrac{1}{6} + \dfrac{1}{24} + \dots
</math>

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

===The Logarithm Series===

Knuth gives two important logarithm series:

<math>
\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
</math>

<math>
\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
</math>

Note the connection to harmonic numbers: the coefficients of the second series are <math>\frac{1}{k}</math>, 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:

<math>
(1 + z)^r = \sum_{k=0}^{\infty} \binom{r}{k} z^k
</math>

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

When <math>r</math> is a negative integer, we obtain an important special case:

<math>
\dfrac{1}{(1-z)^{n+1}} = \sum_{k=0}^{\infty} \binom{n+k}{n} z^k
</math>

For example, when <math>n = 0</math>:

<math>
\dfrac{1}{1-z} = \sum_{k=0}^{\infty} z^k
</math>

which is the geometric series.

===Differentiation and Integration of Series===

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

<math>
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
</math>

and integrate:

<math>
\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
</math>

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

<math>
\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
</math>

Integrating the geometric series gives:

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

===Telescoping Series===

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

<math>
\sum_{k=0}^{n} (b_{k+1} - b_k) = b_{n+1} - b_0
</math>

For an infinite telescoping series, if <math>\lim_{n \to \infty} b_n = L</math>, then:

<math>
\sum_{k=0}^{\infty} (b_{k+1} - b_k) = L - b_0
</math>

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

<math>
\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}
</math>

Taking the limit as <math>n \to \infty</math>:

<math>
\sum_{k=1}^{\infty} \dfrac{1}{k(k+1)} = 1
</math>

===Alternating Series===

An alternating series has terms that alternate in sign:

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

The alternating harmonic series converges (conditionally):

<math>
\sum_{k=1}^{\infty} \dfrac{(-1)^{k+1}}{k} = 1 - \dfrac{1}{2} + \dfrac{1}{3} - \dfrac{1}{4} + \dots = \ln 2
</math>

Knuth uses alternating series in several identities, such as:

<math>
\sum_{k} \binom{n}{k} (-1)^k = (1-1)^n = 0^n
</math>

which equals <math>1</math> when <math>n = 0</math> and <math>0</math> when <math>n > 0</math>.

===Infinite Series in Generating Functions===

A generating function <math>G(z)</math> for a sequence <math>\langle a_n \rangle</math> is the infinite series:

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

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 <math>G(z) = \sum_{k \geq 0} a_k z^k</math> is the generating function for <math>\langle a_n \rangle</math>, then the generating function for the partial sums is:

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

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

===Convergence Tests===

Knuth mentions several tests for convergence, including:

'''Ratio Test:''' For a series <math>\sum a_k</math> with positive terms, if:

<math>
\lim_{k \to \infty} \left| \dfrac{a_{k+1}}{a_k} \right| = L
</math>

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

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

===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:

<math>
\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}
</math>

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 <math>H_0</math>?

===Solution===

By definition:

<math>
H_n = \sum_{k=1}^{n} \dfrac{1}{k}
</math>

The empty sum is zero, so:

<math>
H_0 = 0
</math>

==Knuth AOCP Section 1.2.9 Exercise 1==

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

===Solution===

The generating function for <math>2^n</math> is:

<math>
G_{2^n}(z) = \sum_{k \geq 0} 2^k z^k = \dfrac{1}{1 - 2z}
</math>

The generating function for <math>3^n</math> is:

<math>
G_{3^n}(z) = \dfrac{1}{1 - 3z}
</math>

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

<math>
G(z) = \dfrac{1}{1-2z} + \dfrac{1}{1-3z} = \dfrac{2 - 5z}{1 - 5z + 6z^2}
</math>

The coefficient of <math>z^n</math> in the Taylor expansion of <math>G(z)</math> is <math>2^n + 3^n</math>.

==Sum of Inverse Squares==

The infinite series:

<math>
\sum_{k=1}^{\infty} \dfrac{1}{k^2} = 1 + \dfrac{1}{4} + \dfrac{1}{9} + \dfrac{1}{16} + \dots = \dfrac{\pi^2}{6}
</math>

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):

<math>
\sum_{k=1}^{\infty} \dfrac{1}{k} \to \infty
</math>

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

<math>
\sum_{k=1}^{\infty} \dfrac{1}{k^3} = \zeta(3) \approx 1.2020569\dots
</math>

=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 <math>\gamma</math> related to harmonic series

=Flags=

{{AOCPFlag}}
{{AlgorithmsFlag}}

[[Category:AOCP]]
[[Category:Algorithms]]
[[Category:Combinatorics]]
[[Category:Series]]

AOCP/Infinite Series - Revision history

Admin: Create AOCP/Infinite Series page covering infinite series topics from Knuth's Volume 1 (via create-page on MediaWiki MCP Server)