520 ANSWERS TO EXERCISES
The infinite series converges because the terms for fixed j are dominated by a polynomial in j divided by 2j. Now sum over k, getting
Absorb the j + 1 and apply (5.57) to get the answer, 4(m+ 1). 5.67 3(2nntt52)
b y (5.26), b e c a u s e
(‘i’) = 3(y).
5.68 Using the fact that [n is even] ,
we get “(2” ’ - (,zij,)). 5 . 6 9 S i n c e (k:‘) + (‘y’) < (:) + (i) W k < 1 , t h e m i n i m u m o c c u r s when the k’s are as equal as possible. Hence, by the equipartition formula of Chapter 3, the minimum is (n mod m)
-4
-t (n - (n mod m))
b/ml 2
> $- (n mod m)L :i .
A similar result holds for any lower index in place of 2. 5.70 This is F(-n, i; 1;2); but it’s also (-2)Pn(F)F(-n, -n; i -n; i) if we r e p l a c e k b y n - k . NowF(-n,-n;i-n;:) =F(-f,-l;&n;l)byGauss’s identity (5.111). (Alternatively, F(-n,-n; i-n; i) = 2-“F(-n, i; i-n; -1) by the reflection law (5.101), and Kummer’s formula (5.94) relates this to (5.55).) The answer is 0 when n is odd, 2-“(,,y2) when n is even. (See [134, $1.21 for another derivation. This sum arises in the study of a simple search algorithm [ 1641.) 5.71
(a) S(z) = EkZO okzm-+k/(l -Z)m+Zk+’ = Zm(l -2) -“-‘A@/(1 -z)‘). (b) Here A(z) = x k20 (2,“)(-z)k/(k + 1) = (dm - 1)/2z, so we have A(z/(l -z)‘) = 1 -z. Thus S, = [z”] (z/(1 - 2))“’ = (;I;). 5.72 The stated quantity is m(m - n) . . . (m - (k - l)n)nkPYik’/k!. Any prime divisor p of n divides the numerator at least k - y(k) times and divides the denominator at most k - v(k) times, since this is the number of
