Manuel Kauers Hagenberg, November 16, 2003 RISC-Linz

Analytic Combinatorics

Homework 6

Exercise 18 Prove

\frac{1}{(1 − x)^{m}} = ∑_{k=0}^{∞} \binom{m + k − 1}{k}x^{k} (x ≠ 1, m ∈ ℤ)

We will present two inductions. The first induction provides the proof for m ≥ 0, the second for m ≤ 0. They share the same induction base m = 0:

1 = \frac{1}{(1 − x)^{0}} = ∑_{k=0}^{∞} \binom{k − 1}{k}x^{k}.

The binomial coefficient \binom{k−1}{k} vanishes for all k except for k = 0 where it evaluates to 1. This completes the induction base. Now suppose the claim is true for some m ∈ ℤ and prove it for m + 1.

\frac{1}{(1 − x)^{m+1}} = \frac{1}{(1 − x)^{m}} \frac{1}{1 − x} = ∑_{k=0}^{∞} \binom{m + k − 1}{k}x^{k} ∑_{k=0}^{∞} x^{k}

= ∑_{k=0}^{∞} ∑_{i=0}^{k} \binom{m + i − 1}{i}x^{i}x^{k−i} = ∑_{k=0}^{∞} ( ∑_{i=0}^{k} \binom{m + i − 1}{i})x^{k}

It remains to show the identity

∑_{i=0}^{k} \binom{m + i − 1}{i} = \binom{m + k}{k}

which can be done, e.g., by induction on k. The case k = 0 is evident. As for the induction step, we have

∑_{i=0}^{k+1} \binom{m + i − 1}{i} = ∑_{i=0}^{k} \binom{m + i − 1}{i} + \binom{m + k}{k + 1} = \binom{m + k}{k} + \binom{m + k}{k + 1}

= \binom{m + k + 1}{k + 1}.

This completes the induction “to the right.” Now suppose the claim is true for some m ∈ ℤ and prove it for m − 1.

\frac{1}{(1 − x)^{m−1}} = \frac{1}{(1 − x)^{m}} (1 − x) = ∑_{k=0}^{∞} \binom{m + k − 1}{k}x^{k}(1 − x)

= ∑_{k=0}^{∞} \binom{m + k − 1}{k}x^{k} − ∑_{k=0}^{∞} \binom{m + k − 1}{k}x^{k+1}

= 1 + ∑_{k=1}^{∞} \binom{m + k − 1}{k}x^{k} − ∑_{k=1}^{∞} \binom{m + k − 2}{k − 1}x^{k}

= 1 + ∑_{k=1}^{∞} (\binom{m + k − 1}{k} − \binom{m + k − 2}{k − 1})x^{k}

=^{(∗)} 1 + ∑_{k=1}^{∞} ((−1)^{k}\binom{−m}{k} + (−1)^{k}\binom{−m}{k − 1})x^{k}

= 1 + ∑_{k=1}^{∞}(−1)^{k}\binom{−m + 1}{k}x^{k} = ∑_{k=0}^{∞}(−1)^{k}\binom{−m + 1}{k}x^{k}

=^{(∗)} ∑_{k=0}^{∞} \binom{k + m − 2}{k}x^{k}.

In (∗) we make use of the reflection formula to be proven in the next exercise. (The proof given there won’t make use of the results presented here.) The induction “to the left” is complete, and hence we are done. Remark: The induction steps did not make use of the fact m ∈ ℤ, so if we manage to prove the queried identity for some m = q ∈ ℚ, then it will hold for all m ∈ q+ℤ. For example, a Taylor expansion of 1/\sqrt{1 − x} provides the induction base

\frac{1}{(1 − x)^{1/2}} = ∑_{k=0}^{∞} \binom{k − 1/2}{k}x^{k},

and hence the original formula holds for all m ∈ \frac{1}{2}ℤ.

Exercise 19 Prove the reflection formula for binomial coefficients

\binom{α}{k} = (−1)^{k}\binom{k − α − 1}{k}

where α ∈ ℂ and k ∈ ℕ_{0}.

For k < 0 or k > α both sides evaluate to zero and there is nothing to prove. Otherwise, the right hand side does not vanish and we may divide the conjecture through it. Plugging in the definition of the binomial coefficient gives

\begin{matrix}( & {α \atop k} & ) \\ ( & {k−α−1 \atop k} & ) \end{matrix} = \frac{α(α − 1) … (α − k + 1)/k!}{(k − α − 1)(k − α − 2) … (k − α − 1 − k + 1)/k!}

