12 Bertrand's postulate One can extract even more from this type of estimates:Comparing the derivatives of both sides,one can sharpen(4)to V2-1≥1oga(2m)forn≥2， which with a little arithmetic and(3)implies 2 n P(m≥71og22n This is not that bad an estimate:the "true"number of primes in this range is roughly n/log n.This follows from the "prime number theorem,"which says that the limit lim #{p≤n:pis prime} n400 n/logn exists,and equals 1.This famous result was first proved by Hadamard and de la Vallee-Poussin in 1896;Selberg and Erdos found an elementary proof (without complex analysis tools,but still long and involved)in 1948 On the prime number theorem itself the final word,it seems,is still not in: for example a proof of the Riemann hypothesis(see page 60),one of the major unsolved open problems in mathematics,would also give a substan- tial improvement for the estimates of the prime number theorem.But also for Bertrand's postulate,one could expect dramatic improvements.In fact, the following is a famous unsolved problem: Is there always a prime between n2 and(n +1)2? For additional information see [3,p.19]and [4,pp.248,257]. Appendix:Some estimates Estimating via integrals There is a very simple-but-effective method of estimating sums by integrals (as already encountered on page 4).For estimating the harmonic numbers Hn k k=1 we draw the figure in the margin and derive from it Hn-1= by comparing the area below the graph of f(t)=(1<t n)with the area of the dark shaded rectangles,and12 Bertrand’s postulate One can extract even more from this type of estimates: Comparing the derivatives of both sides, one can sharpen (4) to √ 2n − 1 ≥ 21 4 log2(2n) for n ≥ 211, which with a little arithmetic and (3) implies P(n) ≥ 2 7 n log2(2n) . This is not that bad an estimate: the “true” number of primes in this range is roughly n/ log n. This follows from the “prime number theorem,” which says that the limit limn→∞ #{p ≤ n : p is prime} n/ log n exists, and equals 1. This famous result was first proved by Hadamard and de la Vallée-Poussin in 1896; Selberg and Erdos found an elementary proof ˝ (without complex analysis tools, but still long and involved) in 1948. On the prime number theorem itself the final word, it seems, is still not in: for example a proof of the Riemann hypothesis (see page 60), one of the major unsolved open problems in mathematics, would also give a substan￾tial improvement for the estimates of the prime number theorem. But also for Bertrand’s postulate, one could expect dramatic improvements. In fact, the following is a famous unsolved problem: Is there always a prime between n2 and (n + 1)2? For additional information see [3, p. 19] and [4, pp. 248, 257]. Appendix: Some estimates Estimating via integrals There is a very simple-but-effective method of estimating sums by integrals (as already encountered on page 4). For estimating the harmonic numbers Hn = n k=1 1 k we draw the figure in the margin and derive from it 1 1 2 n Hn − 1 = n k=2 1 k <  n 1 1 t dt = log n by comparing the area below the graph of f(t) = 1 t (1 ≤ t ≤ n) with the area of the dark shaded rectangles, and Hn − 1 n = n −1 k=1 1 k >  n 1 1 t dt = log n