TAOCP 1.2.9 Exercise 21
Let $\langle a_n \rangle = \langle n! \rangle$.
Section 1.2.9: Generating Functions
Exercise 21. [HM30] Set up the generating function for the sequence $\langle n! \rangle$ and study properties of this function.
Verified: yes
Solve time: 1m06s
Setup
Let $\langle a_n \rangle = \langle n! \rangle$. Define its ordinary generating function by
$$ G(z) = \sum_{n \ge 0} n! , z^n. \tag{1} $$
The task is to construct $G(z)$ and analyze its properties using the operations of Section 1.2.9.
Solution
1. Functional equation from shifting
Define the shifted derivative series using (14):
$$ G'(z) = \sum_{n \ge 0} (n+1)(n+1)! z^n. \tag{2} $$
Multiply by $z$ and reindex:
$$ zG'(z) = \sum_{n \ge 0} (n+1)! z^{n+1} = \sum_{n \ge 1} n! z^n = G(z) - 1. \tag{3} $$
The subtraction removes the $n=0$ term $0!z^0 = 1$.
Hence $G(z)$ satisfies the differential equation
$$ zG'(z) - G(z) + 1 = 0. \tag{4} $$
2. Formal solution of the differential equation
Rewrite (4) as
$$ G'(z) - \frac{1}{z}G(z) = -\frac{1}{z}. \tag{5} $$
Multiply by the integrating factor $\frac{1}{z}$:
$$ \frac{1}{z}G'(z) - \frac{1}{z^2}G(z) = -\frac{1}{z^2}. \tag{6} $$
The left-hand side is
$$ \left(\frac{G(z)}{z}\right)'. \tag{7} $$
Thus
$$ \left(\frac{G(z)}{z}\right)' = -\frac{1}{z^2}. \tag{8} $$
Integrating formally in the sense of power series gives
$$ \frac{G(z)}{z} = \frac{1}{z} + C. \tag{9} $$
Multiplying by $z$,
$$ G(z) = 1 + Cz. \tag{10} $$
Comparison with (1) shows that all coefficients of $z^n$ for $n \ge 2$ must vanish in (10), which contradicts $n! \neq 0$ for all $n$. Hence (10) cannot represent a power series about $z=0$ with nonzero radius of convergence.
3. Radius of convergence
By the root test applied to (1),
$$ \lim_{n \to \infty} \sqrt[n]{n!} = \infty. \tag{11} $$
Therefore the radius of convergence $R$ satisfies $R = 0$.
Thus $G(z)$ does not define an analytic function for any $z \ne 0$.
4. Relation to exponential generating function
Define the exponential generating function
$$ \widehat{G}(z) = \sum_{n \ge 0} \frac{n!}{n!} z^n = \sum_{n \ge 0} z^n. \tag{12} $$
Using (5),
$$ \widehat{G}(z) = \frac{1}{1-z}. \tag{13} $$
Hence the sequence $n!$ is recovered from a rational function via
$$ n! = n! \cdot [z^n]\frac{1}{1-z}. \tag{14} $$
5. Integral representation
Using the identity
$$ n! = \int_0^\infty t^n e^{-t} , dt, \tag{15} $$
substitute into (1):
$$ G(z) = \sum_{n \ge 0} z^n \int_0^\infty t^n e^{-t} , dt. \tag{16} $$
Interchange sum and integral formally:
$$ G(z) = \int_0^\infty e^{-t} \sum_{n \ge 0} (zt)^n , dt. \tag{17} $$
The geometric series gives
$$ \sum_{n \ge 0} (zt)^n = \frac{1}{1-zt}, \quad zt \ne 1. \tag{18} $$
Thus
$$ G(z) = \int_0^\infty \frac{e^{-t}}{1-zt} , dt. \tag{19} $$
The integral diverges for every $z \ne 0$, consistent with $R=0$.
Verification
From (3),
$$ zG'(z) = G(z) - 1. $$
Expanding both sides using (1),
$$ z \sum_{n \ge 0} (n+1)(n+1)! z^n = \sum_{n \ge 1} n! z^n, $$
and shifting indices yields equality of coefficients for all $n \ge 1$.
The constant term is excluded on the left, matching the subtraction in $G(z)-1$.
The root test computation (11) implies divergence for every nonzero $z$, since for any $z \ne 0$,
$$ \sqrt[n]{|n! z^n|} = |z| \sqrt[n]{n!} \to \infty. $$
This confirms that (1) is only a formal generating function.
Notes
The ordinary generating function of $n!$ exists only as a formal power series with zero radius of convergence, while the exponential generating function is the convergent rational function $1/(1-z)$ by (13). The differential equation (4) is valid formally but has no analytic solution near $z=0$ other than the trivial series interpretation.