Exercises from Section 1.2.9

Let $G (z) = \sum_{n \geq 0} (2^{n} + 3^{n}) z^{n}$ be the generating function for the sequence $⟨ 2^{n} + 3^{n} ⟩$ . Then

\begin{array}{l} G (z) & = \sum_{n \geq 0} (2^{n} + 3^{n}) z^{n} \\ = \sum_{n \geq 0} 2^{n} z^{n} + \sum_{n \geq 0} 3^{n} z^{n} & by Eq. (2) \\ = \sum_{n \geq 0} {(2 z)}^{n} + \sum_{n \geq 0} {(3 z)}^{n} \\ = \frac{1}{1 - 2 z} + \frac{1}{1 - 3 z} . & by Eq. (5) \end{array}

Proposition. $(\sum_{n \geq 0} \frac{a_{n}}{n!} z^{n}) (\sum_{n \geq 0} \frac{b_{n}}{n!} z^{n}) = \sum_{n \geq 0} \frac{\sum_{0 \leq k \leq n} (\binom{n}{k}) a_{k} b_{n - k}}{n!} z^{n}$ .

Proof. Let $n$ be an arbitrary nonnegative integer, and $⟨ a_{n} ∕ n! ⟩$ , $⟨ b_{n} ∕ n! ⟩$ two arbitrary sequences. We must show that

(\sum_{n \geq 0} \frac{a_{n}}{n!} z^{n}) (\sum_{n \geq 0} \frac{b_{n}}{n!} z^{n}) = \sum_{n \geq 0} \frac{\sum_{0 \leq k \leq n} (\binom{n}{k}) a_{k} b_{n - k}}{n!} z^{n} .

But

\begin{array}{l} (\sum_{n \geq 0} \frac{a_{n}}{n!} z^{n}) (\sum_{n \geq 0} \frac{b_{n}}{n!} z^{n}) & = \sum_{n \geq 0} \sum_{0 \leq k \leq n} \frac{a_{k}}{k!} \frac{b_{n - k}}{(n - k)!} z^{n} & by Eq. (6) \\ = \sum_{n \geq 0} \sum_{0 \leq k \leq n} \frac{1}{n!} \frac{n!}{k! (n - k)!} a_{k} b_{n - k} z^{n} \\ = \sum_{n \geq 0} \sum_{0 \leq k \leq n} \frac{1}{n!} (\binom{n}{k}) a_{k} b_{n - k} z^{n} \\ = \sum_{n \geq 0} \frac{\sum_{0 \leq k \leq n} (\binom{n}{k}) a_{k} b_{n - k}}{n!} z^{n} \end{array}

as we needed to show. □

If we diﬀerentiate the generating function for the harmonic numbers $⟨ H_{n} ⟩$ , Eq. (18),

G (z) = \sum_{n \geq 0} H_{n} z^{n} = \frac{1}{1 - z} \ln \frac{1}{1 - z},

we ﬁnd that

\begin{array}{l} \frac{d}{d z} G (z) & = \frac{d}{d z} (\frac{1}{1 - z} \ln \frac{1}{1 - z}) \\ = \frac{d}{d z} (\frac{1}{1 - z}) \ln \frac{1}{1 - z} + \frac{1}{1 - z} \frac{d}{d z} (\ln \frac{1}{1 - z}) \\ = \frac{1}{{(1 - z)}^{2}} \ln \frac{1}{1 - z} + \frac{1}{1 - z} \frac{d}{d z} (\ln \frac{1}{1 - z}) & by Eq. (16) \\ = \frac{1}{{(1 - z)}^{2}} \ln \frac{1}{1 - z} + \frac{1}{1 - z} \frac{\frac{d}{d z} (1 ∕ (1 - z))}{1 ∕ (1 - z)} \\ = \frac{1}{{(1 - z)}^{2}} \ln \frac{1}{1 - z} + \frac{1 - z}{1 - z} \frac{1}{{(1 - z)}^{2}} & by Eq. (16) \\ = \frac{1}{{(1 - z)}^{2}} \ln \frac{1}{1 - z} + \frac{1}{{(1 - z)}^{2}} . \end{array}

The generating function for $⟨ \sum_{0 \leq k \leq n} H_{k} ⟩$ is

\begin{array}{l} H (z) & = \sum_{n \geq 0} \sum_{0 \leq k \leq n} H_{k} z^{n} \\ = \sum_{n \geq 0} (\sum_{0 \leq k \leq n} H_{k} \cdot 1) z^{n} \\ = (\sum_{n \geq 0} H_{n} z^{n}) (\sum_{n \geq 0} 1 \cdot z^{n}) & by Eq. (6) \\ = (\sum_{n \geq 0} H_{n} z^{n}) (\sum_{n \geq 0} z^{n}) \\ = G (z) \frac{1}{1 - z} & by Eq. (5) \\ = \frac{1}{1 - z} \ln (\frac{1}{1 - z}) \frac{1}{1 - z} \\ = \frac{1}{{(1 - z)}^{2}} \ln \frac{1}{1 - z} \\ = \frac{d}{d z} G (z) - \frac{1}{{(1 - z)}^{2}} \\ = \frac{d}{d z} G (z) - \frac{d}{d z} \frac{1}{1 - z} & by Eq. (16) \\ = \frac{d}{d z} G (z) - \sum_{n \geq 0} (n + 1) z^{n} & by Eq. (16) \\ = \sum_{n \geq 0} (n + 1) H_{n + 1} z^{n} - \sum_{n \geq 0} (n + 1) z^{n} & by Eq. (14) \\ = \sum_{n \geq 0} ((n + 1) H_{n + 1} - (n + 1)) z^{n} \\ = \sum_{n \geq 0} ((n + 1) H_{n + 1} - 1 - n) z^{n} \\ = \sum_{n \geq 0} ((n + 1) H_{n + 1} - \frac{n + 1}{n + 1} - n) z^{n} \\ = \sum_{n \geq 0} ((n + 1) (H_{n + 1} - \frac{1}{n + 1}) - n) z^{n} \\ = \sum_{n \geq 0} ((n + 1) H_{n} - n) z^{n} \\ = \sum_{n \geq 0} (n H_{n} + H_{n} - n) z^{n} . \end{array}

Then,

\begin{array}{l} \sum_{0 \leq k \leq n} H_{k} = n H_{n} + H_{n} - n \\ \Leftrightarrow \sum_{0 \leq k \leq n} H_{k} - H_{n} = n H_{n} - n \\ \Leftrightarrow \sum_{0 \leq k \leq n - 1} H_{k} = n H_{n} - n \\ \Leftrightarrow \sum_{0 \leq k \leq n - 1} H_{k} - 0 = n H_{n} - n \\ \Leftrightarrow \sum_{0 \leq k \leq n - 1} H_{k} - H_{0} = n H_{n} - n \\ \Leftrightarrow \sum_{1 \leq k \leq n - 1} H_{k} = n H_{n} - n, \end{array}

in agreement with Eq. 1.2.7-(8).

Eq. (19),

{(1 + z)}^{r} = \sum_{k \geq 0} (\binom{r}{k}) z^{k},

is a special case of Eq. (21),

x^{r} = \sum_{k \geq 0} (\binom{r - k t}{k}) \frac{r}{r - k t} z^{k},

for $t = 0$ . Then, since $x^{t + 1} = x^{t} + z = x = 1 + z$ ,

\begin{array}{l} x^{r} & = {(1 + z)}^{r} \\ = \sum_{k \geq 0} (\binom{r - k t}{k}) \frac{r}{r - k t} z^{k} \\ = \sum_{k \geq 0} (\binom{r}{k}) \frac{r}{r} z^{k} \\ = \sum_{k \geq 0} (\binom{r}{k}) z^{k} . \end{array}

Proposition. ${(e^{z} - 1)}^{n} = n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!}$ .

Proof. Let $n$ be an arbitrary nonnegative integer. We must show that

{(e^{z} - 1)}^{n} = n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!} .

If $n = 0$ ,

\begin{array}{l} {(e^{z} - 1)}^{0} & = 1 \\ = z^{0} \\ = \{\binom{0}{0}\} \frac{z^{0}}{0!} \\ = \sum_{k} \{\binom{k}{0}\} \frac{z^{k}}{k!} \\ = 0! \sum_{k} \{\binom{k}{0}\} \frac{z^{k}}{k!} . \end{array}

Then, assuming

{(e^{z} - 1)}^{n} = n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!},

we must show

{(e^{z} - 1)}^{n + 1} = (n + 1)! \sum_{k} \{\binom{k}{n + 1}\} \frac{z^{k}}{k!} .

But

\begin{array}{l} {(e^{z} - 1)}^{n + 1} & = (e^{z} - 1) {(e^{z} - 1)}^{n} \\ = (e^{z} - 1) n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!} \\ = ((\sum_{k \geq 0} \frac{1}{k!} z^{k}) - 1) n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!} & by Eq. (22) \\ = (\sum_{k \geq 0} \frac{1}{k!} z^{k}) (n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!}) - n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!} \\ = n! (\sum_{k \geq 0} \frac{1}{k!} z^{k}) (\sum_{k \geq 0} \{\binom{k}{n}\} \frac{1}{k!} z^{k}) - n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!} \\ = n! \sum_{k} \frac{1}{k!} \sum_{j} (\binom{k}{j}) \{\binom{j}{n}\} z^{k} - n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!} & by Eq. (11) \\ = n! \sum_{k} \frac{1}{k!} \{\binom{k + 1}{n + 1}\} z^{k} - n! \sum_{k} \{\binom{k}{n}\} \frac{z^{k}}{k!} & by Eq. 1.2.6-(52) \\ = n! \sum_{k} (\{\binom{k + 1}{n + 1}\} - \{\binom{k}{n}\}) \frac{z^{k}}{k!} \\ = n! \sum_{k} (n + 1) \{\binom{k}{n + 1}\} \frac{z^{k}}{k!} & by Eq. 1.2.6-(46) \\ = (n + 1)! \sum_{k} \{\binom{k}{n + 1}\} \frac{z^{k}}{k!} \end{array}

as we needed to show. □

The generating function for

⟨ \sum_{0 < k < n} \frac{1}{k (n - k)} ⟩

is

\begin{array}{l} G (z) & = \sum_{n > 0} \sum_{0 < k < n} \frac{1}{k (n - k)} z^{n} \\ = \sum_{n > 0} \sum_{0 < k < n} \frac{1}{k} \frac{1}{n - k} z^{n} \\ = (\sum_{n > 0} \frac{1}{n} z^{n}) (\sum_{n > 0} \frac{1}{n} z^{n}) & by Eq. (6) \\ = {(\sum_{n > 0} \frac{1}{n} z^{n})}^{2} \\ = {(\ln \frac{1}{1 - z})}^{2} . & by Eq. (17) \end{array}

Diﬀerentiating, we ﬁnd

\begin{array}{l} \frac{d}{d z} G (z) & = \frac{d}{d z} {(\ln \frac{1}{1 - z})}^{2} \\ = 2 \ln \frac{1}{1 - z} \frac{d}{d z} \ln \frac{1}{1 - z} \\ = 2 \ln \frac{1}{1 - z} (1 - z) \frac{d}{d z} f r a c 11 - z \\ = 2 \ln \frac{1}{1 - z} (1 - z) \frac{1}{{(1 - z)}^{2}} & by Eq. (16) \\ = 2 \frac{1}{1 - z} \ln \frac{1}{1 - z} \\ = 2 \sum_{n \geq 0} H_{n} z^{n} . & by Eq. (18) \end{array}

Then,

\begin{array}{l} G (z) & = \int_{0}^{z} \frac{d}{d t} G (t) d t \\ = \int_{0}^{z} 2 \sum_{n \geq 0} H_{n} t^{n} d t \\ = 2 \int_{0}^{z} \sum_{n \geq 0} H_{n} t^{n} d t \\ = 2 \sum_{n \geq 1} \frac{1}{n} H_{n - 1} z^{n} & by Eq. (15) \\ = \sum_{n > 0} \frac{2}{n} H_{n - 1} z^{n} . \end{array}

And so,

\sum_{0 < k < n} \frac{1}{k (n - k)} = 2 H_{n - 1} ∕ n

for $n > 0$ .

Suppose that we have $n$ numbers $x_{1}, x_{2}, \dots, x_{n}$ and we want the sum

h_{m} = \sum_{1 \leq j_{1} \leq n} x_{j_{1}} \sum_{j_{1} \leq j_{2} \leq n} x_{j_{2}} \dots \sum_{j_{m - 1} \leq j_{m} \leq n} x_{j_{m}} = \sum_{1 \leq j_{1} \leq \dots \leq j_{m} \leq n} x_{j_{1}} \dots x_{j_{m}},

expressed in terms of $S_{1}, S_{2}, \dots, S_{m}$ , where

S_{j} = \sum_{1 \leq k \leq n} x_{k}^{j},

the sum of $j$ th powers. First, we establish the identity

\sum_{1 \leq j_{1} \leq \dots \leq j_{m} \leq n} x_{j_{1}} \dots x_{j_{m}} = \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} = n \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{n}^{k_{n}} . (7.1)

If $n = 1$ ,

\begin{array}{l} \sum_{1 \leq j_{1} \leq 1} x_{j_{1}} & = x_{1} \\ = x_{1}^{1} \\ = \sum_{\begin{array}{c} k_{1} \geq 0 \\ k_{1} = 1 \end{array}} x_{1}^{k_{1}} . \end{array}

Then, assuming

\sum_{1 \leq j_{1} \leq \dots \leq j_{m} \leq n} x_{j_{1}} \dots x_{j_{m}} = \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} = n \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{n}^{k_{n}},

we must show

\sum_{1 \leq j_{1} \leq \dots \leq j_{m + 1} \leq n + 1} x_{j_{1}} \dots x_{j_{m + 1}} = \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n + 1} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n + 1} = n + 1 \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{n + 1}^{k_{n + 1}} .

But

\begin{array}{l} \sum_{1 \leq j_{1} \leq \dots \leq j_{m + 1} \leq n + 1} x_{j_{1}} \dots x_{j_{m + 1}} & = \sum_{1 \leq j_{m + 1} \leq n + 1} x_{j_{m + 1}} \sum_{1 \leq j_{1} \leq \dots \leq j_{m} \leq j_{m + 1}} x_{j_{1}} \dots x_{j_{m}} \\ = \sum_{1 \leq j_{m + 1} \leq n + 1} x_{j_{m + 1}} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} = n \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{n}^{k_{n}} \\ \begin{aligned} = \sum_{\begin{array}{c} k_{1} + 1, k_{2}, \dots, k_{n}, 0 \geq 0 \\ k_{1} + 1 + k_{2} + \dots + k_{n} + 0 = n + 1 \end{array}} x_{1}^{k_{1} + 1} x_{2}^{k_{2}} \dots x_{n}^{k_{n}} x_{n + 1}^{0} \\ + \sum_{\begin{array}{c} k_{1}, k_{2} + 1, \dots, k_{n}, 0 \geq 0 \\ k_{1} + k_{2} + 1 + \dots + k_{n} + 0 = n + 1 \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2} + 1} \dots x_{n}^{k_{n}} x_{n + 1}^{0} \\ + \dots + \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} + 1, 0 \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} + 1 = n + 1 \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{n}^{k_{n} + 1} x_{n + 1}^{0} \\ + \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n}, 1 \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} + 1 = n + 1 \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{n}^{k_{n}} x_{n + 1}^{1} \end{aligned} \\ = \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n + 1} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n + 1} = n + 1 \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{n + 1}^{k_{n + 1}}, \end{array}

as we needed to show. Now let

G (z) = \sum_{k \geq 0} h_{k} z^{k} .

Then

