Prove that $\forall n \in \mathbb{N}^*, P_n \lt 4^n$ where $P_n$ is the $n$th prime number. I'm searching for a proof that doesn't use induction and uses only the elementary concepts of number theory.
This theorem appears in an old french book on Arithmetics destined to high school level students (lycée). It is introduced right after the concept of decomposition into prime factors. The book includes a proof that I didn't understand. You can see below a screenshot taken from the book and a translation attempt.
Theorem
For all integers $n \gt0,$ the $nth$ prime number $q$ verifies the inequality $q \lt 4^n$.
Demonstration
The $[1,q]$ interval is included in the set of integers $k$ that can be written, (after grouping all the squares that can be formed with the $n$ prime numbers $p_i \le q $ in a decomposition of $k$), as $k = m^2p_1^{e_1}p_2^{e_2}…p_n^{e_n}$ with $e_i \in {0,1}$. (Here, $p_i$ is the i-th prime number, and $p_n = q$.). There are no more than $\sqrt{q}$ integers like m, and at most $2^n$ choices for the exponents $e_i$, what shows that $q$, cardinal of this set, is strictly lower than the product $2^n\sqrt{q}$, then the result.
Best Answer
The proof given in your book is very nice and elementary (certainly more elementary than Bertrand's postulate, let alone the prime number theorem), so I'll paraphrase it here. The key insight is that there are a lot of numbers out there that have to be expressible as products of primes (or primes and squares, in this proof), and this becomes impossible if there are too few primes to use.
Let $q$ denote the $n$th prime. Notice that every positive integer can be written (uniquely) as a square times a product of distinct primes. (This comes from its prime factorization; for example, $2^7 \cdot 3^5 \cdot 7^4 \cdot 11^2 \cdot 13 = (2^3 \cdot 3^2 \cdot 7^2 \cdot 11)^2 \cdot 2 \cdot 3 \cdot 13$. We allow the square to be $1^2$ when necessary, e.g. $35 = 1^2 \cdot 5 \cdot 7$, and similarly for there to be no extra primes, e.g. $36 = 6^2$.)
So let's express every integer between $1$ and $q$ in this way. For each integer $k$ in this range, we get a square and some set of primes. The square must be at most $q$ (or else $k$ would be greater than $q$), so there are at most $\sqrt q$ possible choices for it, namely $1^2, 2^2, \dots, \lfloor \sqrt q \rfloor^2$. Each of the primes must also be at most $q$, so they must be chosen from among the first $n$ primes, giving us $2^n$ possible choices for a subset. So there are at most $\sqrt q \cdot 2^n$ numbers that can be written in this very specific form. But wait: we just wrote $q$ different numbers in this form. So it must be that $q \leq \sqrt q \cdot 2^n$, which simplifies to $\sqrt q \leq 2^n$ and thus $q \leq 4^n$.