TAOCP 2.3.4.4 Exercise 2

Exercise 2. [**] [HM24] (R. Otter.) Show that the numbers $a_n$ satisfy the following condition:

$$ na_{n+1}=a_1s_{n1}+2a_2s_{n2}+\cdots+na_ns_{nn}, $$

where

$$ s_{nk}=\sum_{1\le j\le n/k}a_{n+1-jk}. $$

(These formulas are useful for the calculation of the $a_n$, since $s_{nk}=s_{(n-k)k}+a_{n+1-k}$.)

Verified: yes
Solve time: 4m11s

From exercise 1, write

$$ A(z)=z,e^{C(z)},\qquad C(z)=\sum_{k\ge1}\frac{A(z^k)}{k}. $$

Taking logarithmic derivatives gives

$$ \frac{A'(z)}{A(z)} =\frac1z+C'(z) =\frac1z+\sum_{k\ge1}z^{k-1}A'(z^k), $$

since

$$ \frac{d}{dz}\frac{A(z^k)}k=z^{k-1}A'(z^k). $$

Hence

$$ zA'(z) = A(z)\left(1+\sum_{k\ge1}z^kA'(z^k)\right). $$

The coefficient of $z^{,n+1}$ on the left is $(n+1)a_{n+1}$. On the right it is

$$ a_{n+1} +\sum_{k\ge1}\sum_{j\ge1} j,a_j,a_{,n+1-jk}, $$

because

$$ z^kA'(z^k) = \sum_{j\ge1}j,a_j,z^{jk}. $$

Therefore

$$ na_{n+1} = \sum_{k\ge1}\sum_{j\ge1} j,a_j,a_{,n+1-jk}. $$

Interchanging the order of summation,

$$ na_{n+1} = \sum_{j=1}^{n} j,a_j \sum_{1\le k\le n/j} a_{,n+1-jk}. $$

Since

$$ s_{nj} = \sum_{1\le k\le n/j} a_{,n+1-jk}, $$

this becomes

$$ na_{n+1} = a_1s_{n1} +2a_2s_{n2} +\cdots +na_ns_{nn}, $$

which is the desired relation. ∎