A ANSWERS TO EXERCISES 521
times 2 divides k!. A prime p that does not divide n must divide the prodn) 1at eas tas often as it divides k!, because uc;-tL;)-n)...(m-(k-l) . ..(m-(p’-1)n )’ 1s a multiple of p’ for all r 3 1 and all m. 5.73 Plugging in X, = n! yields OL = fi = 1; plugging in X, = ni yields K = 1, 6 = 0. Therefore the general solution is X, = olni + b(n! - ni). 5.74
(“l’) - (;I:), for 1 6 k 6 n.
5 . 7 5 Therecurrenc:e Sk(n+l) = Sk(n)+Sik I~ ) mod 3 (n) makes it possible to verify inductively th’at two of the S’s are equal and that .S-,I mod3(n) differs from them by (-1)“. These three values split their sum So(n) + S1 (n) + .Sz(n) = 2n as equally as possible, so there must be 2” mod 3 occurrences of [2”/31 and 3 - (2” mod 3) occurrences of 12”/3J. 5.76
Qn,k = (n f 1 l(c) + (kn+,)’
5.77 The terms are zero unless kl 6 .. < k,, when the product is the multinomial coefficient km kl, kz kl, . . . , k, - k,pl > ’ ( Therefore the sum over kl , . . . , k,-l is mkm , and the final sum over k, yields ( mn+’ - l ) / ( m - 1 ) . 5.78 Extend the sum to k = 2m2 + m - 1; the new terms are (1) + (‘,) + ...-t (1;‘) = 0. Since m I (2m+ l), the pairs (kmod m,kmod (2m-t 1)) are distinct. Furthermore, the numbers (2j + 1) mod (2m+ 1) as j varies from 0 to 2m are the numbers 0, 1, . . . , 2m in some order. Hence the sum is
5.79 (a) The sum is 22np’, so the gcd must be a power of 2. If n = 2kq where q is odd, (:“) is divisible by 2k+’ and not by 2k+2. Each (:$) is divisible by 2k+’ (see exercise 36), so this must be the gtd. (b) If p’ 6 n + 1 < p’+‘, we get the most radix p carries by adding k to n - k when k = p’ - 1. The number of carries in this case is r - e,(n + l), and r = e,(L(n + 1)). 5.80 5.81
First prove by induction that k! 3 (k/e)k.
Let fL,m,n(x) be the left-hand side. It is sufficient to show that we have fl,,,,(l) > 0 and tlhat f;,,,,(x) < 0 for 0 < x 6 1. The value of fl,,,,(l) is (-l)"p"p'(':~~") by (5.23), and this is positive because the binomial coefficient has exactly n - m- 1 negative factors. The inequality is true when 1 = 0, for the same reason. If 1 > 0, we have f&,+(x) = -Iftpl,m,n+l(~), which is negative by induction.
