Maths WorkshopMaths problems with full solutions
Exercise 1838Number theory › PrimesOlympiadAdded 3 Nov 2026

Bounds on the $n$-th prime

#n-th prime#bounds#elementary

Statement

Show that the nn-th prime pnp_n satisfies pn≤22n−1p_n\le2^{2^{n-1}} for all n≥1n\ge1.

Hint

Use induction: pn+1≤p1⋯pn+1p_{n+1}\le p_1\cdots p_n+1.

Show solutionHide solution

Solution

Induction base. p1=2≤2p_1=2\le2.

Inductive step. pn+1p_{n+1} divides p1⋯pn+1p_1\cdots p_n+1 (or is less than it), so pn+1≤p1⋯pn+1p_{n+1}\le p_1\cdots p_n+1. By induction, pi≤22i−1p_i\le2^{2^{i-1}}, so
pn+1≤∏i=1n22i−1+1=22n−1+1<22n.p_{n+1}\le\prod_{i=1}^n2^{2^{i-1}}+1=2^{2^n-1}+1<2^{2^n}.

Conclusion. pn≤22n−1p_n\le2^{2^{n-1}}.

Remark. Much better bounds exist: pn∼nln⁡np_n\sim n\ln n by the prime number theorem.