[proofplan] The proof is a contradiction argument at the asymptotic level, combined with a hand check for small $n$. Assume $(n, 2n)$ contains no prime. Factor $N = \binom{2n}{n}$ into two pieces: the product $N_1$ of primes $p$ with $\nu_p(N) = 1$, and the factor $N_2$ contributed by primes with $\nu_p(N) \geq 2$. Properties (ii)-(iv) of [Properties of $\binom{2n}{n}$](/theorems/1753) and the assumption that no prime lies in $(n, 2n)$ pin down the range of primes in each piece: $N_1$ contains only primes $\leq 2n/3$, and $N_2$ contains only primes $\leq \sqrt{2n}$. Using $\Theta(x) := \prod_{p \leq x} p \leq 4^x$ from the [Primorial Bound](/theorems/1756) to bound $N_1$, and property (iv) to bound each $p^{\nu_p(N)} \leq 2n$ in $N_2$, yields $N \leq 4^{2n/3} \cdot (2n)^{\sqrt{2n}}$. Combining with $N \geq 2^{2n}/(2n)$ from property (i) produces an inequality $2^{2n/3} \leq (2n)^{1+\sqrt{2n}}$ that fails for $n \geq n_0$. The range $n < n_0$ is handled by exhibiting a prime chain. [/proofplan] [step:Set up the contradiction and list the available facts] Fix an integer $n \geq 2$. Suppose for contradiction that no prime $p$ satisfies $n < p < 2n$. We aim to derive a contradiction for $n$ sufficiently large and to verify the claim directly for small $n$. Let $N := \binom{2n}{n}$. We record the properties we will use: (A) $\displaystyle N \geq \frac{2^{2n}}{2n}$ (from property (i) of [Properties of $\binom{2n}{n}$](/theorems/1753)); (B) If $p$ is prime and $n < p \leq 2n$, then $\nu_p(N) = 1$ (property (ii)); (C) If $p$ is prime and $\frac{2n}{3} < p \leq n$, then $\nu_p(N) = 0$ (property (iii), i.e., $\gcd(p, N) = 1$); (D) If $p$ is prime and $p^k \mid N$, then $p^k \leq 2n$ (property (iv)); (E) $\Theta(x) := \prod_{p \leq x} p \leq 4^x$ for all $x \geq 1$ (the [Primorial Bound](/theorems/1756)). [/step] [step:Locate the primes that can divide $N$] Let $p$ be a prime with $\nu_p(N) \geq 1$. We show $p \leq 2n$ and that if $\nu_p(N) = 1$ then in fact $p \leq \frac{2n}{3}$, while if $\nu_p(N) \geq 2$ then $p \leq \sqrt{2n}$. Since $p \mid N$ and $N \mid (2n)!$ (as $N \cdot (n!)^2 = (2n)!$, so the prime factorisation of $N$ uses only primes appearing in $(2n)!$), we have $p \leq 2n$. Now split based on the range of $p$. **Case $p \in (n, 2n]$.** By the contradiction hypothesis, no prime lies in $(n, 2n)$, so $p = 2n$. But $2n$ is prime only if $n = 1$, which is excluded ($n \geq 2$). Hence this case is empty: no prime in $(n, 2n]$ contributes to $N$ under our hypothesis. Alternatively, allowing the possibility $p = 2n$ and $n = 1$: in that case $n = 1$ and Bertrand's postulate ($2 = 2n$? no, the statement requires a prime strictly between $n = 1$ and $2n = 2$, and none exists but for $n = 1$ the statement is vacuous since $n > 1$ is required). So for $n \geq 2$ the case $p \in (n, 2n]$ is empty. **Case $p \in (\frac{2n}{3}, n]$.** By (C), $\nu_p(N) = 0$, so $p$ does not divide $N$. This case contributes nothing. **Case $p \in (\sqrt{2n}, \frac{2n}{3}]$.** By (D), $p^{\nu_p(N)} \leq 2n$, but $p > \sqrt{2n}$ implies $p^2 > 2n$, so $\nu_p(N) \leq 1$. Since we assumed $\nu_p(N) \geq 1$, we have $\nu_p(N) = 1$. **Case $p \in [2, \sqrt{2n}]$.** By (D), $p^{\nu_p(N)} \leq 2n$; no further restriction on $\nu_p(N)$. In summary, under the contradiction hypothesis, every prime $p$ dividing $N$ lies in one of two disjoint ranges: - $p \in (\sqrt{2n}, \frac{2n}{3}]$, with $\nu_p(N) = 1$; - $p \in [2, \sqrt{2n}]$, with $\nu_p(N) \geq 1$ and $p^{\nu_p(N)} \leq 2n$. [guided] We ask: what primes can possibly divide $N = \binom{2n}{n}$, given our assumption that $(n, 2n)$ contains no prime? A prime $p$ dividing $N$ must divide $(2n)!$, so $p \leq 2n$. We partition $[2, 2n]$ into four intervals and check each. **Interval $(n, 2n]$:** By the assumption, no prime in $(n, 2n)$. The only possibility is $p = 2n$, which is prime only when $n = 1$ — outside our range $n \geq 2$. So this interval is empty of primes dividing $N$. **Interval $(\frac{2n}{3}, n]$:** Property (iii) of [Properties of $\binom{2n}{n}$](/theorems/1753) says any such prime satisfies $\gcd(p, N) = 1$, hence does not divide $N$. **Interval $(\sqrt{2n}, \frac{2n}{3}]$:** Property (iv) gives $p^{\nu_p(N)} \leq 2n$. Since $p > \sqrt{2n}$, $p^2 > 2n$, so $\nu_p(N) \leq 1$. If $p$ divides $N$, then $\nu_p(N) = 1$. **Interval $[2, \sqrt{2n}]$:** Property (iv) still gives $p^{\nu_p(N)} \leq 2n$, but no restriction on the size of $\nu_p(N)$ beyond this. So the primes dividing $N$ partition into two groups, one in $(\sqrt{2n}, \frac{2n}{3}]$ with multiplicity exactly $1$, and one in $[2, \sqrt{2n}]$ with $p^{\nu_p(N)} \leq 2n$. This is the structural input for the ensuing estimate. [/guided] [/step] [step:Factor $N = N_1 N_2$ and bound each factor] Based on the previous step, we factor \begin{align*} N = N_1 \cdot N_2, \end{align*} where \begin{align*} N_1 &:= \prod_{\substack{p \text{ prime} \\ \nu_p(N) = 1}} p, \\ N_2 &:= \prod_{\substack{p \text{ prime} \\ \nu_p(N) \geq 2}} p^{\nu_p(N)}. \end{align*} **Bound on $N_1$.** From the previous step, every prime in $N_1$ satisfies $p \leq \frac{2n}{3}$. Hence \begin{align*} N_1 = \prod_{\substack{p \leq 2n/3 \\ \nu_p(N) = 1}} p \leq \prod_{p \leq 2n/3} p = \Theta\!\left(\frac{2n}{3}\right) \leq 4^{2n/3}, \end{align*} where the last inequality is (E), applicable since $\frac{2n}{3} \geq \frac{4}{3} \geq 1$ for $n \geq 2$. **Bound on $N_2$.** Every prime in $N_2$ satisfies $p \leq \sqrt{2n}$ (from the previous step, primes with $\nu_p(N) \geq 2$ lie in $[2, \sqrt{2n}]$). The number of primes in $[2, \sqrt{2n}]$ is at most $\sqrt{2n}$ (a crude bound: $\pi(\sqrt{2n}) \leq \sqrt{2n}$, since the number of integers in $[2, \sqrt{2n}]$ is at most $\sqrt{2n} - 1 \leq \sqrt{2n}$). By (D), $p^{\nu_p(N)} \leq 2n$ for each such prime. Therefore \begin{align*} N_2 = \prod_{\substack{p \leq \sqrt{2n} \\ \nu_p(N) \geq 2}} p^{\nu_p(N)} \leq \prod_{p \leq \sqrt{2n}} (2n) \leq (2n)^{\sqrt{2n}}. \end{align*} Combining, \begin{align*} N = N_1 N_2 \leq 4^{2n/3} \cdot (2n)^{\sqrt{2n}}. \end{align*} [/step] [step:Derive the contradiction inequality and check it fails for large $n$] Combining the upper bound from the previous step with the lower bound (A), \begin{align*} \frac{2^{2n}}{2n} \leq N \leq 4^{2n/3} \cdot (2n)^{\sqrt{2n}} = 2^{4n/3} \cdot (2n)^{\sqrt{2n}}. \end{align*} Rearranging (both sides positive), \begin{align*} 2^{2n - 4n/3} = 2^{2n/3} \leq 2n \cdot (2n)^{\sqrt{2n}} = (2n)^{1 + \sqrt{2n}}. \end{align*} Taking logarithms, \begin{align*} \frac{2n \log 2}{3} \leq (1 + \sqrt{2n}) \log(2n). \end{align*} Define $\varphi : [1, \infty) \to \mathbb{R}$ by \begin{align*} \varphi(y) = \frac{y \log 2}{3} - (1 + \sqrt{y}) \log y, \qquad y = 2n. \end{align*} Our contradiction-hypothesis consequence is $\varphi(2n) \leq 0$. [claim:$\varphi(y) > 0$ for all $y \geq 16384$] [proof] We show $\varphi(16384) > 0$ and that $\varphi$ is strictly increasing on $[16384, \infty)$, hence $\varphi(y) > 0$ for all $y \geq 16384$. **Value at $y = 2^{14} = 16384$.** We have $\log y = 14 \log 2$ and $\sqrt{y} = 128$. Hence \begin{align*} \varphi(16384) &= \frac{16384 \log 2}{3} - (1 + 128) \cdot 14 \log 2 \\ &= \log 2 \cdot \left( \frac{16384}{3} - 129 \cdot 14 \right) \\ &= \log 2 \cdot \left( \frac{16384}{3} - 1806 \right) \\ &= \log 2 \cdot \frac{16384 - 5418}{3} = \log 2 \cdot \frac{10966}{3} > 0. \end{align*} **Monotonicity on $[16384, \infty)$.** Differentiating $\varphi(y) = \frac{y \log 2}{3} - \log y - \sqrt{y} \log y$, \begin{align*} \varphi'(y) = \frac{\log 2}{3} - \frac{1}{y} - \frac{\log y}{2\sqrt{y}} - \frac{1}{\sqrt{y}}. \end{align*} At $y = 16384$: $1/y \approx 6 \times 10^{-5}$, $\log y / (2\sqrt{y}) = 14 \log 2 / 256 \approx 0.038$, and $1/\sqrt{y} = 1/128 \approx 0.0078$. The sum of the negative terms is at most $0.046$, while $\log 2 / 3 \approx 0.231$. Hence $\varphi'(16384) \geq 0.231 - 0.046 > 0$. Since $1/y$, $1/\sqrt{y}$, and $\log y / (2\sqrt{y})$ are all eventually decreasing in $y$ for $y \geq e^2$ (for the third: $\frac{d}{dy}(\log y / (2\sqrt{y})) = \frac{2 - \log y}{4 y^{3/2}} < 0$ for $y > e^2$), the negative contributions to $\varphi'$ decrease for $y \geq 16384$, so $\varphi'(y) > 0$ on $[16384, \infty)$. Therefore $\varphi$ is strictly increasing on $[16384, \infty)$, and $\varphi(y) \geq \varphi(16384) > 0$ for all $y \geq 16384$. [/proof] [/claim] Therefore, for $n \geq 8192$ (well within the asymptotic regime), the contradiction hypothesis forces $\varphi(2n) \leq 0$, which contradicts the claim. Hence no such $n \geq 8192$ exists without a prime in $(n, 2n)$. [guided] Our rearrangement gave \begin{align*} \frac{2n \log 2}{3} \leq (1 + \sqrt{2n}) \log(2n). \end{align*} The left side grows linearly in $n$; the right side grows like $\sqrt{n} \log n$. For $n$ large, linear growth eventually dominates square-root-times-logarithm growth, so the inequality must fail. We formalise by defining $\varphi(y) = \frac{y \log 2}{3} - (1 + \sqrt{y}) \log y$ with $y = 2n$ and showing $\varphi(y) > 0$ for $y \geq y_0$ for some explicit $y_0$. A computation at $y = 16384$ shows $\varphi > 0$; the derivative $\varphi'(y) = \frac{\log 2}{3} - \frac{1}{y} - \frac{\log y}{2\sqrt{y}} - \frac{1}{\sqrt{y}}$ tends to $\log 2 / 3 > 0$, so $\varphi$ is strictly increasing for large $y$, and $\varphi(y) > 0$ persists. The conclusion: for $n \geq 8192$, $\varphi(2n) > 0$, contradicting the consequence $\varphi(2n) \leq 0$ we derived from the no-prime-in-$(n, 2n)$ hypothesis. Hence the hypothesis fails — a prime must exist in $(n, 2n)$. Why this threshold? The asymptotic contradiction regime starts around $n \sim 500$ if one is careful with constants; we chose a loose $n \geq 8192$ to avoid delicate arithmetic. The remaining small $n$ are handled by a direct prime list. [/guided] [/step] [step:Verify the claim for small $n$ by an explicit prime chain] For $n < 8192$, we exhibit primes witnessing Bertrand's postulate. The sequence \begin{align*} p_0, p_1, \ldots, p_{15} = 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 4999, 9973, 19937 \end{align*} consists of primes with $p_0 = 2 < p_1 = 3 < \cdots < p_{15} = 19937$, each pair satisfying $p_{k+1} < 2 p_k$. One verifies each inequality directly: $3 < 4$, $5 < 6$, $7 < 10$, $13 < 14$, $23 < 26$, $43 < 46$, $83 < 86$, $163 < 166$, $317 < 326$, $631 < 634$, $1259 < 1262$, $2503 < 2518$, $4999 < 5006$, $9973 < 9998$, $19937 < 19946$. Each listed number is prime (verified by trial division or by standard prime tables). [claim:For each integer $n$ with $1 < n \leq 8192$, some $p_k$ in the sequence satisfies $n < p_k < 2n$] [proof] Given such $n$, note $2n \leq 16384 < 19937 = p_{15}$, so the set $\{k : p_k \geq 2n\}$ is non-empty (it contains $k = 15$). Let $k$ be the smallest index with $p_k \geq 2n$; then $k \geq 1$ (since $p_0 = 2 < 4 \leq 2n$ for $n \geq 2$), and $p_{k-1} < 2n$. By the chain property, $p_k < 2 p_{k - 1}$, so $p_k < 2 p_{k-1}$. We must show $p_{k - 1} > n$ or, equivalently, we must produce a prime in $(n, 2n)$. Write $q = p_{k-1}$; we have $q < 2n$. We claim $q > n$. If $q \leq n$, then $p_k < 2q \leq 2n$, contradicting $p_k \geq 2n$. So $q > n$. Hence $q = p_{k - 1}$ satisfies $n < q < 2n$, as required. (We also need to verify that $q < 2n$ is strict, i.e., $q \neq 2n$: since $q$ is prime and $q > n \geq 2$, $q$ is odd unless $q = 2$, but $q > n \geq 2$ forces $q \geq 3$; and $2n$ is even and $\geq 4$, so $2n$ is composite unless $n = 1$, which is excluded. Hence $q \neq 2n$ in all cases relevant here.) [/proof] [/claim] Since $8192 < 9973 < 19937$, every $n$ with $1 < n < 8192$ has a prime $p_{k-1}$ in $(n, 2n)$ from the chain, completing the small-$n$ case. [/step] [step:Combine the cases and conclude] For $n \geq 8192$, the contradiction argument of the preceding steps shows that no prime in $(n, 2n)$ is incompatible with the estimates on $\binom{2n}{n}$. For $1 < n < 8192$, the prime chain exhibits an explicit prime in $(n, 2n)$. In both regimes, for every integer $n > 1$, there exists a prime $p$ with $n < p < 2n$. This completes the proof of Bertrand's postulate. [/step]