Comment on ‘Automatic Central Limit Theorems ...’

Herb Wilf

March 27, 2009

1 Better recurrence

Recall that some years ago you were overly generous and credited Nijenhuis and myself with inventing the algorithm for raising a power series to the nth power, that appears in our book Combinatorial Algorithms. We pointed out that it was known long before us, and Don Knuth traced it back to the Neanderthals. Anyway that same algorithm gives a somewhat simpler recurrence for your f_{r}(n)’s in this paper.

In fact, if

(∑_{r≥0} \frac{F_{r}}{r!} z^{r})^{n} = ∑_{r≥0} \frac{f_{r}(n)}{r!}z^{r},

then by logarithmic differentiation and matching coefficients one finds that

f_{r}(n) = ∑_{0≤j<r} (n\binom{r − 1}{j} − \binom{r − 1}{j + 1}) F_{j+1}f_{r−1−j}(n),

with f_{0} = 1, f_{1} = 0, which avoids the extra step of indefinite summation that’s in your present recurrence.