For positive integer n, let s be the binomial coefficient (2n choose n). Show that s is divisible by every prime in [n+1,2n]. Conclude that the number of primes in (n,2n] is at most 2n/(log2 n), where (log2 n) is the logarithm base 2 of n. Next, show that the number of primes in [1,2k] is at most 1+ (sum from m=2 to k) 2m/(m-1). Divide the sum into terms with m < k/2 and m ≥ k/2, and show that the number of primes is at most 1 + (4/k) 2k + 22+k/2. Finally, show that for any x>2, the number of primes in [1,x] is at most 20 x/(log2 x).
I am not sure if the exponents came out right. Here it is again:
It's a long question and my teacher said it's supposed to be easy but I don;t get any of it... help?!?!?For positive integer n, let s be the binomial coefficient (2n choose n). Show that s is divisible by every prime in [n+1,2n]. Conclude that the number of primes in (n,2n] is at most 2n/(log_2 n), where (log_2 n) is the logarithm base 2 of n. Next, show that the number of primes in [1,2k] is at most 1+ (sum from m=2 to k) 2^m /(m-1). Divide the sum into terms with m < k/2 and m >= k/2, and show that the number of primes is at most 1 + (4/k) 2^k + 2^(2+k/2). Finally, show that for any x>2, the number of primes in [1,x] is at most 20 x/(log_2 x).