15.1: Infinite Series

Last updated
Save as PDF

Page ID: 48272

Eric Lehman, F. Thomson Leighton, & Alberty R. Meyer
Google and Massachusetts Institute of Technology via MIT OpenCourseWare

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Informally, a generating function, \(F(x)\), is an infinite series

\[\label{15.1.1} F(x) = f_0 + f_1x + f_2x^2 + f_3x^3 + \cdots.\]

We use the notation \([x^n]F(x)\) for the coefficient of xn in the generating function \(F(x)\). That is, \([x^n]F(x) ::= f_n\).

We can analyze the behavior of any sequence of numbers \(f_0, f_1, \ldots f_n \ldots\) by regarding the elements of the sequence as successive coefficients of a generating function. It turns out that properties of complicated sequences that arise from counting, recursive definition, and programming problems are easy to explain by treating them as generating functions.

Generating functions can produce noteworthy insights even when the sequence of coefficients is trivial. For example, let \(G(x)\) be the generating function for the infinite sequence of ones \(1, 1, \ldots\), namely, the geometric series.

\[\label{15.1.2} G(x) ::= 1 + x + x^2 + \cdots + x^n + \cdots.\]

We’ll use typical generating function reasoning to derive a simple formula for \(G(x)\). The approach is actually an easy version of the perturbation method of Section 13.1.2. Specifically,

\[\begin{aligned}
G(x) &=1+x+x^{2}+x^{3}+\cdots+x^{n}+\cdots \\
-x G(x) &=\quad -x-x^{2}-x^{3}-\cdots-x^{n}-\cdots \\
\hline G(x)-x G(x) &=1.
\end{aligned}\]

Solving for \(G(x)\) gives

\[\label{15.1.3} \dfrac{1}{1-x} = G(x) ::= \sum_{n=0}^{\infty} x^n.\]

In other words,

\[\nonumber [x^n]\left(\dfrac{1}{1-x}\right) = 1\]

Continuing with this approach yields a nice formula for

\[\label{15.1.4} N(x) ::= 1 + 2x + 3x^2 + \cdots + (n+1)x^n + \cdots.\]

Specifically,

\[\begin{aligned}
N(x) &=1+2x+3x^{2}+4x^{3}+\cdots+(n+1)x^{n}+\cdots \\
-x N(x) &=\quad -x-2x^{2}-3x^{3}-\cdots-nx^{n}-\cdots \\
\hline N(x)-x N(x) &=1 + x + x^2 + x^3 + \cdots + x^n + \cdots \\ &= G(x).
\end{aligned}\]

Solving for \(N(x)\) gives

\[\label{15.1.5} \dfrac{1}{(1-x)^2} = \dfrac{G(x)}{1-x} = N(x) ::= \sum_{n=0}^{\infty} (n+1)x^n.\]

On other words,

\[\nonumber [x^n]\left(\dfrac{1}{(1-x)^2}\right) = n + 1.\]

Never Mind Convergence

Equations (\ref{15.1.3}) and (\ref{15.1.5}) hold numerically only when \(|x|< 1\), because both generating function series diverge when \(|x| \geq 1\). But in the context of generating functions, we regard infinite series as formal algebraic objects. Equations such as (\ref{15.1.3}) and (\ref{15.1.5}) define symbolic identities that hold for purely algebraic reasons. In fact, good use can be made of generating functions determined by infinite series that don’t converge anywhere (besides \(x = 0\)). We’ll explain this further in Section 15.5 at the end of this chapter, but for now, take it on faith that you don’t need to worry about convergence.