= \frac{α(α − 1) … (α − k + 1)}{(−α) … (−(α − k + 2)(−(α − k + 1))} = (−1)^{k}

as we wished to prove.

Exercise 20 Consider the sequence {f_{n}}_{n=0}^{∞} defined by

f_{n} = ∑_{k=0}^{n} \binom{m + k − 1}{k}\binom{m}{n − k}(−1)^{n−k}

where m is an arbitrary but fixed complex number. Prove that f_{0} = 1 and f_{n} = 0 for n ≠ 0.

First note that for all α ∈ ℂ and n ∈ ℕ we have

\frac{∂^{n}}{∂^{n}x} \frac{1}{(1 − x)^{α}} = α\overline{n} \frac{1}{(1 − x)^{α+n}} ,

in particular,

\frac{∂^{n}}{∂^{n}x} \frac{1}{(1 − x)^{α}} |_{x=0} = α\overline{n},

and by Taylor’s theorem

\frac{1}{(1 − x)^{α}} = ∑_{n=0}^{∞} \frac{α\overline{n}}{n!} x^{n} = ∑_{n=0}^{∞} \binom{α + n − 1}{n}x^{n}.  (1)

Now consider the generating function f(x) of f_{n}.

f(x) = ∑_{n=0}^{∞} f_{n}x^{n} = ∑_{n=0}^{∞} ( ∑_{k=0}^{n} \binom{m + k − 1}{k}\binom{m}{n − k}(−1)^{n−k})x^{n}

= ∑_{n=0}^{∞} ( ∑_{k=0}^{n} \binom{m + k − 1}{k}\binom{−m + (n − k) − 1}{n − k})x^{n}

= ∑_{n=0}^{∞} \binom{m + n − 1}{n}x^{n} ∑_{n=0}^{∞} \binom{−m + n − 1}{n}x^{n}

=^{(1)} \frac{1}{(1 − x)^{m}} \frac{1}{(1 − x)^{−m}} = 1.

The claim follows by comparing coefficients. Remark: Given the definition of f, Maple returns 0 ignoring the special case n = 0. Carsten’s Sigma simplifies the sum to

−(−1)^{n}(−1 + (−1)^{2n})\binom{m}{n}

which is clearly 0 for all n ∈ ℤ. It also ignores the special case.

Exercise 21 Study recurrences and generating functions of the Stirling numbers of the second kind, S(n, k).

S(n, k) is by definition the number of partitions of a set of n elements into k disjoint nonempty subset. For a recurrence of S(n, k), consider a systematic way to enumerate all those partitions. Given {1, …, n} we may first compute the partitions of {1, …, n−1} into k subsets and add {n} to one of those. There are S(n−1, k) partitions of {1, …, n − 1} and k possible extensions to partitions of {1, …, n}. There are further partitions where {n} is a singleton. These are not included yet because empty subsets are not permitted. There are S(n−1, k −1) partitions S_{1} ∪⋯∪S_{k−1} of {1, …, n − 1} and they extend to as many partitions S_{1} ∪ ⋯ ∪ S_{k−1} ∪ {n} of {1, …, n}. We have found the recurrence

S(n, k) = kS(n − 1, k) + S(n − 1, k − 1) (n ≥ 1, k ≥ 1)

The initial values are S(n, 0) = 0 (n ≠ 0), S(0, k) = 0 (k ≠ 0) and S(0, 0) = 1. We extend the definition of S by putting S(n, k) := 0 (n < 0 or k < 0). The recurrence then holds for all (n, k) ∈ ℤ × ℤ except for (n, k) = (0, 0). We can now study the generating functions of S.

First consider the bivariate generating function F (x, y).

F (x, y) = ∑_{(n,k)} S(n, k)x^{n}y^{k} = 1 + ∑_{(n,k)≠(0,0)} kS(n − 1, k)x^{n}y^{k} + ∑_{(n,k)≠(0,0)} S(n − 1, k − 1)x^{n}y^{k}

= 1 + ∑_{(n,k)} kS(n − 1, k)x^{n}y^{k} + ∑_{(n,k)} S(n − 1, k − 1)x^{n}y^{k}

= 1 + xy \frac{∂}{∂y} ∑_{(n,k)} S(n, k)x^{n}y^{k} + xy ∑_{(n,k)} x^{n}y^{k}

= 1 + xy \frac{∂}{∂y} F (x, y) + xyF (x, y).

As a solution for this system, Maple outputs a complicated expression involving the incomplete Gamma function which we do not want to reproduce here. However, there is a nice form of the “semi exponential” bivariate generating function F̃(x, y) which is exponential wrt. n and ordinary wrt. k. Making use of the results of Exercise 23 below we get

F̃(x, y) = ∑_{(n,k)} \frac{S(n, k)}{n!}x^{n}y^{k} = ∑_{k=0}^{∞} ( ∑_{n=0}^{∞} \frac{S(n, k)}{n!}x^{n})y^{k}

= ∑_{k=0}^{∞} \frac{(e^{x} − 1)^{k}}{k!} y^{k} = exp(y(e^{x} − 1)).

Now keep n discrete and consider the generating function G_{n}(y). For n > 0 we have

G_{n}(y) = ∑_{k=0}^{∞} S(n, k)y^{k} = ∑_{k=0}^{∞} kS(n − 1, k)y^{k} + ∑_{k=0}^{∞} S(n − 1, k − 1)y^{k}

= y \frac{∂}{∂y} ∑_{k=0}^{∞} S(n − 1, k)y^{k} + y ∑_{k=1}^{∞} S(n − 1, k − 1)y^{k−1}

= y \frac{∂}{∂y} G_{n−1}(y) + yG_{n−1}(y)

Is there a closed form for G_{n}? We note that G_{n} is holonomic, the defining annihilating operator is S_{n} − yD_{y} − y. Together with G_{0}(y) = 1 the G_{n}(y) can be consecutively computed for all n > 0, so the system has a unique solution. We do, however, not know if this solution admits a closed form. (Exercise 23 below will consider the exponential sister of G_{n}(x)) Now keep k discrete and consider the generating function H_{k}(x). For k > 0 we have

H_{k}(x) = ∑_{n=0}^{∞} S(n, k)x^{n} = ∑_{n=0}^{∞} kS(n − 1, k)x^{n} + ∑_{n=0}^{∞} S(n − 1, k − 1)x^{n}

= kx ∑_{n=0}^{∞} S(n, k)x^{n} + x ∑_{n=0}^{∞} S(n, k − 1)x^{n} = kxH_{k}(x) + xH_{k−1}(x),

Therefore

H_{k}(x) = \frac{x}{1 − kx}H_{k−1}(x) = \frac{x}{1 − kx} \frac{x}{1 − (k − 1)x}H_{k−2}(x) = ⋯

= H_{0}(x) ∏_{i=1}^{k} \frac{1}{\frac{1}{x} − i} = \frac{1}{(\frac{1}{x})\underline{k}} .

Note that H_{0}(x) = ∑_{n=0}^{∞} S(n, 0)x^{n} = 1. Is there a closed form for S(n, k)? We once more make use of the result of Exercise 23. We have

S(n, k) = n!⟨x^{n}⟩\frac{(e^{x} − 1)^{k}}{k!} = \frac{1}{k!} \frac{∂^{n}}{∂^{n}x}(e^{x} − 1)^{k}|_{x=0}
\frac{∂^{n}}{∂^{n}x}(e^{x} − 1)^{k} = \frac{∂^{n}}{∂^{n}x} ∑_{i=0}^{k} \binom{k}{i}e^{ix}(−1)^{k−i} = ∑_{i=0}^{k} \binom{k}{i}i^{n}e^{ix}(−1)^{k−i}

and therefore

S(n, k) = \frac{1}{k!} ∑_{i=0}^{k} \binom{k}{i}i^{n}(−1)^{k−i}.

This may or may not be considered a closed form.

Exercise 22 Find closed form expressions for the following sequences and their ordinary and exponential generating functions.

a) a_{n+1} = 3a_{n} + 2 (n ≥ 0), a_{0} = 0