\begin{array}{l} G (z) & = \sum_{k \geq 0} h_{k} z^{k} \\ = \sum_{k \geq 0} \sum_{1 \leq j_{1} \leq \dots \leq j_{k} \leq n} x_{j_{1}} \dots x_{j_{k}} z^{k} \\ = \sum_{k \geq 0} z^{k} \sum_{1 \leq j_{1} \leq \dots \leq j_{k} \leq n} x_{j_{1}} \dots x_{j_{k}} \\ = \sum_{k \geq 0} z^{k} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} = n \end{array}} x_{1}^{k_{1}} x_{2}^{k_{2}} \dots x_{n}^{k_{n}} & by (7.1) \\ = \prod_{1 \leq j \leq n} \sum_{k \geq 0} x_{j}^{k} z^{k} & by Eq. (9) \\ = \prod_{1 \leq j \leq n} \sum_{k \geq 0} {(x_{j} z)}^{k} \\ = \prod_{1 \leq j \leq n} \frac{1}{1 - x_{j} z} & by Eq. (5) . \end{array}

Taking the logarithm yields

\begin{array}{l} \ln G (z) & = \ln \prod_{1 \leq j \leq n} \frac{1}{1 - x_{j} z} \\ = \sum_{1 \leq j \leq n} \ln \frac{1}{1 - x_{j} z} \\ = \sum_{1 \leq j \leq n} \sum_{k \geq 1} \frac{1}{k} {(x_{j} z)}^{k} & by Eq. (17) \\ = \sum_{k \geq 1} \frac{\sum_{1 \leq j \leq n} x_{j}^{k} z^{k}}{k} \\ = \sum_{k \geq 1} \frac{S_{k} z^{k}}{k} . \end{array}

Finally,

\begin{array}{l} G (z) & = e^{\ln G (z)} \\ = \exp (\sum_{k \geq 1} \frac{S_{k} z^{k}}{k}) \\ = \prod_{k \geq 1} e^{S_{k} z^{k} ∕ k} \\ = \prod_{k \geq 1} \sum_{j \geq 0} \frac{1}{j!} {(\frac{S_{k} z^{k}}{k})}^{j} & by Eq. (22) \\ = \prod_{k \geq 1} \sum_{j \geq 0} \frac{S_{k}^{j} {(z^{k})}^{j}}{k^{j} j!} \\ = \prod_{j \geq 1} \sum_{k \geq 0} \frac{S_{j}^{k}}{j^{k} k!} {(z^{j})}^{k} \\ = \prod_{j \geq 1} \sum_{k \geq 0} \frac{S_{j}^{k}}{j^{k} k!} z^{j k} \\ = \prod_{j \geq 1} \sum_{k ∕ j \geq 0} \frac{S_{j}^{k ∕ j}}{j^{k ∕ j} (k ∕ j)!} z^{k} \\ = \sum_{n \geq 0} z^{n} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} = n \end{array}} \frac{S_{1}^{k_{1} ∕ 1}}{1^{k_{1} ∕ 1} (k_{1} ∕ 1)!} \frac{S_{2}^{k_{2} ∕ 2}}{2^{k_{2} ∕ 2} (k_{2} ∕ 2)!} \dots \frac{S_{n}^{k_{n} ∕ n}}{n^{k_{n} ∕ n} (k_{n} ∕ n)!} & by Eq. (9) \\ = \sum_{n \geq 0} z^{n} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + 2 k_{2} + \dots + n k_{n} = n \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \frac{S_{2}^{k_{2}}}{2^{k_{2}} k_{2}!} \dots \frac{S_{n}^{k_{n}}}{n^{k_{n}} k_{n}!}, \end{array}

and hence Eq. (38).

The number of partitions $p (n)$ corresponds to the number of solutions of the equation $k_{1} + 2 k_{2} + \dots + n k_{n} = n$ , where $k_{j} \geq 0$ is the number of $j$ s in the partition. For example, for $n = 5$ ,

\begin{array}{l} p (5) & = \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{5} \geq 0 \\ k_{1} + 2 k_{2} + \dots + 5 k_{5} = 5 \end{array}} 1 \\ \begin{aligned} = (1 \cdot 5 + 2 \cdot 0 + 3 \cdot 0 + 4 \cdot 0 + 5 \cdot 0) ∕ 5 \\ + (1 \cdot 3 + 2 \cdot 1 + 3 \cdot 0 + 4 \cdot 0 + 5 \cdot 0) ∕ 5 \\ + (1 \cdot 1 + 2 \cdot 2 + 3 \cdot 0 + 4 \cdot 0 + 5 \cdot 0) ∕ 5 \\ + (1 \cdot 2 + 2 \cdot 0 + 3 \cdot 1 + 4 \cdot 0 + 5 \cdot 0) ∕ 5 \\ + (1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 + 5 \cdot 0) ∕ 5 \\ + (1 \cdot 1 + 2 \cdot 0 + 3 \cdot 0 + 4 \cdot 1 + 5 \cdot 0) ∕ 5 \\ + (1 \cdot 0 + 2 \cdot 0 + 3 \cdot 0 + 4 \cdot 1 + 5 \cdot 1) ∕ 5 \end{aligned} \\ \begin{aligned} = (1 + 1 + 1 + 1 + 1) ∕ 5 \\ + (1 + 1 + 1 + 2) ∕ 5 \\ + (1 + 2 + 2) ∕ 5 \\ + (1 + 1 + 3) ∕ 5 \\ + (2 + 3) ∕ 5 \\ + (1 + 4) ∕ 5 \\ + (5) ∕ 5 \end{aligned} \\ = 7 . \end{array}

The generating function for $p (n)$ is therefore obtained by making all possible combinations from $1$ to $n$ available through multiplication, so that the coeﬃcient is the sum count of these combinations, as

G (z) = \sum_{n \geq 0} p (n) z^{n} = \prod_{j \geq 1} \sum_{k \geq 0} z^{j k} .

For example, for $n = 5$ ,

\begin{array}{l} [z^{5}] G (z) & = [z^{5}] \sum_{n \geq 0} p (n) z^{n} \\ = [z^{5}] \prod_{j \geq 1} \sum_{k \geq 0} z^{j k} \\ \begin{aligned} = [z^{5}] \dots + z^{1 \cdot 5 + 2 \cdot 0 + 3 \cdot 0 + 4 \cdot 0 + 5 \cdot 0} \\ + z^{1 \cdot 3 + 2 \cdot 1 + 3 \cdot 0 + 4 \cdot 0 + 5 \cdot 0} \\ + z^{1 \cdot 1 + 2 \cdot 2 + 3 \cdot 0 + 4 \cdot 0 + 5 \cdot 0} \\ + z^{1 \cdot 2 + 2 \cdot 0 + 3 \cdot 1 + 4 \cdot 0 + 5 \cdot 0} \\ + z^{1 \cdot 0 + 2 \cdot 1 + 3 \cdot 1 + 4 \cdot 0 + 5 \cdot 0} \\ + z^{1 \cdot 1 + 2 \cdot 0 + 3 \cdot 0 + 4 \cdot 1 + 5 \cdot 0} \\ + z^{1 \cdot 0 + 2 \cdot 0 + 3 \cdot 0 + 4 \cdot 1 + 5 \cdot 1} + \dots \end{aligned} \\ \begin{aligned} = [z^{5}] \dots + z^{1 + 1 + 1 + 1 + 1} \\ + z^{1 + 1 + 1 + 2} \\ + z^{1 + 2 + 2} \\ + z^{1 + 1 + 3} \\ + z^{2 + 3} \\ + z^{1 + 4} \\ + z^{5} + \dots \end{aligned} \\ = [z^{5}] 7 z^{5} \\ = 7 . \end{array}

So,

\begin{array}{l} G (z) & = \sum_{n \geq 0} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + 2 k_{2} + \dots + n k_{n} = n \end{array}} z^{n} \\ = \sum_{n \geq 0} z^{n} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + 2 k_{2} + \dots + n k_{n} = n \end{array}} 1^{k_{1}} 1^{k_{2}} \dots 1^{k_{n}} \\ = \sum_{n \geq 0} z^{n} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} = n \end{array}} 1^{k_{1} ∕ 1} 1^{k_{2} ∕ 2} \dots 1^{k_{n} ∕ n} \\ = \prod_{j \geq 1} \sum_{k ∕ j \geq 0} 1^{k ∕ j} z^{k} & by Eq. (9) \\ = \prod_{j \geq 1} \sum_{k \geq 0} z^{j k} \\ = \prod_{j \geq 1} \sum_{k \geq 0} {(z^{j})}^{k} \\ = \prod_{j \geq 1} \frac{1}{1 - z^{j}} & by Eq. (5) \\ = \frac{1}{\prod_{n \geq 1} (1 - z^{n})} . \end{array}

That is,

\begin{array}{l} G (z) & = \sum_{n \geq 0} p (n) z^{n} \\ = \sum_{n \geq 0} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + 2 k_{2} + \dots + n k_{n} = n \end{array}} z^{n} \\ = \prod_{j \geq 1} \sum_{k \geq 0} z^{j k} \\ = \frac{1}{\prod_{n \geq 1} (1 - z^{n})} . \end{array}

______________________________________________________________________________________________________________________________

[G. Pólya, Induction and Analogy in Mathematics (Princeton: Princeton University Press, 1954), Chapter 6]

Suppose that we have $n$ numbers $x_{1}, x_{2}, \dots, x_{n}$ and we want the sum

h_{m} = \sum_{1 \leq j_{1} \leq n} x_{j_{1}} \sum_{j_{1} \leq j_{2} \leq n} x_{j_{2}} \dots \sum_{j_{m - 1} \leq j_{m} \leq n} x_{j_{m}} = \sum_{1 \leq j_{1} \leq \dots \leq j_{m} \leq n} x_{j_{1}} \dots x_{j_{m}},

expressed in terms of $S_{1}, S_{2}, \dots, S_{m}$ , where

S_{j} = \sum_{1 \leq k \leq n} x_{k}^{j},

the sum of $j$ th powers. In particular, $h_{4}$ . But

\begin{array}{l} [z^{4}] G (z) & = [z^{4}] \sum_{k \geq 0} h_{k} z^{k} & by Eq. (35) \\ = [z^{4}] \sum_{n \geq 0} z^{n} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + 2 k_{2} + \dots + n k_{n} = n \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \frac{S_{2}^{k_{2}}}{2^{k_{2}} k_{2}!} \dots \frac{S_{n}^{k_{n}}}{n^{k_{n}} k_{n}!} & by Eq. (38) \\ = \sum_{\begin{array}{c} k_{1}, k_{2}, k_{3}, k_{4} \geq 0 \\ k_{1} + 2 k_{2} + 3 k_{3} + 4 k_{4} = 4 \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \frac{S_{2}^{k_{2}}}{2^{k_{2}} k_{2}!} \frac{S_{3}^{k_{3}}}{3^{k_{3}} k_{3}!} \frac{S_{4}^{k_{4}}}{4^{k_{n}} k_{4}!} \\ \begin{aligned} = \frac{S_{1}^{4}}{1^{4} 4!} \frac{S_{2}^{0}}{2^{0} 0!} \frac{S_{3}^{0}}{3^{0} 0!} \frac{S_{4}^{0}}{4^{0} 0!} \\ + \frac{S_{1}^{2}}{1^{2} 2!} \frac{S_{2}^{1}}{2^{1} 1!} \frac{S_{3}^{0}}{3^{0} 0!} \frac{S_{4}^{0}}{4^{0} 0!} \\ + \frac{S_{1}^{1}}{1^{1} 1!} \frac{S_{2}^{0}}{2^{0} 0!} \frac{S_{3}^{1}}{3^{1} 1!} \frac{S_{4}^{0}}{4^{0} 0!} \\ + \frac{S_{1}^{0}}{1^{0} 0!} \frac{S_{2}^{2}}{2^{2} 2!} \frac{S_{3}^{0}}{3^{0} 0!} \frac{S_{4}^{0}}{4^{0} 0!} \\ + \frac{S_{1}^{0}}{1^{0} 0!} \frac{S_{2}^{0}}{2^{0} 0!} \frac{S_{3}^{0}}{3^{0} 0!} \frac{S_{4}^{1}}{4^{1} 1!} \end{aligned} \\ = \frac{S_{1}^{4}}{1^{4} 4!} + \frac{S_{1}^{2}}{1^{2} 2!} \frac{S_{2}^{1}}{2^{1} 1!} + \frac{S_{1}^{1}}{1^{1} 1!} \frac{S_{3}^{1}}{3^{1} 1!} + \frac{S_{2}^{2}}{2^{2} 2!} + \frac{S_{4}^{1}}{4^{1} 1!} \\ = \frac{S_{1}^{4}}{24} + \frac{S_{1}^{2}}{2} \frac{S_{2}}{2} + S_{1} \frac{S_{3}}{3} + \frac{S_{2}^{2}}{8} + \frac{S_{4}}{4} \\ = \frac{1}{24} S_{1}^{4} + \frac{1}{4} S_{1}^{2} S_{2} + \frac{1}{8} S_{2}^{2} + \frac{1}{3} S_{1} S_{3} + \frac{1}{4} S_{4} . \end{array}

Suppose that we have $n$ numbers $x_{1}, x_{2}, \dots, x_{n}$ and we want the elementary symmetric function

e_{m} = \sum_{1 \leq j_{1} \leq n} x_{j_{1}} \sum_{j_{1} < j_{2} \leq n} x_{j_{2}} \dots \sum_{j_{m - 1} < j_{m} \leq n} x_{j_{m}} = \sum_{1 \leq j_{1} < \dots < j_{m} \leq n} x_{j_{1}} \dots x_{j_{m}},

expressed in terms of $S_{1}, S_{2}, \dots, S_{m}$ , where

S_{j} = \sum_{1 \leq k \leq n} x_{k}^{j},

the sum of $j$ th powers. First, we establish the identity

\sum_{k \geq 0} \sum_{1 \leq j_{1} < \dots < j_{k} \leq n} x_{j_{1}} \dots x_{j_{k}} z^{k} = \prod_{1 \leq j \leq n} (1 + x_{j} z) . (10.1)

If $n = 1$ ,

\begin{array}{l} \sum_{k \geq 0} \sum_{1 \leq j_{1} \leq 1} x_{j_{1}} \dots x_{j_{k}} z^{k} \\ = \sum_{k \geq 0} x_{1} \dots x_{j_{k}} z^{k} \\ = z^{0} + x_{1} z^{1} \\ = 1 + x_{1} z \\ = \prod_{1 \leq j \leq 1} (1 + x_{j} z) . \end{array}

Then, assuming

\sum_{k \geq 0} \sum_{1 \leq j_{1} < \dots < j_{k} \leq n} x_{j_{1}} \dots x_{j_{k}} z^{k} = \prod_{1 \leq j \leq n} (1 + x_{j} z),

we must show

\sum_{k \geq 0} \sum_{1 \leq j_{1} < \dots < j_{k + 1} \leq n + 1} x_{j_{1}} \dots x_{j_{k + 1}} z^{k + 1} = \prod_{1 \leq j \leq n + 1} (1 + x_{j} z) .

But

\begin{array}{l} \sum_{k \geq 0} \sum_{1 \leq j_{1} < \dots < j_{k + 1} \leq n + 1} x_{j_{1}} \dots x_{j_{k + 1}} z^{k + 1} \\ = \sum_{k \geq 0} \sum_{1 \leq j_{k + 1} \leq n + 1} x_{j_{k + 1}} z \sum_{1 \leq j_{1} < \dots < j_{k} < j_{k + 1}} x_{j_{1}} \dots x_{j_{k}} z^{k} \\ \begin{aligned} = \sum_{k \geq 0} \sum_{1 \leq j_{k + 1} < n + 1} x_{j_{k + 1}} z \sum_{1 \leq j_{1} < \dots < j_{k} < j_{k + 1}} x_{j_{1}} \dots x_{j_{k}} z^{k} \\ + \sum_{k \geq 0} \sum_{j_{k + 1} = n + 1} x_{j_{k + 1}} z \sum_{1 \leq j_{1} < \dots < j_{k} < j_{k + 1}} x_{j_{1}} \dots x_{j_{k}} z^{k} \end{aligned} \\ = \sum_{k \geq 0} \sum_{1 \leq j_{1} < \dots < j_{k} \leq n} x_{j_{1}} \dots x_{j_{k}} z^{k} + \sum_{k \geq 0} x_{n + 1} z \sum_{1 \leq j_{1} < \dots < j_{k} \leq n} x_{j_{1}} \dots x_{j_{k}} z^{k} \\ = (1 + x_{n + 1} z) \sum_{k \geq 0} \sum_{1 \leq j_{1} < \dots < j_{k} \leq n} x_{j_{1}} \dots x_{j_{k}} z^{k} \\ = (1 + x_{n + 1} z) \prod_{1 \leq j \leq n} (1 + x_{j} z) \\ = \prod_{1 \leq j \leq n + 1} (1 + x_{j} z), \end{array}

as we needed to show. Now let

G (z) = \sum_{k \geq 0} e_{k} z^{k} .

Then

\begin{array}{l} G (z) & = \sum_{k \geq 0} e_{k} z^{k} \\ = \sum_{k \geq 0} \sum_{1 \leq j_{1} < \dots < j_{k} \leq n} x_{j_{1}} \dots x_{j_{k}} z^{k} \\ = \prod_{1 \leq j \leq n} (1 + x_{j} z) . & by (10.1) \end{array}

Taking the logarithm yields

\begin{array}{l} \ln G (z) & = \ln \prod_{1 \leq j \leq n} (1 + x_{j} z) \\ = \sum_{1 \leq j \leq n} \ln (1 + x_{j} z) \\ = \sum_{1 \leq j \leq n} \sum_{k \geq 1} \frac{{(- 1)}^{k + 1}}{k} {(x_{j} z)}^{k} & by Eq. (24) \\ = \sum_{k \geq 1} \frac{{(- 1)}^{k + 1} \sum_{1 \leq j \leq n} x_{j}^{k} z^{k}}{k} \\ = \sum_{k \geq 1} \frac{{(- 1)}^{k + 1} S_{k} z^{k}}{k} . \end{array}

Finally,

\begin{array}{l} G (z) & = e^{\ln G (z)} \\ = \exp (\sum_{k \geq 1} \frac{{(- 1)}^{k + 1} S_{k} z^{k}}{k}) \\ = \prod_{k \geq 1} e^{{(- 1)}^{k + 1} S_{k} z^{k} ∕ k} \\ = \prod_{k \geq 1} \sum_{j \geq 0} \frac{1}{j!} {(\frac{{(- 1)}^{k + 1} S_{k} z^{k}}{k})}^{j} & by Eq. (22) \\ = \prod_{k \geq 1} \sum_{j \geq 0} \frac{{({(- 1)}^{k + 1} S_{k})}^{j} {(z^{k})}^{j}}{k^{j} j!} \\ = \prod_{j \geq 1} \sum_{k \geq 0} \frac{{({(- 1)}^{j + 1} S_{j})}^{k}}{j^{k} k!} {(z^{j})}^{k} \\ = \prod_{j \geq 1} \sum_{k \geq 0} \frac{{({(- 1)}^{j + 1} S_{j})}^{k}}{j^{k} k!} z^{j k} \\ = \prod_{j \geq 1} \sum_{k ∕ j \geq 0} \frac{{({(- 1)}^{j + 1} S_{j})}^{k ∕ j}}{j^{k ∕ j} (k ∕ j)!} z^{k} \\ \begin{aligned} = \sum_{n \geq 0} z^{n} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + k_{2} + \dots + k_{n} = n \end{array}} \frac{{({(- 1)}^{1 + 1} S_{1})}^{k_{1} ∕ 1}}{1^{k_{1} ∕ 1} (k_{1} ∕ 1)!} \frac{{({(- 1)}^{2 + 1} S_{2})}^{k_{2} ∕ 2}}{2^{k_{2} ∕ 2} (k_{2} ∕ 2)!} \\ \dots \frac{{({(- 1)}^{n + 1} S_{n})}^{k_{n} ∕ n}}{n^{k_{n} ∕ n} (k_{n} ∕ n)!} \end{aligned} & by Eq. (9) \\ = \sum_{n \geq 0} z^{n} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + 2 k_{2} + \dots + n k_{n} = n \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \frac{{(- S_{2})}^{k_{2}}}{2^{k_{2}} k_{2}!} \dots \frac{{({(- 1)}^{n + 1} S_{n})}^{k_{n}}}{n^{k_{n}} k_{n}!}, \end{array}

