# Existence of primes between every entry of $\{p, p^2, \ldots, p^n\}$ where $p$ is a prime?

Consider the sequence: $$\{p, p^2, \ldots, p^n\}$$ where $p \ge 2$ is a prime, and $n \in \mathbb{N}_{>1}$. I’d like to show that:

For all $1 \le i < n$, there exists a$^\dagger$ prime $q$ such that $p^i < q < p^{i+1}$.

For example, the sequence: $\{2, 4, 8, 16, 32\}$ satisfies this property since $2 < 3 < 4$, $4 < 7 < 8$ (or $4 < 5 <8$), $8 < 11 < 16$ (or $13$), $16 < 17 < 32$ (or $23$ etc.).

I am not interested in methods for finding such primes. For now, I am only interested in showing existence of such primes$^\ddagger$. Any pointers?

$^\dagger$ There could be more than one prime $p^i < q < p^{i+1}$, but I’m only interested in showing existence of any one of them.

$^\ddagger$ Context: I'm designing a program where I'm given $p,n$ as input, and available to me a function next_prime() as well. For the correct functionality of the program, I will call next_prime($p^i$) and want to make sure that next_prime($p^i$) will always return a prime $< p^{i+1}$.

-
Are you familiar with Bertrand's Postulate? The result you want is an immediate consequence. – Alex Becker Feb 18 '12 at 21:15
@AlexBecker I was not familiar with it. Now I see. For all $p^i > 1$, there exists at least one prime $q$ such that $p^i < q < 2p^i < p^{i+1}$. Right? I will leave the question open for other informative comments and answers. Please go ahead and post this as answer please. – user2468 Feb 18 '12 at 21:29

This is a consequence of Bertrand's Postulate, which states that there for any $n>1$, there is always a prime $q$ satisfying $n<q<2n$. Thus since $p\geq 2$, for any $i\geq 1$ we have a prime $q$ satisfying $p^i<q<2p^i\leq p^{i+1}$.