355 pdfsam Graham, Knuth, Patashnik Concrete Mathematics

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...

0 downloads 43 Views 20KB Size
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