b) a_{n+2} = 2a_{n+1} − a_{n} (n ≥ 0), a_{0} = 0, a_{1} = 1

c) a_{n+1} = \frac{1}{3}a_{n} + 1 (n ≥ 0), a_{0} = 0

Find closed form representations for the exponential generating function of the following sequences.

d) a_{n+1} = (n + 1)a_{n} − \binom{n}{2}a_{n−2} (n ≥ 0), a_{0} = 1

e) 2a_{n+1} = ∑_{k=0}^{n} \binom{n}{k}a_{k}a_{n−k} (n ≥ 1), a_{0} = a_{1} = 1

f) 2a_{n+1} = ∑_{k=0}^{n} \binom{n}{k}a_{k}a_{n−k} (n ≥ 0), a_{0} = 1.

Ad a) The closed form for a_{n} itself is easily obtained as a_{n} = 3^{n} − 1 as described in detail in previous exercises on similar examples. This closed form admits immediately closed forms for the generating functions:

a(x) = ∑_{n=0}^{∞} a_{n}x^{n} = ∑_{n=0}^{∞}(3^{n} − 1)x^{n} = ∑_{n=0}^{∞}(3x)^{n} − ∑_{n=0}^{∞} x^{n}

= \frac{1}{1 − 3x} + \frac{1}{1 − x} = \frac{2x}{(3x − 1)(x − 1)}