and hence

\begin{array}{l} G (z) & = \sum_{k \geq 0} e_{k} z^{k} \\ = \sum_{k \geq 0} \sum_{1 \leq j_{1} < \dots < j_{m} \leq n} x_{j_{1}} \dots x_{j_{m}} z^{k} \\ = \sum_{n \geq 0} z^{n} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{n} \geq 0 \\ k_{1} + 2 k_{2} + \dots + n k_{n} = n \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \frac{{(- S_{2})}^{k_{2}}}{2^{k_{2}} k_{2}!} \dots \frac{{({(- 1)}^{n + 1} S_{n})}^{k_{n}}}{n^{k_{n}} k_{n}!} . \end{array}

We then have

\begin{array}{l} e_{1} & = \sum_{\begin{array}{c} k_{1} \geq 0 \\ k_{1} = 1 \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \\ = \frac{S_{1}^{1}}{1^{1} 1!} \\ = S_{1}, \end{array}

\begin{array}{l} e_{2} & = \sum_{\begin{array}{c} k_{1}, k_{2} \geq 0 \\ k_{1} + 2 k_{2} = 2 \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \frac{{(- S_{2})}^{k_{2}}}{2^{k_{2}} k_{2}!} \\ = \frac{S_{1}^{2}}{1^{2} 2!} \frac{{(- S_{2})}^{0}}{2^{0} 0!} + \frac{S_{1}^{0}}{1^{0} 0!} \frac{{(- S_{2})}^{1}}{2^{1} 1!} \\ = \frac{S_{1}^{2}}{2} + \frac{- S_{2}}{2} \\ = \frac{1}{2} S_{1}^{2} - \frac{1}{2} S_{2}, \end{array}

\begin{array}{l} e_{3} & = \sum_{\begin{array}{c} k_{1}, k_{2}, k_{3} \geq 0 \\ k_{1} + 2 k_{2} + 3 k_{3} = 3 \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \frac{{(- S_{2})}^{k_{2}}}{2^{k_{2}} k_{2}!} \frac{S_{3}^{k_{3}}}{3^{k_{3}} k_{3}!} \\ = \frac{S_{1}^{3}}{1^{3} 3!} \frac{{(- S_{2})}^{0}}{2^{0} 0!} \frac{S_{3}^{0}}{3^{0} 0!} + \frac{S_{1}^{1}}{1^{1} 1!} \frac{{(- S_{2})}^{1}}{2^{1} 1!} \frac{S_{3}^{0}}{3^{0} 0!} + \frac{S_{1}^{0}}{1^{0} 0!} \frac{{(- S_{2})}^{0}}{2^{0} 0!} \frac{S_{3}^{1}}{3^{1} 1!} \\ = \frac{S_{1}^{3}}{3!} + S_{1} \frac{- S_{2}}{2} + \frac{S_{3}}{3} \\ = \frac{1}{6} S_{1}^{3} - \frac{1}{2} S_{1} S_{2} + \frac{1}{3} S_{3}, \end{array}

and

\begin{array}{l} e_{4} & = \sum_{\begin{array}{c} k_{1}, k_{2}, k_{3}, k_{4} \geq 0 \\ k_{1} + 2 k_{2} + 3 k_{3} + 4 k_{4} = 4 \end{array}} \frac{S_{1}^{k_{1}}}{1^{k_{1}} k_{1}!} \frac{{(- S_{2})}^{k_{2}}}{2^{k_{2}} k_{2}!} \frac{S_{3}^{k_{3}}}{3^{k_{3}} k_{3}!} \frac{{(- S_{4})}^{k_{4}}}{4^{k_{4}} k_{4}!} \\ \begin{aligned} = \frac{S_{1}^{4}}{1^{4} 4!} \frac{{(- S_{2})}^{0}}{2^{0} 0!} \frac{S_{3}^{0}}{3^{0} 0!} \frac{{(- S_{4})}^{0}}{4^{0} 0!} + \frac{S_{1}^{2}}{1^{2} 2!} \frac{{(- S_{2})}^{1}}{2^{1} 1!} \frac{S_{3}^{0}}{3^{0} 0!} \frac{{(- S_{4})}^{0}}{4^{0} 0!} \\ + \frac{S_{1}^{1}}{1^{1} 1!} \frac{{(- S_{2})}^{0}}{2^{0} 0!} \frac{S_{3}^{1}}{3^{1} 1!} \frac{{(- S_{4})}^{0}}{4^{0} 0!} + \frac{S_{1}^{0}}{1^{0} 0!} \frac{{(- S_{2})}^{2}}{2^{2} 2!} \frac{S_{3}^{0}}{3^{0} 0!} \frac{{(- S_{4})}^{0}}{4^{0} 0!} + \frac{S_{1}^{0}}{1^{0} 0!} \frac{{(- S_{2})}^{0}}{2^{0} 0!} \frac{S_{3}^{0}}{3^{0} 0!} \frac{{(- S_{4})}^{1}}{4^{1} 1!} \end{aligned} \\ = \frac{S_{1}^{4}}{4!} + \frac{S_{1}^{2}}{2} \frac{- S_{2}}{2} + S_{1} \frac{S_{3}}{3} + \frac{S_{2}^{2}}{4 \cdot 2!} + \frac{- S_{4}}{4} \\ = \frac{1}{24} S_{1}^{4} - \frac{1}{4} S_{1}^{2} S_{2} + \frac{1}{3} S_{1} S_{3} + \frac{1}{8} S_{2}^{2} - \frac{1}{4} S_{4} . \end{array}

______________________________________________________________________________________________________________________________

[Isaac Newton, Arithmetica Universalis (1707); D. J. Struik, Source Book in Mathematics (Harvard University Press, 1969), 94–95]

From Eq. (39),

h_{n} = \frac{1}{n} \sum_{1 \leq k \leq n} S_{k} h_{n - k}

for $n \geq 1$ ; or equivalently,

\begin{array}{l} h_{n} = \frac{1}{n} \sum_{1 \leq k \leq n} S_{k} h_{n - k} & \Leftrightarrow n h_{n} = \sum_{1 \leq k \leq n} S_{k} h_{n - k} \\ \Leftrightarrow n h_{n} = S_{n} h_{0} + \sum_{1 \leq k \leq n - 1} S_{k} h_{n - k} \\ \Leftrightarrow S_{n} h_{0} = n h_{n} - \sum_{1 \leq k \leq n - 1} S_{k} h_{n - k} \\ \Leftrightarrow S_{n} = n h_{n} - \sum_{1 \leq k \leq n - 1} S_{k} h_{n - k} . \end{array}

Note that for $G (z) = \sum_{k \geq 0} h_{k} z^{k}$ ,

\begin{array}{l} \sum_{k \geq 1} \frac{S_{k} z^{k}}{k} & = \ln G (z) & by Eq. (37) \\ = \ln \sum_{k \geq 0} h_{k} z^{k} \\ = \ln (h_{0} z^{0} + \sum_{k \geq 1} h_{k} z^{k}) \\ = \ln (1 + \sum_{k \geq 1} h_{k} z^{k}) \\ = \sum_{m \geq 1} \frac{{(- 1)}^{m + 1}}{m} {(\sum_{k \geq 1} h_{k} z^{k})}^{m} & by Eq. (24) \\ = \sum_{k \geq 1} \frac{{(- 1)}^{k - 1}}{k} {(\sum_{m \geq 1} h_{m} z^{m})}^{k} . \end{array}

By the multinomial theorem¹ , Eqs. 1.2.6-(42) and 1.2.6-(41),

\begin{array}{l} \sum_{m \geq 1} \frac{S_{m} z^{m}}{m} \\ = \sum_{m \geq 1} \frac{{(- 1)}^{m + 1}}{m} {(\sum_{k \geq 1} h_{k} z^{k})}^{m} \\ = \sum_{m \geq 1} \frac{{(- 1)}^{m - 1}}{m} {(\sum_{1 \leq k \leq m} h_{k} z^{k})}^{m} \\ = \sum_{m \geq 1} \frac{{(- 1)}^{m - 1}}{m} {(\sum_{1 \leq k \leq m} h_{k} z^{k})}^{m} \\ = \sum_{m \geq 1} \frac{{(- 1)}^{m - 1}}{m} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{m} \geq 0 \\ k_{1} + k_{2} + \dots + k_{m} = m \end{array}} (\binom{m}{k_{1}, k_{2}, \dots, k_{m}}) \prod_{1 \leq j \leq m} {(h_{j} z^{j})}^{k_{j}} \\ = \sum_{m \geq 1} \frac{{(- 1)}^{m - 1}}{m} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{m} \geq 0 \\ k_{1} + k_{2} + \dots + k_{m} = m \end{array}} \frac{m!}{k_{1}! k_{2}! \dots k_{m}!} \prod_{1 \leq j \leq m} {(h_{j} z^{j})}^{k_{j}} \\ = \sum_{m \geq 1} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{m} \geq 0 \\ k_{1} + k_{2} + \dots + k_{m} = m \end{array}} \frac{{(- 1)}^{m - 1} (m - 1)!}{k_{1}! k_{2}! \dots k_{m}!} \prod_{1 \leq j \leq m} h_{j}^{k_{j}} z^{j k_{j}} \\ \begin{aligned} = \sum_{m \geq 1} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{m} \geq 0 \\ k_{1} + k_{2} + \dots + k_{m} = m \end{array}} \frac{{(- 1)}^{k_{1} + k_{2} + \dots + k_{m} - 1} (k_{1} + k_{2} + \dots + k_{m} - 1)!}{k_{1}! k_{2}! \dots k_{m}!} \\ h_{1}^{k_{1}} h_{2}^{k_{2}} \dots h_{m}^{k_{m}} z^{k_{1} + 2 k_{2} + \dots + m k_{m}} \end{aligned} \\ = \sum_{m \geq 1} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{m} \geq 0 \\ k_{1} + 2 k_{2} + \dots + m k_{m} = m \end{array}} \frac{{(- 1)}^{k_{1} + k_{2} + \dots + k_{m} - 1} (k_{1} + k_{2} + \dots + k_{m} - 1)!}{k_{1}! k_{2}! \dots k_{m}!} h_{1}^{k_{1}} h_{2}^{k_{2}} \dots h_{m}^{k_{m}} z^{m} . \end{array}

Hence,

\begin{array}{l} \sum_{m \geq 1} S_{m} z^{m} \\ = \sum_{m \geq 1} \sum_{\begin{array}{c} k_{1}, k_{2}, \dots, k_{m} \geq 0 \\ k_{1} + 2 k_{2} + \dots + m k_{m} = m \end{array}} \frac{{(- 1)}^{k_{1} + k_{2} + \dots + k_{m} - 1} m (k_{1} + k_{2} + \dots + k_{m} - 1)!}{k_{1}! k_{2}! \dots k_{m}!} h_{1}^{k_{1}} h_{2}^{k_{2}} \dots h_{m}^{k_{m}} z^{m} . \end{array}

That is, the coeﬃcient of $h_{1}^{k_{1}} h_{2}^{k_{2}} \dots h_{m}^{k_{m}}$ in this representation of $S_{m}$ , when $k_{1} + 2 k_{2} + \dots m k_{m} = m$ is

{(- 1)}^{k_{1} + k_{2} + \dots + k_{m} - 1} m (k_{1} + k_{2} + \dots + k_{m} - 1)! ∕ k_{1}! k_{2}! \dots k_{m}! .

______________________________________________________________________________________________________________________________

[Albert Girard, Invention Nouvelle en Algébre (Amsterdam: 1629)]

Given a sequence $⟨ a_{m, n} ⟩ = ⟨ (\binom{n}{m}) ⟩$ for $m, n \geq 0$ , we ﬁnd the generating function to be

\begin{array}{l} \sum_{m, n \geq 0} a_{m, n} w^{m} z^{n} & = \sum_{m, n \geq 0} (\binom{n}{m}) w^{m} z^{n} \\ = \sum_{n \geq 0} \sum_{m \geq 0} (\binom{n}{m}) w^{m} z^{n} \\ = \sum_{n \geq 0} {(1 + w)}^{n} z^{n} & by Eq. (19) \\ = \sum_{n \geq 0} {(z + w z)}^{n} \\ = 1 ∕ (1 - (z + w z)) & by Eq. (5) \\ = 1 ∕ (1 - z - w z) . \end{array}

