7.6 EXPONENTIAL GENERATING FUNCTIONS 353
And the latter sumI is a geometric progression, so there’s a closed form S(z,n)
(7.77)
= $+.
All we need to do is figure out the coefficients of this relatively simple function, and we’ll know S,i:n), because S,(n) = m! [z”‘]S(z,n). Here’s where 13ernoulli numbers come into the picture. We observed a moment ago that t.he egf for Bernoulli numbers is
hence we can write enz-1 B(z) z
S(z) = =
(
Bo~.+B,~+Bz~+...)(n~+n2~+n3~+-..)
The sum S,(n) is m! times the coefficient of z”’ in this product. For example,
So(n)
=
O!
S(n)
= 1!
n;
(h3&)
(
nL
n
Elom+Blm
>
= .!n2-d-n;
f%(n) = .2! (Bo$. . + B1 & + B2 &) = in3-tn2+in. . . *. We have therefore derived the formula 0, = Sz(n) = $n(n - i)(n - 1) for the umpteenth time, and this was the simplest derivation of all: In a few lines we have found the general behavior of S,(n) for all m. The general fo:rmula can be written
%-l(n) = &EL,(n) - B,(O)) ,
(7.78)
where B,(x) is the Bernoulli polynomial defined by B,(x) = t
(;)BkX-‘.
(7.79)
k
Here’s why: The Bernoulli polynomial is the binomial convolution of the sequence (Bo, B1, B;r, . . . ) with (1, x,x2,. . . ); hence the exponential generating
