Maths Olympiad Prep

Library / Estonian Math Competitions /9 of 148

Estonian Math Competitions

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 pn≥2n−1p_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 n−1n-1 odd numbers between 22 and 2n2n, there are at most nn prime numbers less or equal to 2n−12n-1, hence pn≥2n−1p_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 pk≥2k−1p_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+⋯+(2n−1)=(12−02)+(22−12)+⋯+(n2−(n−1)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,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

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