7.5 Beta use it’s so
CONVOLUTIONS
This seems almost too good to be true. But it checks, at least when n = 2:
harmonic.
=
(T+;+3)(r+:+3+r+j+2)
Special cases like s .= 0 are as remarkable as the general case. And there’s more. We can use the convolution identity
& (‘:“)(“fn”*k)
= (r+y+‘)
to transpose H, to t,he other side, since H, is independent of k: ; (r;k)(s;:;k)Hr+~
= (I+sfn+‘)(Hr+rni~ -H,+,+, +H,). There’s still more: If r and s are nonnegative integers 1 and m, we can replace (‘+kk) by (‘I”) and (“‘,“i”) by (‘“‘,“Pk); then we can change k to k- 1 and n to n - m - 1, gett,ing
integers 1, m, n 3 0.
(7.63)
Even the special case 1= m = 0 of this identity was difficult for us to handle in Chapter 2! (See (2.36).) We’ve come a long way. Example 3: Convolutions of convolutions. If we form the convolution of (fn) and (g,,), then convolve this with a third sequence (h,), we get a sequence whose nth term is
j+k+l=n
The generating function of this three-fold convolution is, of course, the threefold product F(z) G(z) H(z). In a similar way, the m-fold convolution of a sequence ( gn) with itself has nth term equal to x
gk,
gkl
... gk,
kl +kr+...+k,=n
and its generating function is Go.
341