ā(x) = ∑_{n=0}^{∞} \frac{a_{n}}{n!} x^{n} = ∑_{n=0}^{∞} \frac{3^{n} − 1}{n!}x^{n} = ∑_{n=0}^{∞} \frac{1}{n!}(3x)^{n} − ∑_{n=0}^{∞} \frac{1}{n!}x^{n} = e^{3x} − e^{x}.

Ad b) Again the defining recurrence is C-finite, so we obtain a_{n} = n effordlessly. As for the generating functions, we have

a(x) = ∑_{n=0}^{∞} a_{n}x^{n} = ∑_{n=0}^{∞} nx^{n} = ∑_{n=1}^{∞} nx^{n} = x ∑_{n=1}^{∞} nx^{n−1}

∑_{n=1}^{∞} nx^{n−1} = \frac{∂}{∂x} ∑_{n=1}^{∞} x^{n} = \frac{∂}{∂x}(\frac{1}{x − 1} − 1) = \frac{1}{(x − 1)^{2}}
⟹  a(x) = \frac{x}{(x − 1)^{2}}

and

ā(x) = ∑_{n=0}^{∞} \frac{a_{n}}{n!} x^{n} = ∑_{n=0}^{∞} \frac{n}{n!}x^{n} = ∑_{n=1}^{∞} \frac{n}{n!}x^{n} = x ∑_{n=1}^{∞} \frac{1}{(n − 1)!}x^{n−1}

= x ∑_{n=0}^{∞} \frac{1}{n!}x^{n} = xe^{x}.

Ad c) The closed form for a_{n} is again for free: a_{n} = \frac{3}{2}(1 − (1/3)^{n}). What are the generating functions?

a(x) = ∑_{n=0}^{∞} a_{n}x^{n} = \frac{3}{2} ∑_{n=0}^{∞} (1 − 3^{−n})x^{n} = \frac{3}{2}( ∑_{n=0}^{∞} x^{n} − ∑_{n=0}^{∞}(x/3)^{n})

= \frac{3}{2}(\frac{1}{x − 1} + \frac{3}{3 − x}) = \frac{3x}{(x − 1)(x − 3)},

ā(x) = ∑_{n=0}^{∞} \frac{a_{n}}{n!} x^{n} = \frac{3}{2}( ∑_{n=0}^{∞} \frac{1}{n!}x^{n} − ∑_{n=0}^{∞} \frac{1}{n!}(x/3)^{n}) = \frac{3}{2}(e^{x} − e^{x/3})

Remark: All generating functions in a), b), and c) can be obtained as well be the standard method without using the closed form of a_{n}, but the required “manipulatorics” is much more involved.

Ad d) Starting from the recurrence of a_{n}, we get

a_{n+1} = (n + 1)a_{n} − \frac{1}{2}n(n − 1)a_{n−2}
\frac{a_{n+1}}{n!} = (n + 1)\frac{a_{n}}{n!} − \frac{1}{2}n(n − 1)\frac{a_{n−2}}{n!}
∑_{n=0}^{∞} \frac{a_{n+1}}{n!} x^{n} = ∑_{n=0}^{∞} \frac{a_{n}}{n!} x^{n} − \frac{1}{2} ∑_{n=0}^{∞} n(n − 1)\frac{a_{n−2}}{n!} x^{n}.

We observe

∑_{n=0}^{∞} \frac{a_{n+1}}{n!} x^{n} = ∑_{n=1}^{∞} \frac{a_{n}}{(n − 1)!}x^{n−1} = ∑_{n=0}^{∞} \frac{a_{n}}{n!} nx^{n−1} = \frac{∂}{∂x} ∑_{n=0}^{∞} \frac{a_{n}}{n!} x^{n} = ā′(x)

∑_{n=0}^{∞} \frac{a_{n}}{n!} (n + 1)x^{n} = \frac{∂}{∂x} ∑_{n=0}^{∞} \frac{a_{n}}{n!} x^{n+1} = \frac{∂}{∂x}(xā(x)) = ā(x) + xā′(x)