Given the step function $f (x) = \sum_{0 \leq k \leq x} a_{k}$ and generating function $G (z)$ of $⟨ a_{n} ⟩$ as

\begin{array}{l} G (z) & = \sum_{n \geq 0} a_{n} z^{n}, \end{array}

we have that

\begin{array}{l} L f (s) & = \int_{0}^{\infty} e^{- s t} f (t) d t \\ = \sum_{n \geq 0} \int_{n}^{n + 1} e^{- s t} f (t) d t \\ = \sum_{n \geq 0} \int_{n}^{n + 1} f (t) e^{- s t} d t \\ = \sum_{n \geq 0} \int_{n}^{n + 1} \sum_{0 \leq k \leq n} a_{k} e^{- s t} d t \\ = \sum_{n \geq 0} \sum_{0 \leq k \leq n} \int_{n}^{n + 1} a_{k} e^{- s t} d t \\ = \sum_{n \geq 0} \sum_{0 \leq k \leq n} a_{k} \int_{n}^{n + 1} e^{- s t} d t \\ = \sum_{n \geq 0} f (n) \int_{n}^{n + 1} e^{- s t} d t \\ = \sum_{n \geq 0} f (n) {\frac{- 1}{s} e^{- s t}|}_{n}^{n + 1} \\ = \sum_{n \geq 0} f (n) (\frac{- 1}{s} e^{- s (n + 1)} - \frac{- 1}{s} e^{- s n}) \\ = \sum_{n \geq 0} f (n) (e^{- s n} - e^{- s (n + 1)}) ∕ s \\ = \sum_{n \geq 0} f (n) e^{- s n} ∕ s - \sum_{n \geq 0} f (n) e^{- s (n + 1)} ∕ s \\ = \sum_{n \geq 0} f (n) e^{- s n} ∕ s - \sum_{n \geq 1} f (n - 1) e^{- s n} ∕ s \\ = \sum_{n \geq 0} f (n) e^{- s n} ∕ s - \sum_{n \geq 0} f (n - 1) e^{- s n} ∕ s \\ = \sum_{n \geq 0} (f (n) - f (n - 1)) e^{- s n} ∕ s \\ = \sum_{n \geq 0} a_{n} e^{- s n} ∕ s \\ = \sum_{n \geq 0} a_{n} {(e^{- s})}^{n} ∕ s \\ = G (e^{- s}) ∕ s . \end{array}

We may prove Eq. (13).

Proposition. $\sum_{\begin{array}{c} n > 0 \\ n mod m = r \end{array}} a_{n} z^{n} = \frac{1}{m} \sum_{0 \leq k < m} ω^{- k r} G (ω^{k} z)$ .

Proof. Let $m$ and $r$ be arbitrary integers such that $0 \leq r < m$ , and let $ω = e^{2 π i ∕ m} = \cos (2 π ∕ m) + i \sin (2 π ∕ m)$ . If $G (z)$ is the generating function for $⟨ a_{n} ⟩ = a_{0}, a_{1}, \dots$ , we must show that

\sum_{\begin{array}{c} n > 0 \\ n mod m = r \end{array}} a_{n} z^{n} = \frac{1}{m} \sum_{0 \leq k < m} ω^{- k r} G (ω^{k} z) .

But given $ω = e^{2 π i ∕ m}$ and the sum of the geometric progression for $n$ restricted such that $n mod m = r$ ,

\begin{array}{l} \sum_{\begin{array}{c} n > 0 \\ n mod m = r \end{array}} a_{n} z^{n} & = \sum_{\begin{array}{c} n > 0 \\ n - r \equiv 0 (mod m) \end{array}} a_{n} z^{n} \\ = \sum_{n > 0} [n - r \equiv 0 (mod m)] a_{n} z^{n} \\ = \frac{m}{m} \sum_{n > 0} [n - r \equiv 0 (mod m)] a_{n} z^{n} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} [n - r \equiv 0 (mod m)] m \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} [n - r \equiv 0 (mod m)] \sum_{0 \leq k < m} 1^{k} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} \sum_{0 \leq k < m} {(1^{(n - r) ∕ m})}^{k} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} \sum_{0 \leq k < m} {({(- 1)}^{2 (n - r) ∕ m})}^{k} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} \sum_{0 \leq k < m} {(e^{2 π i (n - r) ∕ m})}^{k} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} \sum_{0 \leq k < m} {(ω^{n - r})}^{k} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} \sum_{0 \leq k < m} ω^{k (n - r)} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} \sum_{0 \leq k < m} ω^{k (n - r)} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} \sum_{0 \leq k < m} ω^{k n - k r} \\ = \frac{1}{m} \sum_{n > 0} a_{n} z^{n} \sum_{0 \leq k < m} ω^{- k r} ω^{k n} \\ = \frac{1}{m} \sum_{0 \leq k < m} ω^{- k r} \sum_{n > 0} a_{n} ω^{k n} z^{n} \\ = \frac{1}{m} \sum_{0 \leq k < m} ω^{- k r} \sum_{n > 0} a_{n} {(ω^{k} z)}^{n} \\ = \frac{1}{m} \sum_{0 \leq k < m} ω^{- k r} G (ω^{k} z), \end{array}

and hence the result. □

______________________________________________________________________________________________________________________________

[exercise 1.2.6-38]

In the case that $n > 0$ , we have that

\begin{array}{l} G_{n} (z) & = \sum_{0 \leq k \leq n} (\binom{n - k}{k}) z^{k} \\ = \sum_{0 \leq k \leq n} ((\binom{n - k - 1}{k}) + (\binom{n - k - 1}{k - 1})) z^{k} & by 1.2.6-(9) \\ = \sum_{0 \leq k \leq n} (\binom{n - k - 1}{k}) z^{k} + \sum_{0 \leq k \leq n} (\binom{n - k - 1}{k - 1}) z^{k} \\ \begin{aligned} = (\binom{n - n - 1}{n}) z^{n} + (\binom{n - n - 1}{n - 1}) z^{n} \\ + \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k}) z^{k} + \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k - 1}) z^{k} \end{aligned} \\ \begin{aligned} = 0 + 0 \\ + \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k}) z^{k} + \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k - 1}) z^{k} \end{aligned} \\ = \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k}) z^{k} + \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k - 1}) z^{k} \\ = \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k}) z^{k} + \sum_{1 \leq k \leq n - 1} (\binom{n - k - 1}{k - 1}) z^{k} + (\binom{n - 1}{- 1}) z^{0} \\ = \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k}) z^{k} + \sum_{1 \leq k \leq n - 1} (\binom{n - k - 1}{k - 1}) z^{k} + 0 \\ = \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k}) z^{k} + \sum_{1 \leq k \leq n - 1} (\binom{n - k - 1}{k - 1}) z^{k} \\ = \sum_{0 \leq k \leq n - 1} (\binom{n - k - 1}{k}) z^{k} + \sum_{0 \leq k \leq n - 2} (\binom{n - k - 2}{k}) z^{k + 1} \\ = \sum_{0 \leq k \leq n - 1} (\binom{(n - 1) - k}{k}) z^{k} + z \sum_{0 \leq k \leq n - 2} (\binom{(n - 2) - k}{k}) z^{k} \\ = \sum_{0 \leq k \leq n - 1} (\binom{(n - 1) - k}{k}) z^{k} + z \sum_{0 \leq k \leq n - 2} (\binom{(n - 2) - k}{k}) z^{k} + δ n, 0; \\ = G_{n - 1} (z) + z G_{n - 2} (z) + δ_{n, 0}; \end{array}

and in the case that $n = 0$ , we have that

\begin{array}{l} G_{n} (z) & = \sum_{0 \leq k \leq 0} (\binom{0 - k}{k}) z^{k} \\ = (\binom{0 - 0}{0}) z^{0} \\ = (\binom{0}{0}) z^{0} \\ = 1 \\ = δ n, 0 \\ = \sum_{0 \leq k \leq n - 1} (\binom{(n - 1) - k}{k}) z^{k} + z \sum_{0 \leq k \leq n - 2} (\binom{(n - 2) - k}{k}) z^{k} + δ n, 0 \\ = G_{n - 1} (z) + z G_{n - 2} (z) + δ_{n, 0} . \end{array}

That is, in either case,

G_{n} (z) = G_{n - 1} (z) + z G_{n - 2} (z) + δ_{n, 0} .

Then,

\begin{array}{l} H (w) & = \sum_{n \geq 0} G_{n} (z) w^{n} \\ = G_{0} (z) + G_{1} (z) w + G_{2} (z) w^{2} + \dots, \\ w H (w) & = G_{0} (z) w + G_{1} (z) w^{2} + G_{2} (z) w^{3} + \dots, \\ z w^{2} H (w) & = z G_{0} (z) w^{2} + z G_{1} (z) w^{3} + z G_{2} (z) w^{4} + \dots; \end{array}

so that

\begin{array}{l} H (w) - w H (w) - z w^{2} H (w) \\ = H (w) (1 - w - z w^{2}) \\ = G_{0} (z) + (G_{1} (z) - G_{0} (z)) w + (G_{2} (z) - (G_{1} (z) + z G_{0} (z))) w^{2} + \dots \\ = G_{0} (z) + (G_{1} (z) - G_{0} (z)) w + (G_{2} (z) - (G_{1} (z) + z G_{0} (z) + δ_{2, 0})) w^{2} + \dots \\ = G_{0} (z) + (G_{1} (z) - G_{0} (z)) w + (G_{2} (z) - G_{2} (z)) w^{2} + \dots \\ = G_{0} (z) + (G_{1} (z) - G_{0} (z)) w \\ = G_{0} (z) + G_{1} (z) w - G_{0} (z) w \\ = G_{0} (z) + (G_{0} (z) + z G_{- 1} (z) + δ_{1, 0}) w - G_{0} (z) w \\ = G_{0} (z) + G_{0} (z) w - G_{0} (z) w \\ = G_{0} (z), \\ = 1, \end{array}

or equivalently, so that

H (w) = 1 ∕ (1 - w - z w^{2}) .

Then, if $z \neq - \frac{1}{4}$ ,

\begin{array}{l} H (w) \\ = \sum_{n \geq 0} G_{n} (z) w^{n} \\ = 1 ∕ (1 - w - z w^{2}) \\ = \frac{1}{1 - \frac{2}{2} w - \frac{\sqrt{1 + 4 z}}{2} w + \frac{\sqrt{1 + 4 z}}{2} w - \frac{4 z}{4} w^{2}} \\ = \frac{1}{1 - \frac{1}{2} w - \frac{\sqrt{1 + 4 z}}{2} w - \frac{1}{2} w + \frac{\sqrt{1 + 4 z}}{2} w + \frac{1 - 1 - 4 z}{4} w^{2}} \\ = \frac{1}{1 - \frac{1}{2} (1 - \sqrt{1 + 4 z}) w - \frac{1}{2} (1 + \sqrt{1 + 4 z}) w + \frac{1}{4} (1 + \sqrt{1 + 4 z} - \sqrt{1 + 4 z} - (1 + 4 z)) w^{2}} \\ = \frac{1}{1 - \frac{1}{2} (1 - \sqrt{1 + 4 z}) w - \frac{1}{2} (1 + \sqrt{1 + 4 z}) w + \frac{1}{4} (1 + \sqrt{1 + 4 z}) (1 - \sqrt{1 + 4 z}) w^{2}} \\ = \frac{4 x^{2}}{4 x^{2} - 2 x^{2} (1 - \sqrt{1 + 4 z}) w - 2 x^{2} (1 + \sqrt{1 + 4 z}) w + x^{2} (1 + \sqrt{1 + 4 z}) (1 - \sqrt{1 + 4 z}) w^{2}} \\ \begin{aligned} = \frac{(1 + \sqrt{1 + 4 z}) (2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 - \sqrt{1 + 4 z}) w)}{(2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 + \sqrt{1 + 4 z}) w) (2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 - \sqrt{1 + 4 z}) w)} \\ - \frac{(1 - \sqrt{1 + 4 z}) (2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 + \sqrt{1 + 4 z}) w)}{(2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 + \sqrt{1 + 4 z}) w) (2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 - \sqrt{1 + 4 z}) w)} \end{aligned} \\ = \frac{1 + \sqrt{1 + 4 z}}{2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 + \sqrt{1 + 4 z}) w} - \frac{1 - \sqrt{1 + 4 z}}{2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 - \sqrt{1 + 4 z}) w} \\ = \frac{1 + \sqrt{1 + 4 z}}{2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 + \sqrt{1 + 4 z}) w} - \frac{1 - \sqrt{1 + 4 z}}{2 \sqrt{1 + 4 z} - \sqrt{1 + 4 z} (1 - \sqrt{1 + 4 z}) w} \\ \begin{aligned} = \frac{1}{\sqrt{1 + 4 z}} (\frac{1 + \sqrt{1 + 4 z}}{2}) \frac{1}{1 - \frac{1 + \sqrt{1 + 4 z}}{2} w} - \frac{1}{\sqrt{1 + 4 z}} (\frac{1 - \sqrt{1 + 4 z}}{2}) \frac{1}{1 - \frac{1 - \sqrt{1 + 4 z}}{2} w} \end{aligned} \\ \begin{aligned} = \frac{1}{\sqrt{1 + 4 z}} (\frac{1 + \sqrt{1 + 4 z}}{2}) \sum_{n \geq 0} {(\frac{1 + \sqrt{1 + 4 z}}{2})}^{n} w^{n} \\ - \frac{1}{\sqrt{1 + 4 z}} (\frac{1 - \sqrt{1 + 4 z}}{2}) \sum_{n \geq 0} {(\frac{1 - \sqrt{1 + 4 z}}{2})}^{n} w^{n} \end{aligned} & by Eq. (5) \\ = \frac{1}{\sqrt{1 + 4 z}} (\sum_{n \geq 0} {(\frac{1 + \sqrt{1 + 4 z}}{2})}^{n + 1} w^{n} - \sum_{n \geq 0} {(\frac{1 - \sqrt{1 + 4 z}}{2})}^{n + 1} w^{n}) \\ = \sum_{n \geq 0} \frac{1}{\sqrt{1 + 4 z}} ({(\frac{1 + \sqrt{1 + 4 z}}{2})}^{n + 1} - {(\frac{1 - \sqrt{1 + 4 z}}{2})}^{n + 1}) w^{n} \end{array}

if and only if

G_{n} (z) = ({(\frac{1 + \sqrt{1 + 4 z}}{2})}^{n + 1} - {(\frac{1 - \sqrt{1 + 4 z}}{2})}^{n + 1}) / \sqrt{1 + 4 z};

and if $z = - \frac{1}{4}$ ,

\begin{array}{l} \sum_{n \geq 0} G_{n} (- \frac{1}{4}) w^{n} & = 1 / (1 - w + \frac{1}{4} w^{2}) \\ = \frac{1}{\frac{1}{4} w^{2} - \frac{1}{2} w - \frac{1}{2} w + 1} \\ = \frac{1}{{(\frac{w}{2} - 1)}^{2}} \\ = \frac{1}{{(1 - \frac{w}{2})}^{2}} \\ = {(\frac{1}{1 - \frac{w}{2}})}^{2} \\ = {(\sum_{n \geq 0} \frac{1}{2^{n}} w^{n})}^{2} & by Eq. (5) \\ = \sum_{n \geq 0} \sum_{0 \leq k \leq n} \frac{1}{2^{k}} w^{k} \frac{1}{2^{n - k}} w^{n - k} & by Eq. (6) \\ = \sum_{n \geq 0} \sum_{0 \leq k \leq n} \frac{1}{2^{n}} w^{n} \\ = \sum_{n \geq 0} \frac{1}{2^{n}} w^{n} \sum_{0 \leq k \leq n} 1 \\ = \sum_{n \geq 0} \frac{1}{2^{n}} w^{n} (n + 1) \\ = \sum_{n \geq 0} \frac{(n + 1)}{2^{n}} w^{n}, \end{array}

