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,and
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 √ 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 substantial 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
Bertrand's postulate 13 by comparing with the area of the large rectangles(including the lightly shaded parts).Taken together,this yields 1 logn+<Hn logn 1. In particular,lim Hnoo,and the order of growth of Hn is given by 1.But much better estimates are known (see )such as Here (denotes a function f(n) A。=ogn+y+-1 1 2n-12m2+120m+ such that f(n）≤c holds for some constant c. where y≈0.5772is“Euler's constant..” Estimating factorials-Stirling's formula The same method applied to log(n=log2+log3+…+logn=∑logk k=2 yields log(n-1)月< logt dt log(n!), where the integral is easily computed: logtdi (tlogt=nlognn+1. Thus we get a lower estimate on n! nl>enlogn-.n+1=e(g)】 and at the same time an upper estimate n!=n(n-1)!<nenlogn-n+1 en( Here a more careful analysis is needed to get the asymptotics of n!,as given by Stirling's formula Here f(n)~g(n)means that n!~V2rn（ lim fm=1. no g(n) And again there are more precise versions available,such as n!V2rn 139 12n 288m2- 5140n3+0 Estimating binomial coefficients Just from the definition of the binomial coefficients (as the number of k-subsets of an n-set,we know that the sequence (),(2),...,(n)of binomial coefficients
Bertrand’s postulate 13 by comparing with the area of the large rectangles (including the lightly shaded parts). Taken together, this yields log n + 1 n < Hn < log n + 1. In particular, limn→∞ Hn → ∞, and the order of growth of Hn is given by limn→∞ Hn log n = 1. But much better estimates are known (see [2]), such as Here O 1 n6 denotes a function f(n) such that f(n) ≤ c 1 n6 holds for some constant c. Hn = log n + γ + 1 2n − 1 12n2 + 1 120n4 + O 1 n6 , where γ ≈ 0.5772 is “Euler’s constant.” Estimating factorials — Stirling’s formula The same method applied to log(n!) = log 2 + log 3 + ··· + log n = n k=2 log k yields log((n − 1)!) < n 1 log t dt < log(n!), where the integral is easily computed: n 1 log t dt = tlog t − t n 1 = n log n − n + 1. Thus we get a lower estimate on n! n! > en log n−n+1 = e n e n and at the same time an upper estimate n! = n (n − 1)! < nen log n−n+1 = enn e n . Here a more careful analysis is needed to get the asymptotics of n!, as given by Stirling’s formula Here f(n) ∼ g(n) means that limn→∞ f(n) g(n) = 1. n! ∼ √ 2πn n e n . And again there are more precise versions available, such as n! = √ 2πn n e n 1 + 1 12n + 1 288n2 − 139 5140n3 + O 1 n4 . Estimating binomial coefficients Just from the definition of the binomial coefficients n k as the number of k-subsets of an n-set, we know that the sequence n 0 , n 1 ,..., n n of binomial coefficients
14 Bertrand's postulate ●sums to (份=2” k=0 ·is symmetric: (风)=（n”) 1 331 From the functional equation ()=)one easily finds that for 4641 15101051 every n the binomial coefficients form a sequence that is symmetric 1 615201561 and unimodal:it increases towards the middle,so that the middle binomial 172135352171 coefficients are the largest ones in the sequence: Pascal's triangle 1=(8)<(份)<…<（)=(2)>…>(n)>(份）)=1. Here x resp.[r]denotes the number z rounded down resp.rounded up to the nearest integer. From the asymptotic formulas for the factorials mentioned above one can obtain very precise estimates for the sizes of binomial coefficients.How- ever,we will only need very weak and simple estimates in this book,such as the following:()<2m for all k,while for n>2 we have n 2n n/21 n with equality only for n =2.In particular,for n>1, 2n n 器 2 This holdssince(a middle binomial coefficient is the largest eny in the sequence ()+()(),(2),..(),whose sumis 2",and whose average is thus On the other hand,we note the upper bound for binomial coefficients 2 n(n-1)…(n-k+1) nk k kI which is a reasonably good estimate for the "small"binomial coefficients at the tails of the sequence,when n is large(compared to k). References [1]P.ERDOS:Beweis eines Satzes von Tschebyschef,Acta Sci.Math.(Szeged)5 (1930-32).194-198. [2]R.L.GRAHAM,D.E.KNUTH O.PATASHNIK:Concrete Mathematics. A Foundation for Computer Science,Addison-Wesley,Reading MA 1989. [3]G.H.HARDY E.M.WRIGHT:An Introduction to the Theory of Numbers, Fifth edition,Oxford University Press 1979. [4]P.RIBENBOIM:The New Book of Prime Number Records,Springer-Verlag, New York 1989
14 Bertrand’s postulate • sums to n k=0 n k = 2n • is symmetric: n k = n n−k . From the functional equation n k = n−k+1 k n k−1 one easily finds that for every n the binomial coefficients n k form a sequence that is symmetric and unimodal: it increases towards the middle, so that the middle binomial 1 coefficients are the largest ones in the sequence: 1 1 1 1 1 1 1 1 2 3 4 5 6 7 15 10 6 3 1 1 4 10 20 35 15 5 1 1 6 7 1 21 2135 1 Pascal’s triangle 1 = n 0 < n 1 < ··· < n n/2 = n n/2 > ··· > n n−1 > n n = 1. Here x resp. x denotes the number x rounded down resp. rounded up to the nearest integer. From the asymptotic formulas for the factorials mentioned above one can obtain very precise estimates for the sizes of binomial coefficients. However, we will only need very weak and simple estimates in this book, such as the following: n k ≤ 2n for all k, while for n ≥ 2 we have n n/2 ≥ 2n n , with equality only for n = 2. In particular, for n ≥ 1, 2n n ≥ 4n 2n. This holds since n n/2 , a middle binomial coefficient, is the largest entry in the sequence n 0 + n n , n 1 , n 2 ,..., n n−1 , whose sum is 2n, and whose average is thus 2n n . On the other hand, we note the upper bound for binomial coefficients n k = n(n − 1)···(n − k + 1) k! ≤ nk k! ≤ nk 2k−1 , which is a reasonably good estimate for the “small” binomial coefficients at the tails of the sequence, when n is large (compared to k). References [1] P. ERDOS˝ : Beweis eines Satzes von Tschebyschef, Acta Sci. Math. (Szeged) 5 (1930-32), 194-198. [2] R. L. GRAHAM, D. E. KNUTH & O. PATASHNIK: Concrete Mathematics. A Foundation for Computer Science, Addison-Wesley, Reading MA 1989. [3] G. H. HARDY & E. M. WRIGHT: An Introduction to the Theory of Numbers, Fifth edition, Oxford University Press 1979. [4] P. RIBENBOIM: The New Book of Prime Number Records, Springer-Verlag, New York 1989
Binomial coefficients Chapter 3 are (almost)never powers There is an epilogue to Bertrand's postulate which leads to a beautiful re- sult on binomial coefficients.In 1892 Sylvester strengthened Bertrand's postulate in the following way: Ifn >2k,then at least one of the numbers n,n-1,...:n-k+1 has a prime divisor p greater than k. Note that for n =2k we obtain precisely Bertrand's postulate.In 1934, Erdos gave a short and elementary Book Proof of Sylvester's result,running along the lines of his proof of Bertrand's postulate.There is an equivalent way of stating Sylvester's theorem: The binomial coefficient n(m-1)(m-k+1 k (n≥2k) k! always has a prime factor p >k. With this observation in mind,we turn to another one of Erdos'jewels: When is (equal to a power m? The case k=e=2 leads to a classical topic.Multiplying (2)-m2 by 8 and rearranging terms gives(2n-1)2-2(2m)2=1,which is a special case of Pell's equation,x2-2y2=1.One learns in number theory that this equation has infinitely many positive solutions (k,y),which are given by k+kV2=(3+2√②)kfork≥l.The smallest examples are (a1,1)=(3,2),(x2,2=(17,12),and(x3,gg）=(99,70),yielding 伯=12，（份=62，and()=352. For k =3 it is known that (2)=m2 has the unique solution n=50, m 140.But now we are at the end of the line.For 4 and any e>2 no solutions exist,and this is what Erdos proved by an ingenious argument. Theorem.The equation ()=mt has no integer solutions with l≥2amd4≤k≤n-4 M.Aigner,G.M.Ziegler,Proofs from THE BOOK,DOI 10.1007/978-3-662-44205-0_3, Springer-Verlag Berlin Heidelberg 2014
Binomial coefficients are (almost) never powers Chapter 3 There is an epilogue to Bertrand’s postulate which leads to a beautiful result on binomial coefficients. In 1892 Sylvester strengthened Bertrand’s postulate in the following way: If n ≥ 2k, then at least one of the numbers n, n − 1,...,n − k + 1 has a prime divisor p greater than k. Note that for n = 2k we obtain precisely Bertrand’s postulate. In 1934, Erdos gave a short and elementary Book Proof of Sylvester’s result, running ˝ along the lines of his proof of Bertrand’s postulate. There is an equivalent way of stating Sylvester’s theorem: The binomial coefficient n k = n(n − 1)···(n − k + 1) k! (n ≥ 2k) always has a prime factor p>k. With this observation in mind, we turn to another one of Erdos’ jewels: ˝ When is n k equal to a power m? The case k = = 2 leads to a classical topic. Multiplying n 2 = m2 by 8 and rearranging terms gives (2n − 1)2 − 2(2m)2 = 1, which is a special case of Pell’s equation, x2 − 2y2 = 1. One learns in number theory that this equation has infinitely many positive solutions (xk, yk), which are given by xk + yk √2 = (3 + 2√ 2)k for k ≥ 1. The smallest examples are (x1, y1) = (3, 2), (x2, y2) = (17, 12), and (x3, y3) = (99, 70), yielding 2 2 = 12, 9 2 = 62, and 50 2 = 352. For k = 3 it is known that n 3 = m2 has the unique solution n = 50, m = 140. But now we are at the end of the line. For k ≥ 4 and any ≥ 2 no solutions exist, and this is what Erdos proved by an ingenious argument. ˝ Theorem. The equation n k = m has no integer solutions with ≥ 2 and 4 ≤ k ≤ n − 4. M. Aigner, G.M. Ziegler, Proofs from THE BOOK, DOI 10.1007/978-3-662-44205-0_3, © Springer-Verlag Berlin Heidelberg 2014
16 Binomial coefficients are (almost)never powers Proof.Note first that we may assume n 2k because of ()=() Suppose the theorem is false,and that (=m.The proof,by contra- diction,proceeds in the following four steps. (1)By Sylvester's theorem,there is a prime factor p of ()greater thank. hence pe divides n(n-1)...(n-k +1).Clearly,only one of the factors n-i can be a multiple of any such p >k,and we conclude pn-i,and therefore n≥p>k4≥k2 (2)Consider any factor n-j of the numerator and write it in the form n-j=ajm,where aj is not divisible by any nontrivial e-th power.We note by (1)that aj has only prime divisors less than or equal to k.We want to show next that ai aj for ij.Assume to the contrary that ai =aj for some i<j.Then mi>mj+1 and k>(n-i)-(m-j)=a(m-m)≥a(m+1)-m) >alm51≥am/2≥n-k+1)e ≥（受+1）1/2>n2/2, which contradicts n >k2 from above. (3)Next we prove that the ai's are the integers 1,2,...,k in some order. (According to Erdos,this is the crux of the proof.)Since we already know that they are all distinct,it suffices to prove that aoa1·ak-1 divides k!. Substituting n-j=ajm into the equation()=m,we obtain aoa1…ak-1(mom…mk-1)'=klm. Cancelling the common factors of mo...mk1 and m yields a0a1…ak-1u2=kue with gcd(u,v)=1.It remains to show that v 1.If not,then v con- tains a prime divisor p.Since gcd(u,v)=1,p must be a prime divisor of aoa1...ak1 and hence is less than or equal to k.By the theorem of Legendre (see page 8)we know that contains p to the power We now estimate the exponent of p in n(n-1)...(n-k+1).Let i be a positive integer,and let bi<b2<...<bs be the multiples of p'among n,n-1,...,n-k 1.Then bs =61+(s-1)p'and hence (s-1)p2=bs-b1≤n-(n-k+1)=k-1, which implies s≤+1≤制+1
16 Binomial coefficients are (almost) never powers Proof. Note first that we may assume n ≥ 2k because of n k = n n−k . Suppose the theorem is false, and that n k = m. The proof, by contradiction, proceeds in the following four steps. (1) By Sylvester’s theorem, there is a prime factor p of n k greater than k, hence p divides n(n − 1)···(n − k + 1). Clearly, only one of the factors n − i can be a multiple of any such p>k, and we conclude p | n − i, and therefore n ≥ p > k ≥ k2. (2) Consider any factor n − j of the numerator and write it in the form n − j = ajm j , where aj is not divisible by any nontrivial -th power. We note by (1) that aj has only prime divisors less than or equal to k. We want to show next that ai = aj for i = j. Assume to the contrary that ai = aj for some i<j. Then mi ≥ mj + 1 and k > (n − i) − (n − j) = aj (m i − m j ) ≥ aj ((mj + 1) − m j ) > aj m−1 j ≥ (ajm j ) 1/2 ≥ (n − k + 1)1/2 ≥ ( n 2 + 1)1/2 > n1/2, which contradicts n>k2 from above. (3) Next we prove that the ai’s are the integers 1, 2,...,k in some order. (According to Erdos, this is the crux of the proof.) Since we already know ˝ that they are all distinct, it suffices to prove that a0a1 ··· ak−1 divides k!. Substituting n − j = ajm j into the equation n k = m, we obtain a0a1 ··· ak−1(m0m1 ··· mk−1) = k!m . Cancelling the common factors of m0 ··· mk−1 and m yields a0a1 ··· ak−1u = k!v with gcd(u, v)=1. It remains to show that v = 1. If not, then v contains a prime divisor p. Since gcd(u, v)=1, p must be a prime divisor of a0a1 ··· ak−1 and hence is less than or equal to k. By the theorem of Legendre (see page 8) we know that k! contains p to the power i≥1 k pi . We now estimate the exponent of p in n(n − 1)···(n − k + 1). Let i be a positive integer, and let b1 < b2 < ··· < bs be the multiples of pi among n, n − 1,...,n − k + 1. Then bs = b1 + (s − 1)pi and hence (s − 1)pi = bs − b1 ≤ n − (n − k + 1) = k − 1, which implies s ≤ k − 1 pi + 1 ≤ k pi + 1.