MathDB
Bertrand and Prime Counting

Source: IrMO 1989 Paper 2 Problem 5

September 29, 2017
number theory

Problem Statement

(i): Prove that if nn is a positive integer, then (2nn)=(2n)!(n!)2\binom{2n}{n}=\frac{(2n)!}{(n!)^2} is a positive integer that is divisible by all prime numbers pp with n<p≤2nn<p\le 2n, and that (2nn)<22n.\binom{2n}{n}<2^{2n}.
(ii): For xx a positive real number, let π(x)\pi(x) denote the number of prime numbers p≤xp \le x. [Thus, π(10)=4\pi(10) = 4 since there are 44 primes, viz., 22, 33, 55, and 77, not exceeding 1010.]Prove that if n≥3n \ge 3 is an integer, then (a)π(2n)<π(n)+2nlog⁡2(n);\pi(2n) < \pi(n) + {{2n}\over{\log_2(n)}};(b)π(2n)<2n+1log⁡2(n−1)n;\pi(2^n) < {{2^{n+1}\log_2(n-1)}\over{n}};(c) Deduce that, for all real numbers x≥8x \ge 8,π(x)<4xlog⁡2(log⁡2(x))log⁡2(x).\pi(x) < {{4x \log_2(\log_2(x))}\over{\log_2(x)}}.
Back to ProblemsView on AoPS