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
,
Previous Page Next Page