so that for $n \geq 0$ ,

G_{n} (- \frac{1}{4}) = (n + 1) ∕ 2^{n} .

Hence, for $n \geq 0$ ,

G_{n} (z) = \{\begin{matrix} ({(\frac{1 + \sqrt{1 + 4 z}}{2})}^{n + 1} - {(\frac{1 - \sqrt{1 + 4 z}}{2})}^{n + 1}) / \sqrt{1 + 4 z} & if z \neq - \frac{1}{4} \\ (n + 1) ∕ 2^{n} & otherwise. \end{matrix}

We want to ﬁnd $a_{n, k, r}$ , the number of ways to choose $k$ out of $n$ objects, subject to the condition that each object may be chosen at most $r$ times.

Letting $z$ be the formal parameter of our generating function $G_{n, r} (z)$ , the number of ways to choose an object zero times is $[z^{0}] G_{1, 0} (z) = 1$ ; the number of ways to choose an object one time is $[z^{1}] G_{1, 1} = 1$ ; and the number of ways to choose an object $r$ times is $[z^{r}] G_{1, r} = 1$ . That is, $G_{1, r} (z) = 1 + z + \dots + z^{r}$ . For $n$ classes of objects, this is then given by the generating function

G_{n, r} (z) = {(1 + z + \dots + z^{r})}^{n} = {(\frac{1 - z^{r + 1}}{1 - z})}^{n} .

In the case that $r = 1$ , we have that

G_{n, 1} (z) = {(1 + z)}^{n} = \sum_{k} (\binom{n}{k}) z^{k},

or equivalently that $a_{n, k, 1} = (\binom{n}{k})$ ; and in the case that $r \geq k$ ,

\begin{array}{l} G_{n, r} (z) & = {(1 + z + \dots)}^{n} \\ = {(\frac{1}{1 - z})}^{n} \\ = {(1 - z)}^{- n} \\ = \sum_{k} (\binom{- n}{k}) {(- z)}^{k} \\ = \sum_{k} {(- 1)}^{k} (\binom{k - (n + k - 1) - 1}{k}) z^{k} \\ = \sum_{k} (\binom{n + k - 1}{k}) z^{k} & by Eq. 1.2.6-(17) \end{array}

as shown in exercise 1.2.6-60, or equivalently that $a_{n, k, r} = (\binom{n + k - 1}{k})$ for $r \geq k$ , $r \to \infty$ .

________________________________________________________________________________

[exercise 1.2.6-60]

We have

\begin{array}{l} 1 ∕ {(1 - z)}^{w} & = 1 ∕ {(1 - z)}^{(w - 1) + 1} \\ = \sum_{k} (\binom{- (w - 1) - 1}{k}) {(- z)}^{k} & by Eq. (20) \\ = \sum_{k} (\binom{- w}{k}) {(- z)}^{k} \\ = \sum_{k} {(- 1)}^{k} (\binom{- w}{k}) z^{k} \\ = \sum_{k} {(- 1)}^{k} ({(- w)}^{\underset{̲}{k}} ∕ k!) z^{k} & by Eq. 1.2.6-(3) \\ = \sum_{k} {(- 1)}^{k} {(- w)}^{\underset{̲}{k}} z^{k} ∕ k! \\ = \sum_{k} w^{\bar{k}} z^{k} ∕ k! & by Eq. 1.2.5-(20) \\ = \sum_{k} \prod_{0 \leq n \leq k - 1} (w + n) z^{k} ∕ k! & by Eq. 1.2.5-(19) \\ = \sum_{k} \sum_{n} [\binom{k}{n}] w^{n} z^{k} ∕ k! & by Eq. (27) \\ = \sum_{k, n} [\binom{k}{n}] w^{n} z^{k} ∕ k! . \end{array}

We may ﬁnd simple formulas for the sums, given positive integers $n$ and $r$ .

a)

For

\sum_{1 \leq k_{1} < k_{2} < \dots < k_{r} \leq n} k_{1} k_{2} \dots k_{r}

we have

\begin{array}{l} G_{n} (z) & = \sum_{j \geq 0} \sum_{1 \leq k_{1} < \dots < k_{r} \leq n} k_{1} \dots k_{r} z^{j} \\ = \prod_{1 \leq j \leq n} (1 + j z) & by exercise 10 \\ = z^{n + 1} \prod_{0 \leq j \leq (n + 1) - 1} (\frac{1}{z} + j) \\ = z^{n + 1} \sum_{k} [\binom{n + 1}{k}] {(\frac{1}{z})}^{k} & by Eq. (27) \\ = z^{n + 1} \sum_{k} [\binom{n + 1}{k}] z^{- k} \\ = \sum_{k} [\binom{n + 1}{k}] z^{n + 1 - k} \\ = \sum_{r} [\binom{n + 1}{n + 1 - r}] z^{r}, \end{array}

so that the formula is given by

\sum_{1 \leq k_{1} < k_{2} < \dots < k_{r} \leq n} k_{1} k_{2} \dots k_{r} = [\binom{n + 1}{n + 1 - r}] .

b)

For

\sum_{1 \leq k_{1} \leq k_{2} \leq \dots \leq k_{r} \leq n} k_{1} k_{2} \dots k_{r}

we have

\begin{array}{l} G_{n} (z) & = \sum_{j \geq 0} \sum_{1 \leq k_{1} \leq \dots \leq k_{r} \leq n} k_{1} \dots k_{r} z^{j} \\ = \prod_{1 \leq j \leq n} \frac{1}{1 - j z} & by exercise 7 \\ = \frac{1}{\prod_{1 \leq j \leq n} (1 - j z)} \\ = z^{- n} \frac{z^{n}}{\prod_{1 \leq j \leq n} (1 - j z)} \\ = z^{- n} \sum_{k} \{\binom{k}{n}\} z^{k} & by Eq. (28) \\ = \sum_{k} \{\binom{k}{n}\} z^{k - n} \\ = \sum_{r} \{\binom{n + r}{n}\} z^{r}, \end{array}

so that the formula is given by

\sum_{1 \leq k_{1} \leq k_{2} \leq \dots \leq k_{r} \leq n} k_{1} k_{2} \dots k_{r} = \{\binom{n + r}{n}\} .

Proposition. $H_{p ∕ q}$ has the value

H_{p ∕ q} = \frac{q}{p} - \frac{π}{2} \cot \frac{p}{q} π - \ln 2 q + 2 \sum_{0 < k < q ∕ 2} \cos \frac{2 p k}{q} π \cdot \ln \sin \frac{k}{q} π,

when $p$ and $q$ are integers with $0 < p < q$ .

Proof. As a preliminary identity, observe that

\begin{array}{l} \ln (1 - e^{i 𝜃}) & = \ln (2 e^{i (𝜃 - π) ∕ 2} \frac{e^{i 𝜃 ∕ 2} - e^{- i 𝜃 ∕ 2}}{2 i}) \\ = \ln 2 + \ln (e^{i (𝜃 - π) ∕ 2}) + \ln \frac{e^{i 𝜃 ∕ 2} - e^{- i 𝜃 ∕ 2}}{2 i} \\ = \ln 2 + \frac{1}{2} i (𝜃 - π) + \ln \frac{e^{i 𝜃 ∕ 2} - e^{- i 𝜃 ∕ 2}}{2 i} \\ = \ln 2 + \frac{1}{2} i (𝜃 - π) + \ln \sin \frac{𝜃}{2} . & (19.1) \end{array}

Let $p, q$ be artibtrary integers such that $0 < p < q$ , and deﬁne $H_{x}$ as

H_{x} = \sum_{n \geq 1} (\frac{1}{n} - \frac{1}{n + x})

for any nonnegative rational number $x$ . We must show that

H_{p ∕ q} = \frac{q}{p} - \frac{π}{2} \cot \frac{p}{q} π - \ln 2 q + 2 \sum_{0 < k < q ∕ 2} \cos \frac{2 p k}{q} π \cdot \ln \sin \frac{k}{q} π .

We have

H_{p ∕ q} = \sum_{n \geq 1} (\frac{1}{n} - \frac{1}{n + p ∕ q}) .

By Abel’s limit theorem,

\sum_{n \geq 1} (\frac{1}{n} - \frac{1}{n + p ∕ q}) = \lim_{x \to 1 -} \sum_{n \geq 1} (\frac{1}{n} - \frac{1}{n + p ∕ q}) x^{p + n q} .

Then,

\begin{array}{l} \lim_{x \to 1 -} \sum_{n \geq 1} (\frac{1}{n} - \frac{1}{n + p ∕ q}) x^{p + n q} \\ = \lim_{x \to 1 -} (\sum_{n \geq 1} \frac{1}{n} x^{p + n q} - \sum_{n \geq 1} \frac{1}{n + p ∕ q} x^{p + n q}) . \end{array}

For the left sum,

\begin{array}{l} \sum_{n \geq 1} \frac{1}{n} x^{p + n q} \\ = x^{p} \sum_{n \geq 1} \frac{1}{n} {(x^{q})}^{n} \\ = - x^{p} \sum_{n \geq 1} \frac{{(- 1)}^{2 n + 1}}{n} {(x^{q})}^{n} \\ = - x^{p} \sum_{n \geq 1} \frac{{(- 1)}^{n + 1}}{n} {(- x^{q})}^{n} \\ = - x^{p} \ln (1 - x^{q}) . & by Eq. (24) \end{array}

For the right sum with $ω = e^{2 π i ∕ q}$ ,

\begin{array}{l} - \sum_{n \geq 1} \frac{1}{n + p ∕ q} x^{p + n q} \\ = - \sum_{\begin{array}{c} n > 0 \\ p + n q mod q = p \end{array}} \frac{q}{p + n q} x^{p + n q} \\ = \frac{q}{p} x^{p} - \sum_{\begin{array}{c} n \geq 0 \\ p + n q mod q = p \end{array}} \frac{q}{p + n q} x^{p + n q} \\ = \frac{q}{p} x^{p} - \frac{1}{q} \sum_{0 \leq k < q} ω^{- k p} \sum_{n \geq 1} \frac{q}{n} ω^{k n} x^{n} & by Eq. (13) \\ = \frac{q}{p} x^{p} - \sum_{0 \leq k < q} ω^{- k p} \sum_{n \geq 1} \frac{1}{n} {(ω^{k} x)}^{n} \\ = \frac{q}{p} x^{p} + \sum_{0 \leq k < q} ω^{- k p} \sum_{n \geq 1} \frac{{(- 1)}^{2 n + 1}}{n} {(ω^{k} x)}^{n} \\ = \frac{q}{p} x^{p} + \sum_{0 \leq k < q} ω^{- k p} \sum_{n \geq 1} \frac{{(- 1)}^{n + 1}}{n} {(- ω^{k} x)}^{n} \\ = \frac{q}{p} x^{p} + \sum_{0 \leq k < q} ω^{- k p} \ln (1 - ω^{k} x) . & by Eq. (24) \end{array}

That is,

H_{p ∕ q} = \lim_{x \to 1 -} (\sum_{0 \leq k < q} ω^{- k p} \ln (1 - ω^{k} x) - x^{p} \ln (1 - x^{q}) + \frac{q}{p} x^{p}) .

Continuing in the limit as $x \to 1 -$ ,

\begin{array}{l} \sum_{0 \leq k < q} ω^{- k p} \ln (1 - ω^{k} x) - x^{p} \ln (1 - x^{q}) + \frac{q}{p} x^{p} \\ = \sum_{1 \leq k < q} ω^{- k p} \ln (1 - ω^{k} x) + \ln (1 - x) - x^{p} \ln (1 - x^{q}) + \frac{q}{p} x^{p} \\ = \sum_{1 \leq k < q} ω^{- k p} \ln (1 - ω^{k} x) + \ln (1 - x) + \frac{q}{p} x^{p} - x^{p} \ln (1 - x^{q}) + x^{p} \ln (1 - x) - x^{p} \ln (1 - x) \\ = \sum_{1 \leq k < q} ω^{- k p} \ln (1 - ω^{k} x) + (1 - x^{p}) \ln (1 - x) + \frac{q}{p} x^{p} - x^{p} \ln \frac{1 - x^{q}}{1 - x} . (19.2) \end{array}

The limit of the ﬁrst term is

\begin{array}{l} \lim_{x \to 1 -} \sum_{1 \leq k < q} ω^{- k p} \ln (1 - ω^{k} x) \\ = \sum_{1 \leq k < q} ω^{- k p} \ln (1 - ω^{k}) \\ = \sum_{1 \leq k < q} ω^{- k p} (\ln 2 + \frac{1}{2} i (2 π k ∕ q - π) + \ln \sin \frac{2 π k ∕ q}{2}) & by (19.1) \\ = \sum_{1 \leq k < q} ω^{- k p} (\ln 2 + \frac{i π k}{q} - \frac{i π}{2} + \ln \sin \frac{k}{q} π) \\ = \sum_{1 \leq k < q} ω^{- k p} (\ln 2 + \frac{i π k}{q} - \frac{i π}{2}) + \sum_{1 \leq k < q} ω^{- k p} \ln \sin \frac{k}{q} π, \end{array}

and the limit of the remaining terms of (19.2) is

\lim_{x \to 1 -} (1 - x^{p}) \ln (1 - x) + \frac{q}{p} x^{p} - x^{p} \ln \frac{1 - x^{q}}{1 - x} = \frac{q}{p} - \ln q;

but

\begin{array}{l} \sum_{1 \leq k < q} ω^{- k p} (\ln 2 + \frac{i π k}{q} - \frac{i π}{2}) \\ = \sum_{1 \leq k < q} ω^{- k p} \ln 2 + \sum_{1 \leq k < q} ω^{- k p} \frac{i π k}{q} - \sum_{1 \leq k < q} ω^{- k p} \frac{i π}{2} \\ = \frac{\ln 2 (ω^{- p (q - 1)} - 1)}{ω^{p} - 1} + \sum_{1 \leq k < q} ω^{- k p} \frac{i π k}{q} - \sum_{1 \leq k < q} ω^{- k p} \frac{i π}{2} \\ = \frac{\ln 2 (ω^{- p (q - 1)} - 1)}{ω^{p} - 1} + \frac{i π ω^{- p (q - 1)} (q (- ω^{p}) + ω^{p q} + q - 1)}{q {(ω^{p} - 1)}^{2}} - \sum_{1 \leq k < q} ω^{- k p} \frac{i π}{2} \\ = \frac{\ln 2 (ω^{- p (q - 1)} - 1)}{ω^{p} - 1} + \frac{i π ω^{- p (q - 1)} (q (- ω^{p}) + ω^{p q} + q - 1)}{q {(ω^{p} - 1)}^{2}} - \frac{i π (ω^{- p (q - 1)} - 1)}{2 (ω^{p} - 1)} \\ = \frac{- \ln 2 (ω^{p} - 1)}{ω^{p} - 1} + \frac{i π ω^{- p (q - 1)} (q (- ω^{p}) + ω^{p q} + q - 1)}{q {(ω^{p} - 1)}^{2}} - \frac{i π (ω^{- p (q - 1)} - 1)}{2 (ω^{p} - 1)} \\ = - \ln 2 + \frac{i π ω^{- p (q - 1)} (q (- ω^{p}) + ω^{p q} + q - 1)}{q {(ω^{p} - 1)}^{2}} - \frac{i π (ω^{- p (q - 1)} - 1)}{2 (ω^{p} - 1)} \\ = - \ln 2 + \frac{i π ω^{- p (q - 1)} (q (- ω^{p}) + ω^{p q} + q - 1)}{q {(ω^{p} - 1)}^{2}} + \frac{i π (ω^{p} - 1)}{2 (ω^{p} - 1)} \\ = - \ln 2 + \frac{i π ω^{- p (q - 1)} (q (- ω^{p}) + ω^{p q} + q - 1)}{q {(ω^{p} - 1)}^{2}} + \frac{i π}{2} \\ = - \ln 2 + \frac{i π}{2} + \frac{i π ω^{- p (q - 1)} (q (- ω^{p}) + ω^{p q} + q - 1)}{q {(ω^{p} - 1)}^{2}} \\ = - \ln 2 + \frac{i π}{2} + \frac{i π ω^{- p (q - 1)} (q (- ω^{p}) + q)}{q {(ω^{p} - 1)}^{2}} \\ = - \ln 2 + \frac{i π}{2} + \frac{i π ω^{- p (q - 1)} (- ω^{p} + 1)}{{(ω^{p} - 1)}^{2}} \\ = - \ln 2 + \frac{i π}{2} - \frac{i π ω^{p} (ω^{p} - 1)}{{(ω^{p} - 1)}^{2}} \\ = - \ln 2 + \frac{i π}{2} - \frac{i π ω^{p}}{ω^{p} - 1} \\ = - \ln 2 + \frac{i π}{2} - \frac{i π}{- ω^{- p} + 1} \\ = - \ln 2 + \frac{i π}{2} + \frac{i π}{ω^{- p} - 1}, \end{array}

