The ordinary generating function for $ζ(s)$

Question

$$\zeta(s)^m = \sum_{n=1}^{\infty} \frac{a_n}{n^s}$$

where $ζ(s)$ is the Riemann zeta function has the ordinary generating function:

$$\sum \limits_{n=1}^{\infty} a_nx^n = x + {m \choose 1}\sum \limits_{a=2}^{\infty} x^{a} + {m \choose 2}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} x^{ab} + {m \choose 3}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} \sum \limits_{c=2}^{\infty} x^{abc} + {m \choose 4}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} \sum \limits_{c=2}^{\infty} \sum \limits_{d=2}^{\infty} x^{abcd} +... $$ $\tag1$

Wikipedia reference is http://en.wikipedia.org/wiki/Dirichlet_series

My Attempt to prove is below But I am stuck

$$\zeta(s) = \sum_{n=1}^{\infty} \frac{1}{n^s}=(1+\frac{1}{2^s}+\frac{1}{2^{2s}}+....)(1+\frac{1}{3^s}+\frac{1}{3^{2s}}+....)(1+\frac{1}{5^s}+\frac{1}{5^{2s}}+....)...=\prod_{p= prime} \frac{1}{1-p^{-s}}$$

$$\zeta(s)^m = (\sum_{n=1}^{\infty} \frac{1}{n^s})^m=(\frac{1}{1^s}+\frac{1}{2^s}+\frac{1}{3^s}+.....)^m=\prod_{p= prime}(1-p^{-s})^{-m}=\prod_{p= prime}(1+mp^{-s}+\frac{m(m+1)p^{-2s}}{2!}+\frac{m(m+1)(m+2)p^{-3s}}{3!}+....)$$

If we find all prime factors for $n$

if $n=p^{b_1}_1p^{b_2}_2 p^{b_3}_3... p^{b_r}_r$ then

$$a_n=\frac{m(m+1)..(m+(b_1-1))}{b_1!}.\frac{m(m+1)..(m+(b_2-1))}{b_2!}...\frac{m(m+1)..(m+(b_r-1))}{b_r!}$$

I could not see a way after that point how to prove the generation function . Could you please help me how to get the result shown in Equation $1$ with elementary methods?

Thanks a lot for answers

Answer 1

with elementary methods

Not sure if that counts as elementary, but:

If you compute

$$\zeta(s)^m = \left(\sum_{n=1}^\infty \frac{1}{n^s}\right)^m$$

as a Cauchy product of absolutely convergent series, you can see that $a_n$ is the number of ways you can write $n$ as a product of $m$ positive integers, where order matters. $1$ is included as an allowed factor here.

Let $b_n^k$ the number of ways to write $n$ as a product of $k$ integers $> 1$, again order matters, so $12 = 2\cdot 2\cdot 3$ and $12 = 2\cdot 3 \cdot 2$ count as two different ways, hence $b_{12}^3 = 3$.

Then, for $n > 1$, you have

$$a_n = \sum_{k = 1}^m \binom{m}{k} b_n^k,$$

and $a_1 = b_1^0 = 1$. (The binomial coefficients comes from the $\binom{m}{k}$ possible choices of the factors $> 1$.)

The coefficient of $x^n$ in

$$\sum_{\substack{a_i \geqslant 2\\1 \leqslant i \leqslant k}} x^{a_1\cdot \dotsb a_k}$$

is $b_n^k$.

Answer 2

There are several processes to do this. One of those is induction method. See, $(\zeta(s))^m=(\zeta(s))^{m-1}\zeta(s)$. So if $(\zeta(s))^k=\displaystyle\sum_{n=1}^{\infty}\frac{a_k(n)}{n^s}$, Dirichlet convolution gives $a_{k+1}(n)=\displaystyle\sum_{d|n}a_k(d)$.

Now, you have $\sum \limits_{n=1}^{\infty} a_k(n)x^n = x + {m \choose 1}\sum \limits_{a=2}^{\infty} x^{a} + {m \choose 2}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} x^{ab} +...$. So for generating series of $(\zeta(s))^{k+1}$ will be $\sum \limits_{n=1}^{\infty} a_{k+1}(n)x^n=\sum\limits_{n=1}^{\infty}x^n\sum_{d|n}a_k(d)$ and your result followes from this.

Other thing you can do the following:

Combinatorially think if $(\zeta(s))^k=(\sum_{n=1}^{\infty}\frac{1}{n^s})^k=\sum_{n=1}^{\infty}\frac{a_k(n)}{n^s}$ where $a_k(n)=d_k(n):=\#\{(a_1, a_2,..,a_k):a_1a_2...a_k=n, a_i\in\mathbb{N}\}$.

Now, in $a_1a_2...a_k$ choose any $r$ of them and make them $1$, and rest $k-r$ will be bigger that $1$. So if $t_r(n)=\#\{(a_1, a_2,..,a_k):a_1a_2...a_k=n, a_i\geq2\}$ then $d_k(n)=\sum\limits_{r=0}^{k}{{k}\choose{r}}t_r(n)$.

