Page 11 -

3
Change Making
see that “every” way of making change (into 1’s, 2’s, and 3’s) for
“every” n will appear in this multiplying out. Thus if we call C(n) the
number of ways of making change for n, then C(n) will be the exact
n
coefficient of z when the multiplication is effected. (Furthermore
all is rigorous and not just formal, since we have restricted ourselves
to |z| < 1 wherein convergence is absolute.)
Thus

1
n
C(n)z , à 1)
3
2
(1 − zð( 1 − z )(1 − z )
and the generating function for our unknown quantity C(n) is
produced. Our number theoretic problem has been translated into
a problem about analytic functions, namely, finding the Taylor
coefficients of the function 1 3 .
2
(1−zð( 1−z )(1−z )
Fine.Awelldefinedanalyticproblem,buthowtosolveit?Wemust
resist the temptation to solve this problem by undoing the analysis
which led to its formulation. Thus the thing not to do is expand 1 ,
1−z
1 1 z , z , z and multiply only to
3c
a
2b
1−z 2 , 1−z 3 respectively into
discover that the coefficient is the number of ways of making change
for n.
The correct answer, in this case, comes from an algebraic tech-
nique that we all learned in calculus, namely partial fractions. Recall
that this leads to terms like A k for which we know the expan-
(1−αz)
sion explicitly (namely, 1 k is just a constant times the (k − 1)th
(1−αz)
n n

derivative of 1 α z ).
(1−αz)
Carrying out the algebra, then, leads to the partial fractional
decomposition which we may arrange in the following form:
1
2
3
(1 − zð( 1 − z )(1 − z )
1 1 1 1 1 1 1 1
+ + + .
2
3
6 (1 − zð 3 4 (1 − zð 2 4 (1 − z ) 3 (1 − z )
Thus, since
1 d 1 d n n
z (n + 1)z
(1 − zð 2 dz 1 − z dz