and

\begin{array}{l} \sum_{1 \leq k < q} ω^{- k p} \ln \sin \frac{k}{q} π \\ = \sum_{1 \leq k < q ∕ 2} (ω^{- k p} + ω^{- (q - k) p}) \ln \sin \frac{k}{q} π \\ = \sum_{1 \leq k < q ∕ 2} 2 ω^{- p q ∕ 2} \cos (\frac{π p (q - 2 k)}{q}) \ln \sin \frac{k}{q} π \\ = 2 \sum_{1 \leq k < q ∕ 2} \cos (\frac{π p (q - 2 k)}{q}) \ln \sin \frac{k}{q} π \\ = 2 \sum_{1 \leq k < q ∕ 2} \cos (\frac{2 π p q}{2 q} - \frac{2 π p k}{q}) \ln \sin \frac{k}{q} π \\ = 2 \sum_{1 \leq k < q ∕ 2} \cos (- \frac{2 π p k}{q}) \ln \sin \frac{k}{q} π \\ = 2 \sum_{0 < k < q ∕ 2} \cos \frac{2 p k}{q} π \cdot \ln \sin \frac{k}{p} π . \end{array}

Finally,

\begin{array}{l} \frac{i}{2} + \frac{i}{ω^{- p} - 1} \\ = - \frac{1}{2} \cot \frac{p}{q} π . \end{array}

Hence,

H_{p ∕ q} = \frac{q}{p} - \frac{π}{2} \cot \frac{p}{q} π - \ln 2 q + 2 \sum_{0 < k < q ∕ 2} \cos \frac{2 p k}{q} π \cdot \ln \sin \frac{k}{q} π,

as we needed to show. □

______________________________________________________________________________________________________________________________

[exercise 1.2.7-24; C. F. Gauss, §33 of his monograph on hypergeometric series, Eq. [75]; Abel, Crelle 1 (1826), 314–315]

First, observe that multiplying both sides of Eq. (20) by $z^{n}$ yields

\begin{array}{l} \frac{z^{n}}{{(1 - z)}^{n + 1}} & = z^{n} \sum_{k \geq 0} (\binom{n + k}{n}) z^{k} \\ = \sum_{k \geq 0} (\binom{n + k}{n}) z^{n + k} \\ = \sum_{n \geq 0} (\binom{n}{k}) z^{n} . \end{array}

We then have

\begin{array}{l} \sum_{n \geq 0} n^{m} z^{n} & = \sum_{n \geq 0} \sum_{k} \{\binom{m}{k}\} n^{\underset{̲}{k}} z^{n} & by Eq. 1.2.6-(45) \\ = \sum_{k} \{\binom{m}{k}\} \sum_{n \geq 0} n^{\underset{̲}{k}} z^{n} \\ = \sum_{k} k! \{\binom{m}{k}\} \sum_{n \geq 0} \frac{n^{\underset{̲}{k}}}{k!} z^{n} \\ = \sum_{k} k! \{\binom{m}{k}\} \sum_{n \geq 0} (\binom{n}{k}) z^{n} \\ = \sum_{k} k! \{\binom{m}{k}\} \frac{z^{n}}{{(1 - z)}^{n + 1}}, \end{array}

so that

c_{m, k} = k! \{\binom{m}{k}\} .

Let $G (z) = \sum_{n \geq 0} n! z^{n}$ be the generating function for the sequence $⟨ n! ⟩$ . Given the recurrence

n! = n (n - 1)! + [n = 0]

we have that

\begin{array}{l} G (z) & = \sum_{n \geq 0} n! z^{n} \\ = \sum_{n \geq 0} n (n - 1)! z^{n} + \sum_{n = 0} z^{n} \\ = \sum_{n \geq 0} n (n - 1)! z^{n} + 1 \\ = \sum_{n \geq 0} (n + 1) n! z^{n + 1} + 1 \\ = \sum_{n \geq 0} (n) n! z^{n + 1} + \sum_{n \geq 0} n! z^{n + 1} + 1 \\ = \sum_{n \geq 0} (n) n! z^{n + 1} + z \sum_{n \geq 0} n! z^{n} + 1 \\ = \sum_{n \geq 0} (n) n! z^{n + 1} + z G (z) + 1 \\ = \sum_{n \geq 0} (n + 1) (n + 1)! z^{n + 2} + z G (z) + 1 \\ = z^{2} \sum_{n \geq 0} (n + 1) (n + 1)! z^{n} + z G (z) + 1 \\ = z^{2} G^{'} (z) + z G (z) + 1 . & by Eq. (14) \end{array}

This is the ordinary diﬀerential equation

z^{2} G^{'} (z) + (z - 1) G (z) + 1 = 0,

satisﬁed by

G (z) = \frac{- e^{- 1 ∕ z}}{z} (E_{1} (- 1 ∕ z) + C),

for the exponential integral $E_{1} (z) = \int_{z}^{\infty} \frac{1}{t e^{t}} d t$ and constant $C$ ; that is,

G (z) = \frac{- e^{- 1 ∕ z}}{z} (\int_{- 1 ∕ z}^{\infty} \frac{1}{t e^{t}} d t + C),

since

\begin{array}{l} \frac{d}{d z} G (z) & = \frac{d}{d z} (\frac{- e^{- 1 ∕ z}}{z} (E_{1} (- 1 ∕ z) + C)) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) + \frac{d}{d z} \frac{- e^{- 1 ∕ z}}{z} (E_{1} (- 1 ∕ z) + C) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) + \frac{\frac{d}{d z} (- e^{- 1 ∕ z}) z + e^{- 1 ∕ z} \frac{d}{d z} z}{z^{2}} (E_{1} (- 1 ∕ z) + C) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) + \frac{- e^{- 1 ∕ z} \frac{d}{d z} (- 1 ∕ z) z + e^{- 1 ∕ z}}{z^{2}} (E_{1} (- 1 ∕ z) + C) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) + \frac{- e^{- 1 ∕ z} (1 ∕ z^{2}) z + e^{- 1 ∕ z}}{z^{2}} (E_{1} (- 1 ∕ z) + C) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) + \frac{- e^{- 1 ∕ z} (1 ∕ z) + e^{- 1 ∕ z}}{z^{2}} (E_{1} (- 1 ∕ z) + C) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) + \frac{- e^{- 1 ∕ z} + z e^{- 1 ∕ z}}{z^{3}} (E_{1} (- 1 ∕ z) + C) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) + \frac{(z - 1) e^{- 1 ∕ z}}{z^{3}} (E_{1} (- 1 ∕ z) + C) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) - \frac{z - 1}{z^{2}} \frac{- e^{- 1 ∕ z}}{z} (E_{1} (- 1 ∕ z) + C) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (E_{1} (- 1 ∕ z) + C) - \frac{z - 1}{z^{2}} G (z) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{d}{d z} (\int_{- 1 ∕ z}^{\infty} \frac{1}{t e^{t}} d t + C) - \frac{z - 1}{z^{2}} G (z) \\ = \frac{- e^{- 1 ∕ z}}{z} z e^{1 ∕ z} \frac{d}{d z} \frac{- 1}{z} - \frac{z - 1}{z^{2}} G (z) \\ = \frac{- e^{- 1 ∕ z}}{z} z e^{1 ∕ z} \frac{1}{z^{2}} - \frac{z - 1}{z^{2}} G (z) \\ = \frac{- e^{- 1 ∕ z}}{z} e^{1 ∕ z} \frac{1}{z} - \frac{z - 1}{z^{2}} G (z) \\ = \frac{- e^{- 1 ∕ z}}{z} \frac{e^{1 ∕ z}}{z} - \frac{z - 1}{z^{2}} G (z) \\ = - \frac{1}{z^{2}} - \frac{z - 1}{z^{2}} G (z) \\ = - \frac{1}{z^{2}} (1 + (z - 1) G (z)) \end{array}

and

\begin{array}{l} z^{2} G^{'} (z) + (z - 1) G (z) + 1 \\ = z^{2} (- \frac{1}{z^{2}} (1 + (z - 1) G (z))) + (z - 1) G (z) + 1 \\ = - (1 + (z - 1) G (z)) + (z - 1) G (z) + 1 \\ = - 1 - (z - 1) G (z) + (z - 1) G (z) + 1 \\ = 0 . \end{array}

This generating function diverges, as may be veriﬁed using the root test, since for positive $n$ ,

\begin{array}{l} \sqrt[n]{n!} & \leq \sqrt[n]{\frac{n^{n + 1}}{e^{n - 1}}} & by exercise 1.2.5-24 \\ \approx \sqrt[n]{\frac{n^{n}}{e^{n}}} \\ = \frac{n}{e} \end{array}

is unbounded.

________________________________________________________________________________

[K. Knopp, Inﬁnite Sequences and Series (Dover, 1956), Section 66 [sic]]

As a preliminary, observe that if $z$ is an arbitrary complex number such that $| z | < 1$ , we have that

\prod_{i \geq 0} (1 + z^{2^{i}}) = \frac{1}{1 - z},

since

\begin{array}{l} (1 - z) \prod_{i \geq 0} (1 + z^{2^{i}}) & = (1 - z) \lim_{j \to \infty} \prod_{i = 0}^{j} (1 + z^{2^{i}}) \\ = \lim_{j \to \infty} (1 - z) \prod_{i = 0}^{j} (1 + z^{2^{i}}) \\ = \lim_{j \to \infty} (1 - z) (1 + z) \prod_{i = 1}^{j} (1 + z^{2^{i}}) \\ = \lim_{j \to \infty} (1 - z^{2}) \prod_{i = 1}^{j} (1 + z^{2^{i}}) \\ = \lim_{j \to \infty} (1 - z^{2}) (1 + z^{2}) \prod_{i = 2}^{j} (1 + z^{2^{i}}) \\ = \lim_{j \to \infty} (1 - z^{2^{2}}) \prod_{i = 2}^{j} (1 + z^{2^{i}}) \\ = \dots \\ = \lim_{j \to \infty} (1 - z^{2^{j}}) (1 + z^{2^{j}}) \\ = \lim_{j \to \infty} 1 - z^{2^{j + 1}} \\ = 1 . \end{array}

Now, for the given sum,

\sum_{2^{0} k_{0} + 2^{1} k_{1} + 2^{2} k_{2} + \dots = n} (\binom{r}{k_{0}}) (\binom{r}{k_{1}}) (\binom{r}{k_{2}}) \dots,

we may generate the $(\binom{r}{k_{i}})$ terms for all $i \geq 0$ using the binomial theorem as

\begin{array}{l} \sum_{k_{i} \geq 0} (\binom{r}{k_{i}}) z^{2^{i} k_{i}} & = \sum_{k_{i} \geq 0} (\binom{r}{k_{i}}) {(z^{2^{i}})}^{k_{i}} \\ = {(1 + z^{2^{i}})}^{r}, \end{array}

and then multiply them together to arrive at the equivalence

\begin{array}{l} \sum_{2^{0} k_{0} + 2^{1} k_{1} + 2^{2} k_{2} + \dots = n} (\binom{r}{k_{0}}) (\binom{r}{k_{1}}) (\binom{r}{k_{2}}) \dots \\ = {(1 + z^{2^{0}})}^{r} {(1 + z^{2^{1}})}^{r} {(1 + z^{2^{2}})}^{r} \dots \\ = \prod_{i \geq 0} {(1 + z^{2^{i}})}^{r} \\ = {(\prod_{i \geq 0} (1 + z^{2^{i}}))}^{r} \\ = {(\frac{1}{1 - z})}^{r} \\ = \frac{1}{{(1 - z)}^{r}} \\ = {(1 - z)}^{- r} . \end{array}

That is, the generating function is

G (z) = {(1 - z)}^{- r} .

Incidentally,

\begin{array}{l} {(1 - z)}^{- r} & = {(- z + 1)}^{- r} \\ = \sum_{n} (\binom{- r}{n}) {(- z)}^{n} 1^{- r - n} & by Eq. 1.2.6-(13) \\ = \sum_{n} {(- 1)}^{n} (\binom{- r}{n}) z^{n} \\ = \sum_{n} (\binom{n - (- r) - 1}{n}) z^{n} & by Eq. 1.2.6-(17) \\ = \sum_{n} (\binom{r + n - 1}{n}) z^{n} . \end{array}

The answers to exercise 23 follow below.

(a)

We may prove the identity.

Proposition. For all integers $m \geq 1$ there are polynomials $f_{m} (z_{1}, \dots, z_{m})$ and $g_{m} (z_{1}, \dots, z_{m})$ such that for all integers $n \geq r \geq 0$ ,

\begin{array}{l} \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} \\ = f_{m} {(z_{1}, \dots, z_{m})}^{n - r} g_{m} {(z_{1}, \dots, z_{m})}^{r} . \end{array}

Proof. Let $m$ be an arbitrary positive integer. We must show that there are polynomials $f_{m} (z_{1}, \dots, z_{m})$ and $g_{m} (z_{1}, \dots, z_{m})$ such that for all integers $n \geq r \geq 0$ ,

\begin{array}{l} \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} \\ = f_{m} {(z_{1}, \dots, z_{m})}^{n - r} g_{m} {(z_{1}, \dots, z_{m})}^{r} . \end{array}

We proceed with a proof by induction on $m$ .

In the case that $m = 1$ , let $f_{1} (z_{1}) = z_{1}$ and $g_{1} (z_{1}) = z_{1} + 1$ . Then we must show in this case that

\begin{array}{l} \sum_{k_{1} \geq 0} (\binom{r}{n - k_{1}}) z_{1}^{k_{1}} & = f_{1} {(z_{1})}^{n - r} g_{1} {(z_{1})}^{r} \\ = z_{1}^{n - r} {(z_{1} + 1)}^{r} . \end{array}

If $r = 0$ ,

\begin{array}{l} \sum_{k_{1} \geq 0} (\binom{0}{n - k_{1}}) z_{1}^{k_{1}} & = \sum_{k_{1} = n} (\binom{0}{n - k_{1}}) z_{1}^{k_{1}} \\ = (\binom{0}{0}) z_{1}^{n} \\ = z_{1}^{n} \\ = z_{1}^{n - 0} {(z_{1} + 1)}^{0} . \end{array}

Then, assuming

\sum_{k_{1} \geq 0} (\binom{r}{n - k_{1}}) z_{1}^{k_{1}} = z_{1}^{n - r} {(z_{1} + 1)}^{r},

we must show that

\sum_{k_{1} \geq 0} (\binom{r + 1}{n - k_{1}}) z_{1}^{k_{1}} = z_{1}^{n - (r + 1)} {(z_{1} + 1)}^{r + 1} .

But

