Page 12 -

I. The Idea of Analytic Number Theory
4
and
1 d 1 d n + 1 n
z
(1 − zð 3 dz 2(1 − zð 2 dz 2
(n + 2)(n + 1)
n
z ,
2
(n + 2)(n + 1) n + 1 χ 1 (n) χ 2 (n)
C(n) + + + (2)
12 4 4 3
where χ 1 (n) 1if2 | n and 0 otherwise; χ 2 (n) 1if3 | n
and 0 else. A somewhat cumbersome formula, but one which can
be shortened nicely into

n 2 n
C(n) + + 1 ; (3)
12 2
where the terms in the brackets mean the greatest integers.
A nice crisp exact formula, but these are rare. Imagine the mess
that occurs if the coins were the usual coins of the realm, namely 1, 5,
10, 25, 50, (100?). The right thing to ask for then is an “asymptotic”
formula rather than an exact one.
Recall that an asymptotic formula F(n) for a function f (n) is one
f (n)
for which lim n→∞ 1. In the colorful language of E. Landau,
F(n)
the relative error in replacing f (n) by F(n) is eventually 0%. At
any rate, we write f (n) ∼ F(n) when this occurs. One famous such
√
) . (Also note that our
example is Stirling’s formula n! ∼ 2πè( n n
e
n 2
result (3) can be weakened to C(n) ∼ .)
12
So let us assume quite generally that there are coins a 1 , a 2 , a 3 , ...,
a k , where to avoid trivial congruence considerations we will require
that there be no common divisiors other than 1. In this generality we
ask for an asymptotic formula for the corresponding C(n). As before
we find that the generating function is given by

1
n
C(n)z . à 4)
(1 − z )(1 − z ) ··· (1 − z )
a 2
a k
a 1
But the next step, explicitly finding the partial fractional decompo-
sition of this function is the hopeless task. However, let us simply
look for one of the terms in this expansion, the heaviest one. Thus