238 BINOMIAL COEFFICIENTS
72 Prove that, if m, n, and k are integers and n > 0, n2k-v(k)
is an integer,
where v(k) is the number of l’s in the binary representation of k. 73 Use the repertoire method to solve the recurrence
X0 = a; x, := p; Xn = (n-1)(X,-j +X,-2),
for n > 1
Hint: Both n! and ni satisfy this recurrence.
74 This problem concerns a deviant version of Pascal’s triangle in which the sides consist of the numbers 1, 2, 3, 4, . . . instead of all l’s, although the interior numbers still satisfy the addition formula: i
1
4 G,
2 343
2
7
7
I :
i S’
4
.5 ii0v4 i/., $ l1 lb 5 .b
If ((t)) denotes the kth number in row n, for 1 < k < n, we have ((T)) = ((t)) = n, and ((L)) = ((“,‘)) + ((:I:)) for 1 < k < n. Express the quantity ((i)) in closed form. 75 Find a relation between the functions
” (n)
= ;
(31;:
1) ’
S2(n)
= 6
(Sk”,
2)
and the quantities 12”/.3J and [2n/31. 76 Solve the following recurrence for n, k 3 0:
Q n,O = 1;
Qo,k
= [k=Ol;
Q n,k = Qn-l,k + Qn-l,k-, +
for n, k > 0.
