Maths Olympiad Prep

Library / /9 of 158

Number theory Difficulty 4.5 AIME Prove it Estonia

Prove that for any positive integer nn the sum of the first nn primes is greater than n2n^2.

Solution

First notice that the nn-th prime pnp_n satisfies the inequality pn2n1p_n \ge 2n - 1. Indeed, the claim holds for the first prime p1=2p_1 = 2. Since all other primes are odd and there is exactly n1n-1 odd numbers between 22 and 2n2n, there are at most nn prime numbers less or equal to 2n12n-1, hence pn2n1p_n \ge 2n - 1.

Now consider the sum of the nn first primes P=p1+p2++pnP = p_1 + p_2 + \dots + p_n. Since pk2k1p_k \ge 2k - 1 for any kk, and additionally p1=2>1p_1 = 2 > 1, the sum PP is strictly greater than the sum of nn first odd numbers S=1+3++(2n1)=(1202)+(2212)++(n2(n1)2)=n2S = 1 + 3 + \dots + (2n-1) = (1^2 - 0^2) + (2^2 - 1^2) + \dots + (n^2 - (n-1)^2) = n^2. So P>S=n2P > S = n^2.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.