∑_{n=0}^{∞} n(n − 1)\frac{a_{n−2}}{n!} x^{n} = ∑_{n=2}^{∞} n(n − 1)\frac{a_{n−2}}{n!} x^{n} = x^{2} ∑_{n=2}^{∞} \frac{a_{n−2}}{(n − 2)!}x^{n−2}

= x^{2} ∑_{n=0}^{∞} \frac{a_{n}}{n!} x^{n} = x^{2}ā(x).

This yields a differential equation for ā(x)

ā′(x) = ā(x) + xā′(x) − \frac{1}{2}x^{2}ā(x)
(1 − x)ā′(x) = (1 − \frac{1}{2}x^{2})ā(x).

According to Maple, a generic solution of this equation is

ā(x) = α\frac{exp(\frac{1}{4}x^{2} + \frac{1}{2}x)}{\sqrt{x − 1}}.

By ā(0) = −iα =^{!} 1 = a_{0} we obtain α = i and therefore

ā(x) = \frac{exp(\frac{1}{4}x^{2} + \frac{1}{2}x)}{\sqrt{1 − x}}.

Ad e) We first note that

∑_{k=0}^{n} \binom{n}{k}a_{k}a_{n−k} = n! ∑_{k=0}^{n} \frac{a_{k}}{k!} \frac{a_{n−k}}{(n − k)!}.

Let ã(x) be the exponential generating function of a_{n}. Then

ã(x) = ∑_{n=0}^{∞} \frac{a_{n}}{n!} x^{n} = 1 + x + ∑_{n=2}^{∞} \frac{a_{n}}{n!} x^{n}.  (2)

Consider the last sum.

∑_{n=2}^{∞} \frac{a_{n}}{n!} x^{n} = \frac{1}{2} ∑_{n=1}^{∞} \frac{a_{n+1}}{(n + 1)!}x^{n+1} = \frac{1}{2} ∑_{n=1}^{∞} \frac{1}{n + 1} ∑_{k=0}^{n} \frac{a_{k}}{k!} \frac{a_{n−k}}{(n − k)!}x^{n+1}

= \frac{1}{2} ∫ ∑_{n=1}^{∞} ∑_{k=0}^{n} \frac{a_{k}}{k!} \frac{a_{n−k}}{(n − k)!}x^{n} dx = \frac{1}{2} ∫ (( ∑_{n=0}^{∞} a_{n}x^{n})^{2} − a_{0}^{2}) dx

= \frac{1}{2} ∫ (ã(x) − 1) dx.

Plugging this representation into (2) and differentiating on both sides gives

\frac{∂}{∂x}ã(x) = 1 + \frac{1}{2}(ã(x)^{2} − 1) = \frac{1}{2} ã(x) + \frac{1}{2}.

The solution of this equation is ã(x) = tan \frac{x+α}{2} for some α. By ã(0) = a_{0} = 1 we obtain α = π/2 and finally

ã(x) = tan \frac{2x + π}{4}

for the required generating function.

Ad f) We first note that

∑_{k=0}^{n} \binom{n}{k}a_{k}a_{n−k} = n! ∑_{k=0}^{n} \frac{a_{k}}{k!} \frac{a_{n−k}}{(n − k)!}.

Using this we obtain from the recurrence

2a_{n+1} = ∑_{k=0}^{n} \binom{n}{k}a_{k}a_{n−k}

2\frac{a_{n+1}}{n!} = ∑_{k=0}^{n} \frac{a_{k}}{k!} \frac{a_{n−k}}{(n − k)!}

2 ∑_{n=0}^{∞} \frac{a_{n+1}}{n!} x^{n} = ∑_{n=0}^{∞} ( ∑_{k=0}^{n} \frac{a_{k}}{k!} \frac{a_{n−k}}{(n − k)!})x^{n}

2ā′(x) = ( ∑_{n=0}^{∞} a_{n}x^{n})^{2} = ā(x)^{2}

It follows that ā(x) = 2/(α − x) for some α. ā(0) = 2/α =^{!} 1 = a_{0} gives α = 2 and hence the generating function is

ā(x) = \frac{2}{2 − x}.

Exercise 23 Compute a closed form representation for

f_{k}(x) := ∑_{n=k}^{∞} \frac{S(n, k)}{n!}x^{n}

For k > 0 we have