So, $\displaystyle\sum_{n=1}^{\infty}a_k(n)x^n=\sum\limits_{r=0}^{k}{{k}\choose{r}}\displaystyle\sum_{n=1}^{\infty}t_r(n)x^n$.

Note that, $\sum_{n=1}^{\infty}t_r(n)x^n=\displaystyle\sum_{2\leq i_1,i_2,...,i_r \leq n}x^{i_1i_2...i_r}$. And thus your result followes.

Answer 3

I am the person who wrote it there in wikipedia. You are right that this can be proved by elementary methods.

From the chapter on Taylor series and in particular binomial series in Murray R. Spiegels Mathematical Handbook (Schaum's Outlines), we have the formula:

$$(a+x)^m = a^m + {m \choose 1} a^{n-1}x^1 + {m \choose 2} a^{n-2}x^2 + {m \choose 3} a^{n-3}x^3 + {m \choose 4} a^{n-4}x^4+\cdots$$

First we set $a=1$ and get:

$$(1+x)^m = 1^m + {m \choose 1} 1^{n-1}x^1 + {m \choose 2} 1^{n-2}x^2 + {m \choose 3} 1^{n-3}x^3 + {m \choose 4} 1^{n-4}x^4+\cdots$$

which simplifies to:

$$(1+x)^m = 1 + {m \choose 1} x^1 + {m \choose 2} x^2 + {m \choose 3} x^3 + {m \choose 4} x^4+\cdots$$

then we set $x=\zeta(s)$ and get:

$$(1+\zeta(s))^m = 1 + {m \choose 1} \zeta(s)^1 + {m \choose 2} \zeta(s)^2 + {m \choose 3} \zeta(s)^3 + {m \choose 4} \zeta(s)^4+\cdots$$

substitute $\zeta(s) = \zeta(s) - 1$:

$$(1+\zeta(s)-1)^m = 1 + {m \choose 1} (\zeta(s)-1)^1 + {m \choose 2} (\zeta(s)-1)^2 + {m \choose 3} (\zeta(s)-1)^3 + {m \choose 4} (\zeta(s)-1)^4+\cdots$$

which simplifies to:

$$\zeta(s)^m = 1 + {m \choose 1} (\zeta(s)-1)^1 + {m \choose 2} (\zeta(s)-1)^2 + {m \choose 3} (\zeta(s)-1)^3 + {m \choose 4} (\zeta(s)-1)^4+\cdots$$

Where: $$\zeta(s)=1+\frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\frac{1}{5^s}+\cdots+\frac{1}{n^s}$$

and:

$$\zeta(s) - 1 = \frac{1}{2^s}+\frac{1}{3^s}+\frac{1}{4^s}+\frac{1}{5^s}+\cdots+\frac{1}{n^s}$$

Interested in the power series we write: $$\sum\limits_{n=1}^{\infty} \frac{x^n}{n} = x^1+\frac{x^2}{2^s}+\frac{x^3}{3^s}+\frac{x^4}{4^s}+\frac{x^5}{5^s}+\cdots+\frac{x^n}{n^s}$$

and:

$$\sum\limits_{n=1}^{\infty} \frac{x^n}{n} - x^1 = \frac{x^2}{2^s}+\frac{x^3}{3^s}+\frac{x^4}{4^s}+\frac{x^5}{5^s}+\cdots+\frac{x^n}{n^s}$$

which is equal to:

$$\sum\limits_{n=2}^{\infty} \frac{x^n}{n} = \frac{x^2}{2^s}+\frac{x^3}{3^s}+\frac{x^4}{4^s}+\frac{x^5}{5^s}+\cdots+\frac{x^n}{n^s}$$

Now for a moment consider that the sum of the number of divisors of $n$, $\tau$ (tau), which is a sequence starting: $$1, 2, 2, 3, 2, 4, 2, 4, 3, 4, 2, 6, 2, 4, 4, 5, ...$$

This sequence is the row sums of the following matrix:

which is equal to a black square if the column index divides the row index.

Represented as a zero-one matrix we write $1$ if the column index divides the row index, and $0$ if it doesn't, as follows:

$$\mathbf{A} = \left( \begin{array}{cccccccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$$

Squaring the matrix $\mathbf{A}$ through matrix multiplication we write:

$$\mathbf{A}\mathbf{A}=\left( \begin{array}{cccccccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 2 & 2 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 3 & 0 & 2 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 2 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 6 & 4 & 3 & 2 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 4 & 2 & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 4 & 0 & 2 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 5 & 4 & 0 & 3 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$$

Which appears to be equal to $\tau(n/k)$ if $k$ divides $n$ and $0$ if it doesn't, and we know that $\tau$ has the Dirichlet generating function $\zeta(s)^2$

Looking for $(\zeta(s)-1)^1,(\zeta(s)-1)^2,(\zeta(s)-1)^3,(\zeta(s)-1)^4,...$ we subtract $\mathbf{A}$ with the identity matrix $\mathbf{I}$:

$$\mathbf{I}=\left( \begin{array}{cccccccccccccccc} 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array} \right)$$

and take matrix powers. We then have the following matrices:

$$(\mathbf{A}-\mathbf{I})^1=\left( \begin{array}{cccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right)$$ $$(\mathbf{A}-\mathbf{I})^2 = \left( \begin{array}{cccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 4 & 2 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 2 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right)$$ $$(\mathbf{A}-\mathbf{I})^3 = \left( \begin{array}{cccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right)$$ $$(\mathbf{A}-\mathbf{I})^4=\left( \begin{array}{cccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right)$$

The first column in each of these matrices have Dirichlet generating functions as below: $$\text{First column of } (\mathbf{A}-\mathbf{I})^0 \text{ has Dirichlet generating function } (\zeta(s)-1)^0$$ $$\text{First column of } (\mathbf{A}-\mathbf{I})^1 \text{ has Dirichlet generating function } (\zeta(s)-1)^1$$ $$\text{First column of } (\mathbf{A}-\mathbf{I})^2 \text{ has Dirichlet generating function } (\zeta(s)-1)^2$$ $$\text{First column of } (\mathbf{A}-\mathbf{I})^3 \text{ has Dirichlet generating function } (\zeta(s)-1)^3$$ $$\text{First column of } (\mathbf{A}-\mathbf{I})^4 \text{ has Dirichlet generating function } (\zeta(s)-1)^4$$

Then we make the observation that the first column in the matrix powers $(\mathbf{A}-\mathbf{I})^n$ is the row sums of the previous matrix power $(\mathbf{A}-\mathbf{I})^{(n-1)}$, starting always from the second column. This means that when we look at the power series of it all we have for $(\mathbf{A}-\mathbf{I})$ the matrix:

$$\left( \begin{array}{cccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^4 & x^4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^5 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^6 & x^6 & x^6 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^7 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^8 & x^8 & 0 & x^8 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^9 & 0 & x^9 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^{10} & x^{10} & 0 & 0 & x^{10} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^{11} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^{12} & x^{12} & x^{12} & x^{12} & 0 & x^{12} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^{13} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^{14} & x^{14} & 0 & 0 & 0 & 0 & x^{14} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^{15} & 0 & x^{15} & 0 & x^{15} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ x^{16} & x^{16} & 0 & x^{16} & 0 & 0 & 0 & x^{16} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right)$$

and for the second power $(\mathbf{A}-\mathbf{I})^2$ the following expression:

$$\left( \begin{array}{ccccc} +x^4 & +x^6 & +x^8 & +x^{10} \\ +x^6 & +x^9 & +x^{12} & +x^{15} \\ +x^8 & +x^{12} & +x^{16} & +x^{20} \\ +x^{10} & +x^{15} & +x^{20} & +x^{25} \\ \cdots \end{array}\cdots \right)$$

which is equal to: $$\sum\limits_{a=2}^{\infty}\sum\limits_{b=2}^{\infty} x^{ab}$$

Now for due the property of generating functions that when multiplying the exponenent with a number we get a stretched out interleaved sequence and therefore $\sum\limits_{a=2}^{\infty}\sum\limits_{b=2}^{\infty}\sum\limits_{c=2}^{\infty} x^{abc}$ is the sum that corresponds to $(\zeta(s)-1)^3$

This is not very clearly said.

Following this logic of multiple sums from $n$-dimensional Cayley tables we get the final formula:

$$\sum \limits_{n=1}^{\infty} a_nx^n = x + {m \choose 1}\sum \limits_{a=2}^{\infty} x^{a} + {m \choose 2}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} x^{ab} + {m \choose 3}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} \sum \limits_{c=2}^{\infty} x^{abc} + {m \choose 4}\sum \limits_{a=2}^{\infty} \sum \limits_{b=2}^{\infty} \sum \limits_{c=2}^{\infty} \sum \limits_{d=2}^{\infty} x^{abcd} +...$$

$\square$

---

Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld lecture notes on generating functions.

Update 17.8.2017:

The exact equality is: $$\sum_{k=1}^{k=n} a_k x^k = x - {m \choose 1} \sum_{2 \leq a \leq n} x^{a} + {m \choose 2}\underset{ab \leq n}{\sum_{a \geq 2} \sum_{b \geq 2}} x^{ab} - {m \choose 3}\underset{abc \leq n}{\sum_{a \geq 2} \sum_{c \geq 2} \sum_{b \geq 2}} x^{abc} + {m \choose 4}\underset{abcd \leq n}{\sum_{a \geq 2} \sum_{b \geq 2} \sum_{c \geq 2} \sum_{d \geq 2}} x^{abcd} - \cdots$$