\begin{array}{l} \sum_{k_{1} \geq 0} (\binom{r + 1}{n - k_{1}}) z_{1}^{k_{1}} & = \sum_{k_{1} \geq 0} (\binom{r}{n - k_{1}}) z_{1}^{k_{1}} + \sum_{k_{1} \geq 0} (\binom{r}{n - k_{1} - 1}) z_{1}^{k_{1}} \\ = \sum_{k_{1} \geq 0} (\binom{r}{n - k_{1}}) z_{1}^{k_{1}} + \sum_{k_{1} \geq 0} (\binom{r}{(n - 1) - k_{1}}) z_{1}^{k_{1}} \\ = z_{1}^{n - r} {(z_{1} + 1)}^{r} + z_{1}^{(n - 1) - r} {(z_{1} + 1)}^{r} \\ = (z_{1}^{n - r} + z_{1}^{(n - 1) - r}) {(z_{1} + 1)}^{r} \\ = (z_{1}^{n - r} + z_{1}^{n - (r + 1)}) {(z_{1} + 1)}^{r} \\ = (z_{1} z_{1}^{n - (r + 1)} + z_{1}^{n - (r + 1)}) {(z_{1} + 1)}^{r} \\ = z_{1}^{n - (r + 1)} (z_{1} + 1) {(z_{1} + 1)}^{r} \\ = z_{1}^{n - (r + 1)} {(z_{1} + 1)}^{r + 1} . \end{array}

As our inductive hypothesis, we assume that there are polynomials $f_{m} (z_{1}, \dots, z_{m})$ and $g_{m} (z_{1}, \dots, z_{m})$ such that for all integers $n \geq r \geq 0$ ,

\begin{array}{l} \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} \\ = f_{m} {(z_{1}, \dots, z_{m})}^{n - r} g_{m} {(z_{1}, \dots, z_{m})}^{r} . \end{array}

We must show that there are polynomials $f_{m + 1} (z_{1}, \dots, z_{m + 1})$ and $g_{m + 1} (z_{1}, \dots, z_{m + 1})$ such that for all integers $n \geq r \geq 0$ ,

\begin{array}{l} \sum_{k_{1}, \dots, k_{m + 1} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{(m + 1) - 1}}{n - k_{m + 1}}) z_{1}^{k_{1}} \dots z_{m + 1}^{k_{m + 1}} \\ = f_{m + 1} {(z_{1}, \dots, z_{m + 1})}^{n - r} g_{m + 1} {(z_{1}, \dots, z_{m + 1})}^{r} . \end{array}

But, set $z_{m} \leftarrow z_{m} (1 + z_{m + 1}^{- 1})$ , and let

\begin{array}{l} f_{m + 1} (z_{1}, \dots, z_{m + 1}) & = z_{m + 1} f_{m} (z_{1}, \dots, z_{m} (1 + z_{m + 1}^{- 1})), \\ g_{m + 1} (z_{1}, \dots, z_{m + 1}) & = z_{m + 1} g_{m} (z_{1}, \dots, z_{m} (1 + z_{m + 1}^{- 1})) . \end{array}

Then

\begin{array}{l} f_{m + 1} {(z_{1}, \dots, z_{m + 1})}^{n - r} g_{m + 1} {(z_{1}, \dots, z_{m + 1})}^{r} \\ = {(z_{m + 1} f_{m} (z_{1}, \dots, z_{m} (1 + z_{m + 1}^{- 1})))}^{n - r} {(z_{m + 1} g_{m} (z_{1}, \dots, z_{m} (1 + z_{m + 1}^{- 1})))}^{r} \\ = z_{m + 1}^{n} f_{m} {(z_{1}, \dots, z_{m} (1 + z_{m + 1}^{- 1}))}^{n - r} g_{m} {(z_{1}, \dots, z_{m} (1 + z_{m + 1}^{- 1}))}^{r} \\ = z_{m + 1}^{n} \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots {(z_{m} (1 + z_{m + 1}^{- 1}))}^{k_{m}} \\ = z_{m + 1}^{n} \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} {(1 + z_{m + 1}^{- 1})}^{k_{m}} \\ = z_{m + 1}^{n} \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} \\ \cdot \sum_{k_{m + 1} \geq 0} (\binom{k_{m}}{k_{m + 1}}) 1^{k_{m} - k_{m + 1}} z_{m + 1}^{- k_{m + 1}} \\ = \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} \\ \cdot \sum_{k_{m + 1} \geq 0} (\binom{k_{m}}{k_{m + 1}}) z_{m + 1}^{n - k_{m + 1}} \\ = \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} \\ \cdot \sum_{k_{m + 1} \geq 0} (\binom{k_{(m + 1) - 1}}{n - k_{m + 1}}) z_{m + 1}^{k_{m + 1}} \\ = \sum_{k_{1}, \dots, k_{m + 1} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{(m + 1) - 1}}{n - k_{m + 1}}) z_{1}^{k_{1}} \dots z_{m + 1}^{k_{m + 1}} . \end{array}

This is what we needed to show. □

Note that $f_{m} (z_{1}, \dots, z_{m})$ obeys the recurrence

f_{m} (z_{1}, \dots, z_{m}) = \{\begin{matrix} 0 & if m < 0 \\ 1 & if m = 0 \\ z_{m} f_{m - 1} + z_{m - 1} f_{m - 2} & otherwise, \end{matrix}

since $f_{1} (z_{1}) = z_{1} = z_{1} f_{0} + z_{0} f_{- 1}$ , and if $f_{m} (z_{1}, \dots, z_{m}) = z_{m} f_{m - 1} + z_{m - 1} f_{m - 2}$ , then

\begin{array}{l} f_{m + 1} (z_{1}, \dots, z_{m + 1}) & = z_{m + 1} f_{m} (z_{1}, \dots, z_{m - 1}, z_{m} (1 + z_{m + 1}^{- 1})) \\ = z_{m + 1} (z_{m} (1 + z_{m + 1}^{- 1}) f_{m - 1} + z_{m - 1} f_{m - 2}) \\ = z_{m + 1} (z_{m} z_{m + 1}^{- 1} f_{m - 1} + z_{m} f_{m - 1} + z_{m - 1} f_{m - 2}) \\ = z_{m + 1} (z_{m} z_{m + 1}^{- 1} f_{m - 1} + f_{m}) \\ = z_{m} z_{m + 1} z_{m + 1}^{- 1} f_{m - 1} + z_{m + 1} f_{m} \\ = z_{m + 1} f_{m} + z_{m} f_{m - 1}; \end{array}

and similarly $g_{m} (z_{1}, \dots, z_{m})$ the recurrence

g_{m} (z_{1}, \dots, z_{m}) = \{\begin{matrix} 1 & if m \leq 0 \\ z_{m} g_{m - 1} + z_{m - 1} g_{m - 2} & otherwise, \end{matrix}

since $g_{1} (z_{1}) = z_{1} + 1 = z_{1} g_{0} + z_{0} g_{- 1}$ , and if $g_{m} (z_{1}, \dots, z_{m}) = z_{m} g_{m - 1} + z_{m - 1} g_{m - 2}$ , then

\begin{array}{l} g_{m + 1} (z_{1}, \dots, z_{m + 1}) & = z_{m + 1} g_{m} (z_{1}, \dots, z_{m - 1}, z_{m} (1 + z_{m + 1}^{- 1})) \\ = z_{m + 1} (z_{m} (1 + z_{m + 1}^{- 1}) g_{m - 1} + z_{m - 1} g_{m - 2}) \\ = z_{m + 1} (z_{m} z_{m + 1}^{- 1} g_{m - 1} + z_{m} g_{m - 1} + z_{m - 1} g_{m - 2}) \\ = z_{m + 1} (z_{m} z_{m + 1}^{- 1} g_{m - 1} + g_{m}) \\ = z_{m} z_{m + 1} z_{m + 1}^{- 1} g_{m - 1} + z_{m + 1} g_{m} \\ = z_{m + 1} g_{m} + z_{m} g_{m - 1} . \end{array}

(b)

We want to ﬁnd a closed form for the sum

S_{n} (z_{1}, \dots, z_{m}) = \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{k_{1}}{n - k_{2}}) (\binom{k_{2}}{n - k_{3}}) \dots (\binom{k_{m}}{n - k_{1}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}}

in terms of the functions $f_{m}$ and $g_{m}$ of part (a). But

\begin{array}{l} S_{n} (z_{1}, \dots, z^{m - 1}, z) \\ = \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{k_{1}}{n - k_{2}}) (\binom{k_{2}}{n - k_{3}}) \dots (\binom{k_{m}}{n - k_{1}}) z_{1}^{k_{1}} \dots z^{k_{m}} \\ = \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{k_{m}}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z^{k_{m}} \\ = [z_{m}^{n}] \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{k_{m}}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z^{k_{m}} z_{m}^{n} \\ = [z_{m}^{n}] \sum_{\begin{array}{c} k_{1}, \dots, k_{m} \geq 0 \\ r = k_{m} \end{array}} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z^{r} z_{m}^{n - r + k_{m}} \\ = [z_{m}^{n}] \sum_{\begin{array}{c} k_{1}, \dots, k_{m} \geq 0 \\ 0 \leq r \leq n \end{array}} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z^{r} z_{m}^{n - r + k_{m}} \\ = [z_{m}^{n}] \sum_{\begin{array}{c} k_{1}, \dots, k_{m} \geq 0 \\ 0 \leq r \leq n \end{array}} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} z^{r} z_{m}^{n - r} \\ = [z_{m}^{n}] \sum_{r = 0}^{n} z^{r} z_{m}^{n - r} \sum_{k_{1}, \dots, k_{m} \geq 0} (\binom{r}{n - k_{1}}) (\binom{k_{1}}{n - k_{2}}) \dots (\binom{k_{m - 1}}{n - k_{m}}) z_{1}^{k_{1}} \dots z_{m}^{k_{m}} \\ = [z_{m}^{n}] \sum_{r = 0}^{n} z^{r} z_{m}^{n - r} f_{m} {(z_{1}, \dots, z_{m})}^{n - r} g_{m} {(z_{1}, \dots, z_{m})}^{r} . \end{array}

Then,

\begin{array}{l} S_{n} (z_{1}, \dots, z_{m}) \\ = [z_{m}^{n}] \sum_{r = 0}^{n} z_{m}^{r} z_{m}^{n - r} f_{m} {(z_{1}, \dots, z_{m})}^{n - r} g_{m} {(z_{1}, \dots, z_{m})}^{r} \\ = [z_{m}^{n}] \sum_{r = 0}^{n} f_{m} {(z_{1}, \dots, z_{m})}^{n - r} g_{m} {(z_{1}, \dots, z_{m})}^{r} z_{m}^{n} \\ = \sum_{r = 0}^{n} f_{m} {(z_{1}, \dots, z_{m})}^{n - r} g_{m} {(z_{1}, \dots, z_{m})}^{r} \\ = \sum_{r = 0}^{n} {(z_{m} f_{m - 1} + z_{m - 1} f_{m - 2})}^{n - r} {(z_{m} g_{m - 1} + z_{m - 1} g_{m - 2})}^{r} \\ = \sum_{r = 0}^{n} (\sum_{0 \leq s \leq n - r} (\binom{n - r}{s}) {(z_{m} f_{m - 1})}^{s} {(z_{m - 1} f_{m - 2})}^{n - r - s} \sum_{0 \leq s \leq n} (\binom{r}{s}) {(z_{m - 1} g_{m - 2})}^{s} {(z_{m} g_{m - 1})}^{r - s}) \\ = \sum_{0 \leq s \leq r \leq n} (\binom{r}{s}) (\binom{n - r}{s}) {(z_{m} g_{m - 1})}^{r - s} {(z_{m - 1} g_{m - 2})}^{s} {(z_{m} f_{m - 1})}^{s} {(z_{m - 1} f_{m - 2})}^{n - r - s}; \end{array}

and, by Eq. (20),