f_{k}(x) = ∑_{n=k}^{∞} \frac{S(n, k)}{n!}x^{n} = k ∑_{n=k}^{∞} \frac{S(n − 1, k)}{n!}x^{n} + ∑_{n=k}^{∞} \frac{S(n − 1, k − 1)}{n!}x^{n}. (3)

We observe the following relations.

∑_{n=k}^{∞} \frac{S(n − 1, k − 1)}{n!}x^{n} = ∫ ∑_{n=k}^{∞} \frac{S(n − 1, k − 1)}{(n − 1)!}x^{n−1} dx

= ∫ ∑_{n=k−1}^{∞} \frac{S(n, k − 1)}{n!}x^{n} dx = ∫ f_{k−1}(x) dx

∑_{n=k}^{∞} \frac{S(n − 1, k)}{n!}x^{n} = ∫ ∑_{n=k}^{∞} \frac{S(n − 1, k)}{(n − 1)!}x^{n−1} dx = ∫ ∑_{n=k−1}^{∞} \frac{S(n, k)}{n!}x^{n} dx

= ∫ ( ∑_{n=k}^{∞} \frac{S(n, k)}{n!}x^{n} + \underbrace{\frac{S(k − 1, k)}{(k − 1)!}x^{k−1}}_{=0} ) dx

= ∫ f_{k}(x) dx

Plugging them into (3) and differentiating both sides gives

f_{k}(x) = k ∫ f_{k}(x) dx + ∫ f_{k−1}(x) dx
\frac{∂}{∂x}f_{k}(x) = kf_{k}(x) + f_{k−1}(x).

We regard the latter as inhomogenous differential equation in f_{k}. The corresponding homogenous equation has the solution h_{k}(x) = c_{k}e^{kx}. Variation of the constant, f_{k}(x) := c_{k}(x)e^{kx}, leads to

\frac{∂}{∂x}c_{k}(x)e^{kx} − kc_{k}(x)e^{kx} = c_{k−1}e^{(k−1)x}
c′_{k}(x)e^{kx} + c_{k}(x)ke^{kx} − kc_{k}(x)e^{kx} = c_{k−1}e^{(k−1)x}
c′_{k}(x) = c_{k−1}(x)e^{−x}
c_{k}(x) = ∫_{0}^{x} c_{k−1}(t)e^{−t} dt  (4)

where the last step takes into accout that f_{k}(0) = c_{k}(0)e^{0} = 0 for k > 0.

Now consider k = 0, 1, 2, . . .. For k = 0 we have f_{0}(x) = c_{0}(x)e^{0x} = 1, so c_{0}(x) = 1. The further f_{k}(x) can be obtained by means of (4):

c_{1}(x) = ∫_{0}^{x} c_{0}(t)e^{−t} dt = 1 − e^{−x}  ⟹ f_{1}(x) = e^{x} − 1,
c_{2}(x) = ∫_{0}^{x} c_{1}(t)e^{−t} dt = \frac{1}{2}(1 − e^{−x})^{2} ⟹ f_{2}(x) = \frac{1}{2}(e^{x} − 1)^{2},
c_{3}(x) = ∫_{0}^{x} c_{2}(t)e^{−t} dt = \frac{1}{6}(1 − e^{−x})^{3} ⟹ f_{3}(x) = \frac{1}{6}(e^{x} − 1)^{3},
c_{4}(x) = ∫_{0}^{x} c_{3}(t)e^{−t} dt = \frac{1}{24}(1 − e^{−x})^{4} ⟹ f_{4}(x) = \frac{1}{24}(e^{x} − 1)^{4}, …

This leads to the conjecture

c_{k}(x) = \frac{(1 − e^{−x})^{k}}{k!} ,  i.e., f_{k}(x) = \frac{(e^{x} − 1)^{k}}{k!}

which we will now prove by induction. We have seen enough base cases above. Assume now c_{k}(x) is of the desired form. Then

c_{k+1}(x) = ∫_{0}^{x} c_{k}(t)e^{−t} dt = \frac{1}{k!} ∫_{0}^{x}(1 − e^{−t})^{k}e^{−t} dt = \frac{1}{k!} ∫_{−1}^{−e^{−x}}(1 + u)^{k} du

= \frac{1}{k!}[\frac{1}{k + 1}(1 + u)^{k+1}]_{u=−1}^{−e^{−x}} = \frac{1}{(k + 1)!}((1 − e^{−x})^{k+1} − 0)

= \frac{(1 − e^{−x})^{k+1}}{(k + 1)!} .

Exercise 24 Compute a closed form representation for the exponential generating function of the bell numbers B(n) defined by

