1.9. The Stirling formula 11
1.8. The density of a set of integers
Intuitively, it makes sense to say that half of the positive integers are even,
while a third are a multiple of 3. Hence, it would be reasonable to say that
the density of the subset of even integers is
1
2
, compared with
1
3
for the set of
positive integers which are a multiple of 3. Let us now make this definition
of density more rigorous. We will say that a subset A of N has density (or
asymptotic density) δ, where 0 ≤ δ ≤ 1, if the proportion of elements of A
among all natural numbers from 1 to N is asymptotic to δ as N → ∞.
More formally, A ⊂ N has density δ if
lim
N→∞
1
N
n≤N
n∈A
1 = δ.
For example, one easily checks that the set of positive integers which are
a multiple of the positive integer k is
1
k
. Also, given the integers a and b
with 0 ≤ b a and setting A = {n ∈ N : n ≡ b (mod a)}, it is easy to prove
that the density of A is equal to
1
a
. Moreover, one can easily show that it
follows from the Prime Number Theorem that the set of prime numbers is
of zero density.
Finally, there exist subsets of N which do not have a density. For exam-
ple, consider the function f : N → {0, 1} which is defined by f(1) = 1 and,
for each integer n ≥ 2 by
f(n) =
1 if
22m
n ≤
22m+1,
0 if 22m+1 n ≤ 22m+2.
One can easily show that the set {n ∈ N : f(n) = 1} has no density (see
Problem 1.10).
We will study more extensively the notion of asymptotic density in Sec-
tion 7.5 of Chapter 7.
1.9. The Stirling formula
Before proving the Stirling formula n! ∼
nne−n
√
2πn (as n → ∞), it is
interesting to mention its weak form
(1.12) n!
n
e
n
,
