Page 10 -

I. The Idea of Analytic Number Theory
2
four squares becomes the statement that all of the coefficients of the
4
4 n 2
power series for 1 + z + z + ··· + z + ··· are positive. How
one proves such a fact about the coefficients of such a power series
is another story, but at least one begins to see how this transition
from integers to analytic functions takes place. But now let’s look at
some addition problems that we can solve completely by the analytic
method.

Change Making

How many ways can one make change of a dollar? The answer is
293, but the problem is both too hard and too easy. Too hard because
the available coins are so many and so diverse. Too easy because it
concerns just one “changee,” a dollar. More fitting to our spirit is the
following problem: How many ways can we make change for n if the
coins are 1, 2, and 3? To form the appropriate generating function,
let us write, for |z| < 1,

1
1 + z + z 1+1 + z 1+1+1 + ··· ,
1 − z
1
2
1 + z + z 2+2 + z 2+2+2 + ··· ,
1 − z 2
1
3
1 + z + z 3+3 + z 3+3+3 + ··· ,
1 − z 3
and multiplying these three equations to get
1
3
2
(1 − zð( 1 − z )(1 − z )
2
(1 + z + z 1+1 + ···)(1 + z + z 2+2 + ···)
3
× (1 + z + z 3+3 + ···).
Now we ask ourselves: What happens when we multiply out the
2
right-hand side? We obtain terms like z 1+1+1+1 · z · z 3+3 . On the one
12

hand, this term is z , but, on the other hand, it is z four1 s+one2+two3 s
and doesn’t this exactly correspond to the method of changing the
amount 12 into four 1’s, one 2, and two 3’s? Yes, and in fact we