B(n) = ∑_{k=0}^{n} S(n, k) (n ≥ 0)

We will use that S(n, k) = 0 if k > n:

∑_{n=0}^{∞} \frac{B(n)}{n!}x^{n} = ∑_{n=0}^{∞} \frac{1}{n!} ∑_{k=0}^{n} S(n, k)x^{n} = ∑_{n=0}^{∞} ∑_{k=0}^{∞} \frac{S(n, k)}{n!}x^{n} = ∑_{k=0}^{∞} ∑_{n=0}^{∞} \frac{S(n, k)}{n!}x^{n}

=^{(∗)} ∑_{k=0}^{∞} \frac{(e^{x} − 1)^{k}}{k!} = exp(e^{x} − 1),

where (∗) is justified by the previous exercise.

Exercise 25 Let c(n, k) be the number of permutations π ∈ S_{n} with exactly k cycles. Give a combinatorial argument for the recurrence

c(n, k) = (n − 1)c(n − 1, k) + c(n − 1, k − 1) (n, k ≥ 1)

In order to enumerate all permutations π of {1, …, n}, we proceed recursively. The first bunch of permutations leaves n fixed. Then (n) is one cycle of its own, and there are k − 1 further cycles left for permuting the remaining n − 1 elements. These gives c(n − 1, k − 1) permutations.

Next we consider a permutation π of {1, …, n−1} with k cycles. There are c(n−1, k) permutations of this type. Let

π = (p_{1} p_{2} … p_{c_{1}})(p_{c_{1}+1} … p_{c_{2}}) . . . . . . (p_{c_{k−1}+1} … p_{c_{k}})

be a representation of the permutation π. Note that c_{k} = n − 1. Any extension of π to a permutation of {1, …, n} also having exactly k cycles must have the form

π = (p_{1} …) … (… p_{i} n p_{i+1} …) … (… p_{n−1})

for some i = 1, …, n − 1. If p_{i} and p_{i+1} belong to different cycles, we may put n always to the cycle of p_{i}. This is without loss of generality because (a_{1} a_{2} … a_{ℓ}) = (a_{ℓ} a_{1} a_{2} … a_{ℓ−1}). We have found that there are exactly n − 1 ways to extend π to a permutation of {1, …, n} leaving the number of cycles fixed. Putting things together we obtain c(n, k) = (n − 1)c(n − 1, k) + c(n − 1, k − 1), as claimed.

Exercise 26 Prove

x^{n} = ∑_{k=0}^{n} S(n, k)x\underline{k}, x\underline{n} = ∑_{k=0}^{n} s(n, k)x^{k} (n ∈ ℕ_{0})

where S(n, k) and s(n, k) denote the Striling numbers of the second and first kind, respectively.

(1) For n = 0 there is nothing to prove. Suppose the formula holds for some n ≥ 0. Then

∑_{k=0}^{n+1} S(n + 1, k)x\underline{k} = ∑_{k=0}^{n+1} kS(n, k)x\underline{k} + ∑_{k=0}^{n+1} S(n, k − 1)x\underline{k}

= ∑_{k=0}^{n} S(n, k)x\underline{k} + ∑_{k=−1}^{n} S(n, k)x\underline{k+1} = ∑_{k=0}^{n} S(n, k)x\underline{k} + ∑_{k=0}^{n} S(n, k)x\underline{k}(x − k)

= ∑_{k=0}^{n} S(n, k)x\underline{k} + x ∑_{k=0}^{n} S(n, k)x\underline{k} − ∑_{k=0}^{n} S(n, k)x\underline{k} = x^{n+1},

and we are done.

(2) We consider the generating function G_{n}(y) of s(n, k). The recurrence for c(n, k) together with the definition of s(n, k) gives the recurrence

s(n, k) = (1 − n)s(n − 1, k) + s(n − 1, k − 1) (n, k ≥ 1)

Note that s(n, k) = 0 for k > n, so it suffices to show the claim for the generating function in place of the finite sum. For n = 0 we have G_{0}(y) = 1. For n > 0 we have

G_{n}(y) = ∑_{k=0}^{∞} s(n, k)y^{k} = (1 − n) ∑_{k=0}^{∞} s(n − 1, k)x^{k} + ∑_{k=0}^{∞} s(n − 1, k − 1)x^{k}

= (1 − n)G_{n−1}(y) + ∑_{k=1}^{∞} s(n − 1, k − 1)x^{k} = (1 − n)G_{n−1}(y) + x ∑_{k=0}^{∞} s(n − 1, k)x^{k}
= (y + 1 − n)G_{n−1}(y).

