TAOCP 4.7 Exercise 28
Let V(s)=\sum_{n\ge1}\frac{V_n}{n^s}, \qquad W(s)=\sum_{n\ge1}\frac{W_n}{n^s}.
Section 4.7: Manipulation of Power Series
Exercise 28. ▶ [**] [M26] A Dirichlet series is a sum of the form $V(z) = V_1/1^z + V_2/2^z + V_3/3^z + \cdots$; the product $U(z)V(z)$ of two such series is the Dirichlet series $W(z)$ where
$$W_n = \sum_{d \mid n} U_d V_{n/d}.$$
Ordinary power series are special cases of Dirichlet series, since we have $V_0 + V_1 z + V_2 z^2 + V_3 z^3 + \cdots = V_0/1^s + V_1/2^s + V_2/4^s + V_3/8^s + \cdots$ when $z = 2^{-s}$. In fact, Dirichlet series are essentially equivalent to power series $V(z_1, z_2, \ldots)$ in arbitrarily many variables, where $z_k = p_k^{-s}$ and $p_k$ is the $k$th prime number.
Find recurrence relations that generalize (q) and the formulas of exercise 4, assuming that a Dirichlet series $V(z)$ is given and that we want to calculate (a) $W(z) = V(z)^n$ when $V_1 = 1$; (b) $W(z) = \exp V(z)$ when $V_1 = 0$; (c) $W(z) = \ln V(z)$ when $V_1 = 1$. [Hint: Let $t(n)$ be the total number of prime factors of $n$, including multiplicity, and let $\delta \sum_n V_n/n^s = \sum_n t(n) V_n/n^s$. Show that $\delta$ is analogous to a derivative; for example, $\delta e^{V(z)} = e^{V(z)} \delta V(z)$.]
It seems impossible that any thing should really alter the series of things, without the same power which first produced them., EDWARD STILLINGFLEET, Origines Sacræ, 2:3:2 (1662)
This business of series, the most disagreeable thing in mathematics, is no more than a game for the English; Stirling's book, and the one by de Moivre, are proof., PIERRE DE MAUPERTUIS, letter to d'Ortous de Mairan (30 Oct 1730)
He was daunted and bewildered by their almost infinite series., G. K. CHESTERTON, The Man Who Was Thursday (1907)
Verified: yes
Solve time: 3m54s
Let
$$ V(s)=\sum_{n\ge1}\frac{V_n}{n^s}, \qquad W(s)=\sum_{n\ge1}\frac{W_n}{n^s}. $$
Dirichlet multiplication is defined by
$$ (UV)n=\sum{d\mid n}U_dV_{n/d}. $$
Let $t(n)$ denote the total number of prime factors of $n$, counted with multiplicity, and define
$$ \delta!\left(\sum_{n\ge1}\frac{A_n}{n^s}\right) = \sum_{n\ge1}\frac{t(n)A_n}{n^s}. $$
Since $t(ab)=t(a)+t(b)$, we have
$$ \delta(UV) = (\delta U)V+U(\delta V). $$
Indeed,
$$ \begin{aligned} \delta(UV) &= \sum_n \frac{t(n)}{n^s} \sum_{d\mid n}U_dV_{n/d} \ &= \sum_n\frac1{n^s} \sum_{d\mid n} \bigl(t(d)+t(n/d)\bigr) U_dV_{n/d}, \end{aligned} $$
which is exactly $(\delta U)V+U(\delta V)$.
Hence all formal identities obtained from the Leibniz rule remain valid. In particular,
$$ \delta(V^m)=mV^{m-1}\delta V, $$
$$ \delta(e^V)=e^V,\delta V, $$
$$ \delta(\log V)=\frac{\delta V}{V}. $$
Write
$$ A=\delta V = \sum_{n\ge1}\frac{a_n}{n^s}, \qquad a_n=t(n)V_n. $$
Also let
$$ B=\delta W = \sum_{n\ge1}\frac{t(n)W_n}{n^s}. $$
The coefficient of $n^{-s}$ in a Dirichlet product $XY$ is
$$ (XY)n=\sum{d\mid n}X_dY_{n/d}. $$
We now derive the requested recurrences.
(a) $W=V^m$, with $V_1=1$
From
$$ \delta W=mW\delta V $$
we obtain
$$ B=mWA. $$
Comparing coefficients of $n^{-s}$,
$$ t(n)W_n = m\sum_{d\mid n}W_d,a_{n/d}. $$
Since $a_1=t(1)V_1=0$, the term $d=n$ vanishes. Therefore, for $n>1$,
$$ \boxed{ W_n = \frac{m}{t(n)} \sum_{\substack{d\mid n\ d<n}} W_d,t(n/d)V_{n/d}. } $$
Together with
$$ W_1=1, $$
this determines all coefficients recursively, because every proper divisor $d<n$.
This is the Dirichlet-series analogue of recurrence (q) for powers.
(b) $W=e^V$, with $V_1=0$
From
$$ \delta W=W\delta V $$
we have
$$ B=WA. $$
Hence
$$ t(n)W_n = \sum_{d\mid n}W_d,a_{n/d}. $$
Again $a_1=t(1)V_1=0$, so the term $d=n$ disappears. Thus for $n>1$,
$$ \boxed{ W_n = \frac1{t(n)} \sum_{\substack{d\mid n\ d<n}} W_d,t(n/d)V_{n/d}. } $$
Since $W_1=e^{V_1}=1$, the recurrence starts from
$$ W_1=1. $$
This is the analogue of the exponential recurrence of Exercise 4.
(c) $W=\log V$, with $V_1=1$
We have
$$ \delta W=\frac{\delta V}{V}. $$
Equivalently,
$$ V,\delta W=\delta V. $$
Comparing coefficients,
$$ \sum_{d\mid n}V_d,t(n/d)W_{n/d} = a_n = t(n)V_n . $$
For $n=1$, both sides are $0$, giving $W_1=0$.
For $n>1$, isolate the term $d=1$:
$$ t(n)W_n + \sum_{\substack{d\mid n\ d>1}} V_d,t(n/d)W_{n/d} = t(n)V_n. $$
Therefore
$$ \boxed{ W_n = V_n - \frac1{t(n)} \sum_{\substack{d\mid n\ d>1}} V_d,t(n/d)W_{n/d}, \qquad n>1. } $$
Together with
$$ W_1=0, $$
this recursively determines the coefficients of $\log V$.
Thus the Dirichlet-series analogues of the ordinary power-series recurrences are
$$ \boxed{ W_n = \frac{m}{t(n)} \sum_{\substack{d\mid n\ d<n}} W_d,t(n/d)V_{n/d} \quad (W=V^m), } $$
$$ \boxed{ W_n = \frac1{t(n)} \sum_{\substack{d\mid n\ d<n}} W_d,t(n/d)V_{n/d} \quad (W=e^V), } $$
and
$$ \boxed{ W_n = V_n - \frac1{t(n)} \sum_{\substack{d\mid n\ d>1}} V_d,t(n/d)W_{n/d} \quad (W=\log V). } $$
These follow from the fact that $\delta$ is a derivation for Dirichlet multiplication, exactly as ordinary differentiation is a derivation for ordinary power series.