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

,