Multi-Page Printing

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 ,