\begin{array}{l} S_{n} (z_{1}, \dots, z_{m}) \\ = \sum_{0 \leq s \leq r \leq n} (\binom{r}{s}) (\binom{n - r}{s}) {(z_{m} g_{m - 1})}^{r - s} {(z_{m - 1} g_{m - 2})}^{s} {(z_{m} f_{m - 1})}^{s} {(z_{m - 1} f_{m - 2})}^{n - r - s} \\ = [z^{n}] \sum_{s \geq 0} \sum_{r \geq s} \sum_{n \geq r} (\binom{r}{s}) (\binom{n - r}{s}) {(z_{m} g_{m - 1} z)}^{r - s} {(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s} {(z_{m - 1} f_{m - 2} z)}^{n - r - s} \\ = [z^{n}] \sum_{s \geq 0} {(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s} \sum_{r \geq s} (\binom{r}{s}) {(z_{m} g_{m - 1} z)}^{r - s} \sum_{n \geq r} (\binom{n - r}{s}) {(z_{m - 1} f_{m - 2} z)}^{n - r - s} \\ = [z^{n}] \sum_{s \geq 0} {(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s} \sum_{r \geq s} (\binom{r}{s}) {(z_{m} g_{m - 1} z)}^{r - s} \sum_{n - r \geq 0} (\binom{n - r}{s}) {(z_{m - 1} f_{m - 2} z)}^{n - r - s} \\ = [z^{n}] \sum_{s \geq 0} {(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s} \sum_{r \geq s} (\binom{r}{s}) {(z_{m} g_{m - 1} z)}^{r - s} \sum_{n \geq 0} (\binom{n}{s}) {(z_{m - 1} f_{m - 2} z)}^{n - s} \\ = [z^{n}] \sum_{s \geq 0} {(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s} \sum_{r \geq s} (\binom{r}{s}) {(z_{m} g_{m - 1} z)}^{r - s} {(z_{m - 1} f_{m - 2} z)}^{- s} \sum_{n \geq 0} (\binom{n}{s}) {(z_{m - 1} f_{m - 2} z)}^{n} \\ = [z^{n}] \sum_{s \geq 0} {(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s} \sum_{r \geq s} (\binom{r}{s}) {(z_{m} g_{m - 1} z)}^{r - s} {(z_{m - 1} f_{m - 2} z)}^{- s} \frac{{(z_{m - 1} f_{m - 2} z)}^{s}}{{(1 - z_{m - 1} f_{m - 2} z)}^{s + 1}} \\ = [z^{n}] \sum_{s \geq 0} \frac{{(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s}}{{(1 - z_{m - 1} f_{m - 2} z)}^{s + 1}} \sum_{r \geq s} (\binom{r}{s}) {(z_{m} g_{m - 1} z)}^{r - s} \\ = [z^{n}] \sum_{s \geq 0} \frac{{(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s}}{{(1 - z_{m - 1} f_{m - 2} z)}^{s + 1}} \sum_{r - s \geq 0} (\binom{s + r - s}{s}) {(z_{m} g_{m - 1} z)}^{r - s} \\ = [z^{n}] \sum_{s \geq 0} \frac{{(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s}}{{(1 - z_{m - 1} f_{m - 2} z)}^{s + 1}} \sum_{r \geq 0} (\binom{s + r}{s}) {(z_{m} g_{m - 1} z)}^{r} \\ = [z^{n}] \sum_{s \geq 0} \frac{{(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s}}{{(1 - z_{m - 1} f_{m - 2} z)}^{s + 1}} \frac{1}{{(1 - z_{m} g_{m - 1} z)}^{s + 1}} \\ = [z^{n}] \sum_{s \geq 0} \frac{{(z_{m - 1} g_{m - 2} z)}^{s} {(z_{m} f_{m - 1} z)}^{s}}{{(1 - z_{m} g_{m - 1} z)}^{s + 1} {(1 - z_{m - 1} f_{m - 2} z)}^{s + 1}} \\ = [z^{n}] \sum_{s \geq 0} \frac{1}{1 - z_{m} g_{m - 1} z} \frac{1}{1 - z_{m - 1} f_{m - 2} z} {(\frac{z_{m - 1} g_{m - 2} z_{m} f_{m - 1} z^{2}}{(1 - z_{m} g_{m - 1} z) (1 - z_{m - 1} f_{m - 2} z)})}^{s} \\ = [z^{n}] \frac{1}{1 - z_{m} g_{m - 1} z} \frac{1}{1 - z_{m - 1} f_{m - 2} z} \frac{1}{1 - z_{m - 1} g_{m - 2} z_{m} f_{m - 1} z^{2} ∕ ((1 - z_{m} g_{m - 1} z) (1 - z_{m - 1} f_{m - 2} z))} \\ = [z^{n}] \frac{1}{z_{m} g_{m - 1} z_{m - 1} f_{m - 2} z^{2} - z_{m} g_{m - 1} z - z_{m - 1} g_{m - 2} z_{m} f_{m - 1} z^{2} - z_{m - 1} f_{m - 2} z + 1} \\ = [z^{n}] \frac{1}{(1 - z_{m} g_{m - 1} z) (1 - z_{m - 1} f_{m - 2} z) - z_{m - 1} g_{m - 2} z_{m} f_{m - 1} z^{2}} . \end{array}

Let

h_{m} = z_{m} g_{m - 1} + z_{m - 1} f_{m - 2}

and

\begin{array}{l} (1 - ρ z) (1 - σ z) = 1 - h_{m} z + {(- 1)}^{m} z_{1} \dots z_{m} z^{2} \\ \Leftrightarrow 1 - ρ z - σ z + ρ σ z^{2} = 1 - h_{m} z + {(- 1)}^{m} z_{1} \dots z_{m} z^{2} \\ \Leftrightarrow 1 - (ρ + σ) z + ρ σ z^{2} = 1 - h_{m} z + {(- 1)}^{m} z_{1} \dots z_{m} z^{2} \\ \Leftrightarrow ρ + σ = h_{m} \land ρ σ = {(- 1)}^{m} z_{1} \dots z_{m} . \end{array}

Then, since

\begin{array}{l} z_{m} g_{m - 1} z_{m - 1} f_{m - 2} - z_{m - 1} g_{m - 2} z_{m} f_{m - 1} \\ = z_{m - 1} z_{m} (g_{m - 1} f_{m - 2} - g_{m - 2} f_{m - 1}) \\ = z_{m - 1} z_{m} ((z_{m - 1} g_{m - 2} + z_{m - 2} g_{m - 3}) f_{m - 2} - g_{m - 2} (z_{m - 1} f_{m - 2} + z_{m - 2} f_{m - 3})) \\ = z_{m - 1} z_{m} (z_{m - 1} g_{m - 2} f_{m - 2} + z_{m - 2} g_{m - 3} f_{m - 2} - g_{m - 2} z_{m - 1} f_{m - 2} - g_{m - 2} z_{m - 2} f_{m - 3}) \\ = z_{m - 1} z_{m} (z_{m - 2} g_{m - 3} f_{m - 2} - g_{m - 2} z_{m - 2} f_{m - 3}) \\ = (- 1) z_{m - 2} z_{m - 1} z_{m} (g_{m - 2} f_{m - 3} - g_{m - 3} f_{m - 2}) \\ ⋮ \\ = {(- 1)}^{m} z_{1} \dots z_{m} \end{array}

we ﬁnd

\begin{array}{l} S_{n} (z_{1}, \dots, z_{m}) \\ = [z^{n}] \frac{1}{(1 - z_{m} g_{m - 1} z) (1 - z_{m - 1} f_{m - 2} z) - z_{m - 1} g_{m - 2} z_{m} f_{m - 1} z^{2}} \\ = [z^{n}] \frac{1}{1 - z_{m} g_{m - 1} z - z_{m - 1} f_{m - 2} z + z_{m} g_{m - 1} z_{m - 1} f_{m - 2} z^{2} - z_{m - 1} g_{m - 2} z_{m} f_{m - 1} z^{2}} \\ = [z^{n}] \frac{1}{1 - (z_{m} g_{m - 1} + z_{m - 1} f_{m - 2}) z + (z_{m} g_{m - 1} z_{m - 1} f_{m - 2} - z_{m - 1} g_{m - 2} z_{m} f_{m - 1}) z^{2}} \\ = [z^{n}] \frac{1}{1 - h_{m} z + {(- 1)}^{m} z_{1} \dots z_{m} z^{2}} \\ = [z^{n}] \frac{1}{(1 - ρ z) (1 - σ z)} \\ = [z^{n}] (\frac{ρ}{ρ - σ} \frac{1}{1 - ρ z} + \frac{σ}{σ - ρ} \frac{1}{1 - σ z}) \\ = [z^{n}] (\frac{ρ}{ρ - σ} \sum_{n \geq 0} ρ^{n} z^{n} + \frac{σ}{σ - ρ} \sum_{n \geq 0} σ^{n} z^{n}) \\ = [z^{n}] \sum_{n \geq 0} (\frac{ρ}{ρ - σ} ρ^{n} + \frac{σ}{σ - ρ} σ^{n}) z^{n} \\ = [z^{n}] \sum_{n \geq 0} (\frac{ρ^{n + 1}}{ρ - σ} - \frac{σ^{n + 1}}{ρ - σ}) z^{n} \\ = [z^{n}] \sum_{n \geq 0} \frac{ρ^{n + 1} - σ^{n + 1}}{ρ - σ} z^{n} \\ = \frac{ρ^{n + 1} - σ^{n + 1}}{ρ - σ} . \end{array}

(c)

When

z_{1} = \dots = z_{m} = z

, we may simplify

S_{n} (z, \dots, z)

. In the case

m = 1

,

\begin{array}{l} ρ_{1} + σ_{1} & = h_{1} = z_{1} = z, \\ ρ_{1} σ_{1} & = {(- 1)}^{1} z_{1} = - z_{1} = - z, \end{array}

satisﬁed by

\begin{array}{l} ρ_{1} & = \frac{z + \sqrt{z^{2} + 4 z}}{2}, \\ σ_{1} & = \frac{z - \sqrt{z^{2} + 4 z}}{2}; \end{array}

and in the case $m \geq 1$ , since

\begin{array}{l} ρ_{m} + σ_{m} & = h_{m} \\ = z g_{m - 1} + z f_{m - 2} \\ = z (g_{m - 1} + f_{m - 2}) \\ = z (z g_{m - 2} + z g_{m - 3} + z f_{m - 3} + z f_{m - 4}) \\ = z^{2} (g_{m - 2} + g_{m - 3} + f_{m - 3} + f_{m - 4}) \\ = ⋮ \\ = z^{m} \\ = {(ρ_{1} + σ_{1})}^{m} \end{array}

and

\begin{array}{l} ρ_{m} σ_{m} & = {(- 1)}^{m} z^{m} \\ = {(- z)}^{m} \\ = {(ρ_{1} σ_{1})}^{m}, \end{array}

we ﬁnd in general that

\begin{array}{l} ρ_{m} & = ρ_{1}^{m}, \\ σ_{m} & = σ_{1}^{m} . \end{array}

That is,

\begin{array}{l} S_{n} (z, \dots, z) & = \frac{ρ_{m}^{n + 1} - σ_{m}^{n + 1}}{ρ_{m} - σ_{m}} \\ = \frac{ρ_{1}^{m (n + 1)} - σ_{1}^{m (n + 1)}}{ρ_{1}^{m} - σ_{1}^{m}} \\ = \frac{{((z + \sqrt{z^{2} + 4 z}) ∕ 2)}^{m (n + 1)} - {((z - \sqrt{z^{2} + 4 z}) ∕ 2)}^{m (n + 1)}}{{((z + \sqrt{z^{2} + 4 z}) ∕ 2)}^{m} - {((z - \sqrt{z^{2} + 4 z}) ∕ 2)}^{m}} \\ = \frac{1}{2^{m n}} \frac{{(z + \sqrt{z^{2} + 4 z})}^{m (n + 1)} - {(z - \sqrt{z^{2} + 4 z})}^{m (n + 1)}}{{(z + \sqrt{z^{2} + 4 z})}^{m} - {(z - \sqrt{z^{2} + 4 z})}^{m}} . \end{array}

______________________________________________________________________________________________________________________________

[exercise 1.2.8-30; L. Carlitz, Collectanea Math. 27 [sic] (1965), 281–296]

Proposition. $\sum_{k} (\binom{m}{k}) [z^{n - k}] G {(z)}^{k} = [z^{n}] {(1 + z G (z))}^{m}$ .

Proof. Suppose $G (z)$ is an arbitrary generating function,

G (z) = \sum_{n \geq 0} g_{n} z^{n} .

We must show that

\sum_{k} (\binom{m}{k}) [z^{n - k}] G {(z)}^{k} = [z^{n}] {(1 + z G (z))}^{m} .

But by a rule of the coeﬃcient of operator² ,

\begin{array}{l} \sum_{k} (\binom{m}{k}) [z^{n - k}] G {(z)}^{k} & = \sum_{k} (\binom{m}{k}) [z^{n}] z^{k} G {(z)}^{k} \\ = [z^{n}] \sum_{k} (\binom{m}{k}) G {(z)}^{k} z^{k} \\ = [z^{n}] \sum_{k} (\binom{m}{k}) {(z G (z))}^{k} \\ = [z^{n}] {(1 + z G (z))}^{m}, \end{array}

as we needed to show. □

(a)

For

G (z) = \frac{1}{1 - z}

,

\begin{array}{l} \sum_{k} (\binom{m}{k}) [z^{n - k}] G {(z)}^{k} & = \sum_{k} (\binom{m}{k}) [z^{n - k}] {(\frac{1}{1 - z})}^{k} \\ = \sum_{k} (\binom{m}{k}) [z^{n - k}] \frac{1}{{(1 - z)}^{k}} \\ = \sum_{k} (\binom{m}{k}) [z^{n - k}] \sum_{n \geq 0} (\binom{k + n - 1}{n}) z^{n} \\ = \sum_{k} (\binom{m}{k}) [z^{n - k}] \sum_{n - k \geq 0} (\binom{k + n - k - 1}{n - k}) z^{n - k} \\ = \sum_{k} (\binom{m}{k}) [z^{n - k}] \sum_{n - k \geq 0} (\binom{n - 1}{n - k}) z^{n - k} \\ = \sum_{k} (\binom{m}{k}) (\binom{n - 1}{n - k}) \end{array}

and

\begin{array}{l} [z^{n}] {(1 + z G (z))}^{m} & = [z^{n}] {(1 + z \frac{1}{1 - z})}^{m} \\ = [z^{n}] \sum_{k} (\binom{m}{k}) {(z \frac{1}{1 - z})}^{k} \\ = [z^{n}] \sum_{k} (\binom{m}{k}) z^{k} \frac{1}{{(1 - z)}^{k}} \\ = [z^{n}] \sum_{k} (\binom{m}{k}) z^{k} \sum_{n} (\binom{k + n - 1}{n}) z^{n} \\ = [z^{n}] \sum_{k} (\binom{m}{k}) z^{k} \sum_{n - k} (\binom{n - 1}{n - k}) z^{n - k} \\ = [z^{n}] \sum_{k} (\binom{m}{k}) z^{k} \sum_{k} (\binom{n - 1}{k}) z^{k} \\ = [z^{n}] {(1 + z)}^{m} {(1 + z)}^{n - 1} \\ = [z^{n}] {(1 + z)}^{m + n - 1} \\ = [z^{n}] \sum_{n \geq 0} (\binom{m + n - 1}{n}) z^{n} \\ = (\binom{m + n - 1}{n}) . \end{array}

(b)

For

G (z) = \frac{e^{z} - 1}{z}

,

\begin{array}{l} \sum_{k} (\binom{m}{k}) [z^{n - k}] G {(z)}^{k} & = \sum_{k} (\binom{m}{k}) [z^{n - k}] {(\frac{e^{z} - 1}{z})}^{k} \\ = \sum_{k} (\binom{m}{k}) [z^{n}] z^{k} {(\frac{e^{z} - 1}{z})}^{k} \\ = \sum_{k} (\binom{m}{k}) [z^{n}] z^{k} \frac{{(e^{z} - 1)}^{k}}{z^{k}} \\ = \sum_{k} (\binom{m}{k}) [z^{n}] {(e^{z} - 1)}^{k} \\ = \sum_{k} (\binom{m}{k}) [z^{n}] k! \sum_{n} \{\binom{n}{k}\} \frac{z^{n}}{n!} & by Eq. (23) \\ = \sum_{k} (\binom{m}{k}) k! [z^{n}] \sum_{n} \{\binom{n}{k}\} \frac{z^{n}}{n!} \\ = \sum_{k} (\binom{m}{k}) k! \{\binom{n}{k}\} / n! \\ = \sum_{k} \frac{m^{\underset{̲}{k}}}{k!} k! \{\binom{n}{k}\} / n! \\ = \sum_{k} m^{\underset{̲}{k}} \{\binom{n}{k}\} / n! \end{array}

and

\begin{array}{l} [z^{n}] {(1 + z G (z))}^{m} & = [z^{n}] {(1 + z \frac{e^{z} - 1}{z})}^{m} \\ = [z^{n}] {(e^{z})}^{m} \\ = [z^{n}] e^{m z} \\ = [z^{n}] \sum_{n \geq 0} \frac{{(m z)}^{n}}{n!} \\ = [z^{n}] \sum_{n \geq 0} \frac{m^{n}}{n!} z^{n} \\ = m^{n} ∕ n!, \end{array}

since

\sum_{k} m^{\underset{̲}{k}} \{\binom{n}{k}\} = m^{n} .

We have

\begin{array}{l} \sum_{k} [w^{k}] {(1 - 2 w)}^{n} [z^{n - k}] {(1 + z)}^{2 n - 2 k} \\ = \sum_{k} [w^{k}] {(1 - 2 w)}^{n} [z^{n}] z^{k} {(1 + z)}^{2 n - 2 k} \\ = [z^{n}] \sum_{k} [w^{k}] {(1 - 2 w)}^{n} z^{k} {(1 + z)}^{2 n - 2 k} \\ = [z^{n}] \sum_{k} [w^{k}] {(1 - 2 w)}^{n} z^{k} {(1 + z)}^{2 n} {(1 + z)}^{- 2 k} \\ = [z^{n}] {(1 + z)}^{2 n} \sum_{k} [w^{k}] {(1 - 2 w)}^{n} z^{k} {(1 + z)}^{- 2 k} \\ = [z^{n}] {(1 + z)}^{2 n} \sum_{k} [w^{k}] {(1 - 2 w)}^{n} z^{k} {(1 ∕ {(1 + z)}^{2})}^{k} \\ = [z^{n}] {(1 + z)}^{2 n} \sum_{k} [w^{k}] {(1 - 2 w)}^{n} {(z ∕ {(1 + z)}^{2})}^{k} \\ = [z^{n}] {(1 + z)}^{2 n} \sum_{k} [w^{k}] {(z ∕ {(1 + z)}^{2})}^{k} {(1 - 2 w)}^{n} \\ = [z^{n}] {(1 + z)}^{2 n} \sum_{k} [w^{k}] {(z ∕ {(1 + z)}^{2})}^{k} \sum_{j} (\binom{n}{j}) {(- 2 w)}^{j} \\ = [z^{n}] {(1 + z)}^{2 n} \sum_{k} [w^{k}] {(z ∕ {(1 + z)}^{2})}^{k} \sum_{j} {(- 2)}^{j} (\binom{n}{j}) w^{j} \\ = [z^{n}] {(1 + z)}^{2 n} \sum_{k} {(z ∕ {(1 + z)}^{2})}^{k} {(- 2)}^{k} (\binom{n}{k}) \\ = [z^{n}] {(1 + z)}^{2 n} \sum_{k} (\binom{n}{k}) {(- 2 z ∕ {(1 + z)}^{2})}^{k} \\ = [z^{n}] {(1 + z)}^{2 n} {(1 - 2 z ∕ {(1 + z)}^{2})}^{n} \\ = [z^{n}] {({(1 + z)}^{2} (1 - 2 z ∕ {(1 + z)}^{2}))}^{n} \\ = [z^{n}] {({(1 + z)}^{2} - 2 z)}^{n} \\ = [z^{n}] {(1 + z^{2})}^{n} \\ = [z^{n}] \sum_{k} (\binom{n}{k}) {(z^{2})}^{k} \\ = [z^{n}] \sum_{k} (\binom{n}{k}) z^{2 k} \\ = [z^{n}] \sum_{\begin{array}{c} k ∕ 2 \\ k even \end{array}} (\binom{n}{k ∕ 2}) z^{k} \\ = (\binom{n}{n ∕ 2}) [n even] . \end{array}

______________________________________________________________________________________________________________________________

[G. P. Egorychev, Integral Representation and the Computation of Combintatorial Sums (Amer. Math. Soc., 1984)]

n.a.

________________________________________________________________________________

[D. E. Knuth, A Classical Mind (Prentice-Hall, 1994), 247–258]