223 pdfsam Graham, Knuth, Patashnik Concrete Mathematics

5.5 HYPERGEOMETRIC FUNCTIONS 209 looks like in hypergeometric notation. We need to write the sum as an infinite series ...

0 downloads 46 Views 18KB Size
5.5 HYPERGEOMETRIC FUNCTIONS 209

looks like in hypergeometric notation. We need to write the sum as an infinite series that starts at k = 0, so we replace k by n - k: r+n-k n - k

E x (r+n-k)! k,O r! (n - k)!

=

tk x

/

k>O

.

This series is formally infinite but actually finite, because the (n - k)! in the denominator will make tk = 0 when k > n. (We’ll see later that l/x! is defined for all x, and that l/x! = 0 when x is a negative integer. But for now, let’s blithely disregard such technicalities until we gain more hypergeometric experience.) The term ratio is (r+n-k-l)!r!(n-k)! = r!(n-k-l)!(r+n-k)! tk tk+l

n - k = r+n-k (k+ l)(k-n)(l)

= (k-n-r)(k+ 1) Furthermore to = (“,“). Hence the parallel summation law is equivalent to the hypergeometric identity ("n")r(:l+il)

= (r+,,').

Dividing through by (“,“) g’Ives a slightly simpler version, (5.82)

Let’s do another one. The term ratio of identity (5.16), integer m, is (k-m)/(r-m+k+l) =(k+l)(k-m)(l)/(k-m+r+l)(k+l), we replace k by m - k; hence (5.16) gives a closed form for

First derangements, now degenerates.

after

This is essentially the same as the hypergeometric function on the left of (5.82), but with m in place of n and r + 1 in place of -r. Therefore identity (5.16) could have been derived from (5.82), the hypergeometric version of (5.9). (No wonder we found it easy to prove (5.16) by using (5.g).) Before we go further, we should think about degenerate cases, because hypergeometrics are not defined when a lower parameter is zero or a negative