[proofplan] The upper and lower bounds on $\pi(x)$ are proved independently, both via the central binomial coefficient $N = \binom{2n}{n}$ and its divisibility properties from the [Properties of $\binom{2n}{n}$](/theorems/1753). The upper bound is obtained by an induction on $k$ establishing $\pi(2^k) \leq 3 \cdot 2^k / k$: the inductive step uses that $\prod_{n < p \leq 2n} p$ divides $N$ (by property (ii)) and hence is bounded by $N \leq 2^{2n}$. The lower bound uses property (iv), $p^{\nu_p(N)} \leq 2n$, to bound $\log N \leq \pi(2n) \log(2n)$; combining with the lower bound $N \geq 2^{2n}/(2n)$ from property (i) gives $\pi(2n) \gtrsim 2n \log 2 / \log(2n)$. [/proofplan] [step:State the two auxiliary inputs from Properties of $\binom{2n}{n}$] Let $n \geq 1$ and $N := \binom{2n}{n}$. We will use three facts from [Properties of $\binom{2n}{n}$](/theorems/1753): (A) $\displaystyle \frac{2^{2n}}{2n} \leq N \leq 2^{2n}$ (from property (i)); (B) Every prime $p$ with $n < p \leq 2n$ satisfies $\nu_p(N) = 1$, so $p \mid N$ (from property (ii)); (C) For every prime $p \leq 2n$, $p^{\nu_p(N)} \leq 2n$ (from property (iv) applied with $k = \nu_p(N)$). [/step] [step:Upper bound: show $\pi(2n) - \pi(n) \leq \frac{2n \log 2}{\log n}$ for $n \geq 2$] Fix $n \geq 2$. Consider the product of primes in the interval $(n, 2n]$: \begin{align*} \prod_{n < p \leq 2n} p. \end{align*} By (B), each such prime divides $N$ with $\nu_p(N) = 1$; distinct primes are coprime, so their product divides $N$. Moreover each factor satisfies $p > n$, so \begin{align*} n^{\pi(2n) - \pi(n)} = \prod_{n < p \leq 2n} n < \prod_{n < p \leq 2n} p \leq N \leq 2^{2n}, \end{align*} where the last step is (A). Taking logarithms (base $e$) and using $\log n > 0$ since $n \geq 2$, \begin{align*} (\pi(2n) - \pi(n)) \log n \leq 2n \log 2, \end{align*} i.e., \begin{align*} \pi(2n) - \pi(n) \leq \frac{2n \log 2}{\log n}. \end{align*} [/step] [step:Upper bound: prove by induction that $\pi(2^k) \leq \frac{3 \cdot 2^k}{k}$ for all $k \geq 1$] We prove \begin{align*} \pi(2^k) \leq \frac{3 \cdot 2^k}{k}, \qquad k \geq 1, \end{align*} by induction on $k$. **Base cases $k = 1, 2, 3, 4, 5, 6$.** We check directly: \begin{align*} \pi(2) &= 1 \leq 6 = 3 \cdot 2 / 1, \\ \pi(4) &= 2 \leq 6 = 3 \cdot 4 / 2, \\ \pi(8) &= 4 \leq 8 = 3 \cdot 8 / 3, \\ \pi(16) &= 6 \leq 12 = 3 \cdot 16 / 4, \\ \pi(32) &= 11 \leq 96/5 = 19.2, \\ \pi(64) &= 18 \leq 192/6 = 32. \end{align*} **Inductive step for $k \geq 6$.** Assume $\pi(2^k) \leq 3 \cdot 2^k / k$. Set $n = 2^k$; by the previous step (applicable since $n = 2^k \geq 2$), \begin{align*} \pi(2^{k+1}) - \pi(2^k) \leq \frac{2 \cdot 2^k \log 2}{\log 2^k} = \frac{2^{k+1} \log 2}{k \log 2} = \frac{2^{k+1}}{k}. \end{align*} Adding to the inductive hypothesis, \begin{align*} \pi(2^{k+1}) \leq \frac{3 \cdot 2^k}{k} + \frac{2^{k+1}}{k} = \frac{3 \cdot 2^k + 2 \cdot 2^k}{k} = \frac{5 \cdot 2^k}{k} = \frac{5 \cdot 2^{k+1}}{2k}. \end{align*} We want $\frac{5 \cdot 2^{k+1}}{2k} \leq \frac{3 \cdot 2^{k+1}}{k+1}$, i.e., $5(k + 1) \leq 6k$, i.e., $k \geq 5$. Since we are in the regime $k \geq 6$, this holds, completing the induction. [guided] The target is $\pi(2^k) \leq 3 \cdot 2^k / k$. We prove it by induction, with the inductive step consuming the bound $\pi(2n) - \pi(n) \leq 2n\log 2 / \log n$ from the previous step. The base cases $k = 1, \ldots, 6$ are direct computations: count the primes up to $2, 4, 8, 16, 32, 64$ and check each against $3 \cdot 2^k / k$. For the inductive step at $k \geq 6$: set $n = 2^k$. The bound from the previous step gives \begin{align*} \pi(2^{k+1}) = \pi(2n) \leq \pi(n) + \frac{2n \log 2}{\log n} = \pi(2^k) + \frac{2^{k+1}}{k}, \end{align*} since $\log(2^k) = k \log 2$, so $2n \log 2 / \log n = 2 \cdot 2^k \log 2 / (k \log 2) = 2^{k+1} / k$. Applying the induction hypothesis, \begin{align*} \pi(2^{k+1}) \leq \frac{3 \cdot 2^k}{k} + \frac{2^{k+1}}{k} = \frac{5 \cdot 2^k}{k}. \end{align*} We want this bounded by $3 \cdot 2^{k+1} / (k+1) = 6 \cdot 2^k / (k+1)$. The inequality $5 \cdot 2^k / k \leq 6 \cdot 2^k / (k+1)$ simplifies to $5(k+1) \leq 6k$, i.e., $k \geq 5$. Since $k \geq 6$ in the inductive regime, this holds. The induction runs from the last base case $k = 6$ onwards. Why do we need several base cases rather than just $k = 1$? Because the inductive step requires $k \geq 5$ to make the arithmetic close; small $k$ must be verified individually. [/guided] [/step] [step:Upper bound: interpolate from powers of $2$ to all $x \geq 3$ to obtain $\pi(x) \leq 6 \log 2 \cdot x / \log x$] Let $x \geq 3$ and let $k \geq 1$ be the unique integer with $2^k \leq x < 2^{k+1}$; in particular $k = \lfloor \log x / \log 2 \rfloor \geq 1$. Define $\psi : [e, \infty) \to \mathbb{R}$ by $\psi(t) = t / \log t$. Differentiating, \begin{align*} \psi'(t) = \frac{\log t - 1}{(\log t)^2}, \end{align*} which is positive for $t > e$. Hence $\psi$ is strictly increasing on $[e, \infty)$. Since $x < 2^{k+1}$, we have $\pi(x) \leq \pi(2^{k+1})$, and by the previous step, \begin{align*} \pi(x) \leq \pi(2^{k+1}) \leq \frac{3 \cdot 2^{k+1}}{k+1}. \end{align*} We compare this to $6 \log 2 \cdot x / \log x$. Using $2^k \leq x$, so $\log x \geq k \log 2$, i.e., $k + 1 \geq (\log x + \log 2)/\log 2 \geq \log x / \log 2$, and $2^{k+1} \leq 2x$ (from $2^k \leq x$): \begin{align*} \frac{3 \cdot 2^{k+1}}{k+1} \leq \frac{3 \cdot 2x}{\log x / \log 2} = \frac{6 x \log 2}{\log x}. \end{align*} Hence for all $x \geq 3$, \begin{align*} \pi(x) \leq \frac{6 \log 2 \cdot x}{\log x} = c_2 \frac{x}{\log x} \qquad \text{with } c_2 = 6 \log 2. \end{align*} (For the edge cases $x = 3$: $\pi(3) = 2$ and $6\log 2 \cdot 3/\log 3 \approx 11.34$, so the bound holds. For $x \in (2^k, 2^{k+1})$ one notes $\pi(x) = \pi(\lfloor x \rfloor)$ and the above interpolation handles integer $x$.) [/step] [step:Lower bound: bound $\log N$ below using $N \geq 2^{2n}/(2n)$ and above using property (iv)] We now prove the lower bound. By (A), \begin{align*} \log N \geq \log \frac{2^{2n}}{2n} = 2n \log 2 - \log(2n). \end{align*} On the other hand, factoring $N$ over primes, \begin{align*} \log N = \sum_{p \text{ prime}} \nu_p(N) \log p = \sum_{p \leq 2n} \nu_p(N) \log p, \end{align*} where the sum is restricted to $p \leq 2n$ since $\nu_p(N) = 0$ for $p > 2n$ (such a prime cannot appear in the factorisation of $(2n)!$, hence not in $N$). By (C), $p^{\nu_p(N)} \leq 2n$, so $\nu_p(N) \log p \leq \log(2n)$ for each prime $p \leq 2n$. Therefore \begin{align*} \log N \leq \sum_{p \leq 2n} \log(2n) = \pi(2n) \log(2n). \end{align*} Combining, \begin{align*} 2n \log 2 - \log(2n) \leq \pi(2n) \log(2n), \end{align*} so \begin{align*} \pi(2n) \geq \frac{2n \log 2 - \log(2n)}{\log(2n)} = \frac{2n \log 2}{\log(2n)} - 1. \end{align*} [guided] We have two handles on $\log N$: a lower bound from (A) and an upper bound from (C). **Lower bound on $\log N$.** Property (A) of [Properties of $\binom{2n}{n}$](/theorems/1753) says $N \geq 2^{2n}/(2n)$. Taking logarithms, \begin{align*} \log N \geq 2n \log 2 - \log(2n). \end{align*} **Upper bound on $\log N$.** Factor $N$ as $\prod_p p^{\nu_p(N)}$ over primes. Since $N$ divides $(2n)!$ (in fact $N \leq (2n)!$ and $N \cdot (n!)^2 = (2n)!$), only primes $p \leq 2n$ appear. So \begin{align*} \log N = \sum_{p \leq 2n} \nu_p(N) \log p. \end{align*} Property (C), which is property (iv) of [Properties of $\binom{2n}{n}$](/theorems/1753) applied with $k = \nu_p(N)$, says $p^{\nu_p(N)} \leq 2n$, i.e., $\nu_p(N) \log p \leq \log(2n)$. Thus each of the $\pi(2n)$ terms is bounded by $\log(2n)$, giving \begin{align*} \log N \leq \pi(2n) \log(2n). \end{align*} **Combining.** Chaining the two, \begin{align*} 2n \log 2 - \log(2n) \leq \log N \leq \pi(2n) \log(2n), \end{align*} so dividing by $\log(2n) > 0$ (valid since $n \geq 1$, so $2n \geq 2$ and $\log(2n) > 0$): \begin{align*} \pi(2n) \geq \frac{2n \log 2}{\log(2n)} - 1. \end{align*} The strategy is characteristic of Chebyshev-style lower bounds: bound the factorisation quantity ($\log N$) from below by its size ($N \geq 2^{2n}/(2n)$) and from above by its prime factor count ($\pi(2n)$), each factor being controlled individually. [/guided] [/step] [step:Lower bound: interpolate from even arguments to all $x \geq 3$ to obtain $\pi(x) \geq \frac{\log 2}{2} \cdot x / \log x$] Let $x \geq 3$. Write $n = \lfloor x/2 \rfloor$; then $2n \leq x < 2n + 2$ and $n \geq 1$. Hence $\pi(x) \geq \pi(2n)$. From the previous step (for $n \geq 1$), \begin{align*} \pi(x) \geq \pi(2n) \geq \frac{2n \log 2}{\log(2n)} - 1. \end{align*} **Large $x$ case: $x \geq 16$.** Then $n \geq 8$, and $2n \geq x - 2 \geq x/2 + 6$ (using $x \geq 16$ gives $x/2 \geq 8 \geq x - x/2 - 6$? more cleanly: $2n \geq x - 1$, and since $x \geq 16$, $2n \geq 15 \geq x - 1$). Using $\log(2n) \leq \log x$ (since $2n \leq x$) and $2n \geq x - 1 \geq x/2$ (for $x \geq 2$): \begin{align*} \pi(x) \geq \frac{2n \log 2}{\log(2n)} - 1 \geq \frac{(x-1) \log 2}{\log x} - 1. \end{align*} We show this exceeds $\frac{\log 2}{2} \cdot \frac{x}{\log x}$ for $x \geq 16$. Equivalently, \begin{align*} \frac{(x-1)\log 2}{\log x} - \frac{x \log 2}{2 \log x} \geq 1 \iff \frac{\log 2}{\log x}\left(x - 1 - \frac{x}{2}\right) \geq 1 \iff \frac{(x/2 - 1) \log 2}{\log x} \geq 1, \end{align*} i.e., $(x - 2) \log 2 \geq 2 \log x$, i.e., $(x - 2) \log 2 - 2 \log x \geq 0$. At $x = 16$: $14 \log 2 - 2 \log 16 = 14 \log 2 - 8 \log 2 = 6 \log 2 > 0$. The derivative with respect to $x$ is $\log 2 - 2/x$, which is positive for $x > 2/\log 2 \approx 2.89$; so the function is strictly increasing on $[16, \infty)$ and remains $\geq 0$. **Small $x$ case: $3 \leq x < 16$.** We verify by direct computation that $\pi(x) \geq \frac{\log 2}{2} \cdot \frac{x}{\log x}$. At $x = 3$: $\pi(3) = 2$ and $\frac{\log 2}{2} \cdot \frac{3}{\log 3} \approx 0.347 \cdot 2.73 \approx 0.95$; the bound holds. The function $\frac{\log 2}{2} \cdot x/\log x$ is increasing on $[e, 16]$ (by the monotonicity of $\psi$ shown earlier), with value at $x = 16$ equal to $\frac{\log 2}{2} \cdot 16/\log 16 \approx 0.347 \cdot 16/2.77 \approx 2.0$. Meanwhile $\pi(x) \geq 2$ for $x \geq 3$ (the primes $2, 3$). For $x \in [3, 16]$, $\pi(x) \geq 2$ always exceeds $\frac{\log 2}{2} \cdot x/\log x \leq 2.0$; the finitely many cases $x \in \{3, 4, 5, \ldots, 15\}$ are checked individually. Hence for all $x \geq 3$, \begin{align*} \pi(x) \geq \frac{\log 2}{2} \cdot \frac{x}{\log x} = c_1 \cdot \frac{x}{\log x} \qquad \text{with } c_1 = \frac{\log 2}{2}. \end{align*} [/step] [step:Combine the two bounds] From the preceding steps, for all $x \geq 3$, \begin{align*} \frac{\log 2}{2} \cdot \frac{x}{\log x} \leq \pi(x) \leq 6 \log 2 \cdot \frac{x}{\log x}, \end{align*} with $c_1 = \log 2 / 2 \approx 0.347$ and $c_2 = 6 \log 2 \approx 4.16$. This completes the proof of Chebyshev's theorem. [/step]