This gives

G_{1}(y) = y = y\underline{1},
G_{2}(y) = y(y − 1) = y\underline{2},
G_{3}(y) = y(y − 1)(y − 2) = y\underline{3}, …
G_{k}(y) = y(y − 1) ⋯ (y − (k − 1)) = y\underline{k}.

Exercise 27 Is ℂ[[x]] a Eucledian domain?

Yes: We have to provide a degree function deg: ℂ[[x]]\{0} → ℕ_{0} such that deg ab ≥ deg a for all a, b ≠ 0 and such that for all a, b ∈ ℂ[[x]], b ≠ 0 there exists elements q, r ∈ ℂ[[x]] with a = qb + r where r = 0 or deg r < deg b. For every nonzero power series a = ∑_{n=0}^{∞} a_{n}x^{n} put deg a := min{ n ∈ ℕ_{0} : a_{n} ≠ 0 }. Let a, b ≠ 0 be arbitrary power series. Then a = x^{deg a}ã, b = x^{deg b}b̃ where ã, b̃ are invertible. (We use the statement of Exercise 29.) Apparently we have deg ã = deg b̃ = 0 = deg ãb̃, the latter “=” because ℂ[[x]] is an integral domain. It follows that deg ab = deg a + deg b ≥ deg a, as required. Now, assume deg a ≥ deg b and define q = \frac{ã}{b̃}x^{deg a−deg b} (recall that b̃ is invertible) and r = 0. Then

qb + r = qb = \frac{ã}{b̃}x^{deg a−deg b} · x^{deg b}b̃ + 0 = ãx^{deg a} = a,

as required. On the other hand, if deg a < deg b, define q = 0 and r = a. Then again a = qb + r and deg r < deg b.

Exercise 28 What is the quotient field of ℂ[[x]]?

Let a(x) = ∑_{n=0}^{∞} a_{n}x^{n} ∈ ℂ[[x]] be a power which does not have an inverse (a(x) ≠ 0). Let N be the least number N ∈ ℕ such that a_{N} ≠ 0. According to the next exercise, N > 0 and and ã(x) := ∑_{n=0}^{∞} ã_{n}x^{n} where ã_{n} := a_{n+N} is invertible. We have a(x) = x^{N} ã(x). If there were an inverse (x^{N})^{−1} for x^{N} then there were also an inverse for a(x), namely a^{−1}(x) = ã^{−1}(x)(x^{N})^{−1}. This motivates the consideration of ℂ((x)) := ℂ[[x]][Y]/⟨xY − 1⟩. Indeed ℂ((x)) is a field which contains ℂ[[x]], and every element of ℂ((x)) can be written as the quotient of two power series. Hence ℂ((x)) = Q(ℂ[[x]]).

Exercise 29 Prove: ∑_{n=0}^{∞} a_{n}x^{n} ∈ ℂ[[x]] has a multiplicative inverse if and only if a_{0} ≠ 0.

“⟹” Suppose ∑_{n=0}^{∞} a_{n}x^{n} has ∑_{n=0}^{∞} b_{n}x^{n} as its multiplicative inverse. Then

1 = ∑_{n=0}^{∞} a_{n}x^{n} ∑_{n=0}^{∞} b_{n}x^{n} = ∑_{n=0}^{∞} ( ∑_{k=0}^{n} a_{k}b_{n−k})x^{n}.

Comparing coefficients gives a_{0}b_{0} = 1, and hence a_{0} ≠ 0. “⟸” Let a = ∑_{n=0}^{∞} a_{n}x^{n} be a formal power series with a_{0} ≠ 0. We make an indetermined ansatz for the inverse a^{−1} = ∑_{n=0}^{∞} b_{n}x^{n}. In order to be the inverse it must be satisfied

1 = ∑_{n=0}^{∞} ( ∑_{k=0}^{n} a_{k}b_{n−k})x^{n}.

Comparing coefficients gives a_{0}b_{0} = 1, so b_{0} = 1/a_{0}. Suppose the coefficients of a^{−1} are known up to some n ≥ 0. Then

∑_{k=0}^{n+1} a_{k}b_{n+1−k} = 0  ⟹  b_{n+1} = \frac{1}{a_{0}} ∑_{k=1}^{n+1} a_{k}b_{n+1−k}

shows that also the next coefficient exists. By induction, all coefficient exist and so a^{−1} exists.