7.1 DOMINO THEORY AND CHANGE 315 How many pennies
are there, really?
If n is greater than, say, 10”) I bet that P, = 0 in the “real world.”
Obviously P, = 1 for all n 3 0. And a little thought proves that we have N, = Ln/5J + 1: To make n cents out of pennies and nickels, we must choose either 0 or 1 or . . . or Ln/5] nickels, after which there’s only one way to supply the requisite number of pennies. Thus P, and N, are simple; but the values of Dn, Qn, and C, are increasingly more complicated. One way to deal with these formulas is to realize that 1 + zm + 2’“’ +. . . is just l/(1 - 2”‘). Thus we can write P
= l/(1 -2’1,
N
=
P/(1 -i’),
D = N/(1 - 2”) , Q = D/(1 - zz5) , C
=
Q/(1 -2”).
Multiplying by the denominators, we have (l-z)P = 1 , (1 -z5)N = P, (l-z”)D = N , (~-z~~)Q = D , (1-z5’)C = Q .
Now we can equate coefficients of 2” in these equations, getting recurrence relations from which the desired coefficients can quickly be computed: P, = P,-I + [n=O] , N, =
N-5
+ P,,
D, = Dn-IO
-tN,,
Qn = Cn =
-t D,, + Qn.
Qn-25 G-50
For example, the coefficient of Z” in D = (1 - z~~)Q is equal to Q,, - Qnp25; so we must have Qll - Qnp25 = D,, as claimed. We could unfold these recurrences and find, for example, that Qn = D,+D,-zs+Dn~5o+Dn~75+..., stopping when the subscripts get negative. But the non-iterated form is convenient because each coefficient is computed with just one addition, as in Pascal’s triangle. Let’s use the recurrences to find Csc. First, Cso = CO + Q50; so we want to know Qso. Then Q50 = Q25 + D50, and Q25 = QO + D25; so we also want to know D50 and 1125. These D, depend in turn on DUO, DUO, DUO, D15, DIO, D5, and on NSO, NC,, . . . , Ns. A simple calculation therefore suffices to
