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