Why are there always two primes between $2^n$ and $2^{n+1}$?

Question

In a cryptographic lecture we just assumed that this statement holds. In particular, we said for a fixed length of bits one can always find two primes, that have the same length in binary representation. But why so? Is there an easy explanation I just overlooked or is the matter a bit more complicated?

I guess it follows from Bertrand's postulate, but I don't see how we get the second prime in this interval.

Edit: Of course this statement only holds for a large enough n, meaning $n\geq2$

Answer 1

This follows from a strengthening of Bertrand's postulate. In fact it can be shown that for every $\varepsilon>0$, for all sufficiently large $n$ there exists a prime between $n$ and $(1+\varepsilon)n$: See here.

In particular, for any $k$ there are at least $k$ primes between $2^n$ and $2^{n+1}$ for sufficiently large $n$.

Answer 2

By the prime number theorem, the prime counting function $\pi(n)$ is quite close to

$$\pi(n) \approx \frac{n}{\log n}$$

so

$$\pi(2^{n+1}) - \pi(2^n) \\= \frac{2^{n+1}}{\log 2^{n+1}} - \frac{2^{n}}{\log 2^{n}}\\= \frac{2^n}{\log 2} \left( \frac{2}{n+1} - \frac{1}{n}\right)\\=\frac{2^n}{\log 2} \left( \frac{n-1}{n(n+1)}\right)\\\gg 2 $$

for large $n$.

Answer 3

We have certain properties, that have been proven, and other properties, that are totally sure, but not proven. It has been proven that between $n$ and $2 \times n$, we have at least 1 prime. It has not been proven that between $n$ and $1.01 \times n$, for $n > 10^{1000}$, we have at least 1 prime, but if I work on crypto or any science that need primes, I will consider that this property is true. In such an interval, the question is not "is there at least 1 prime ?", but "how many millions of primes ?"