[proofplan] We reduce to the case $x = n$ an integer and prove $\Theta(n) \leq 4^n$ by strong induction on $n$. The induction splits on parity: even $n$ reduces to odd $n - 1$ by the observation that $\Theta$ is unchanged across a non-prime argument. For odd $n = 2m + 1$, the binomial coefficient $\binom{2m+1}{m+1}$ is divisible by every prime in $(m + 1, 2m + 1]$ (because such a prime divides the numerator $(2m+1)!/(m!)!$ but not the denominator), so the product of these primes is at most $\binom{2m+1}{m+1} \leq 4^m$. Multiplying by $\Theta(m + 1) \leq 4^{m+1}$ from the inductive hypothesis gives $\Theta(2m + 1) \leq 4^{2m+1}$. [/proofplan] [step:Reduce to integer arguments] Let $x \geq 1$ be arbitrary and set $n = \lfloor x \rfloor \in \mathbb{Z}_{\geq 1}$. The function $\Theta$ defined by \begin{align*} \Theta : [1, \infty) &\to \mathbb{R}_{> 0} \\ x &\mapsto \prod_{p \leq x} p \end{align*} depends on $x$ only through the set $\{p \text{ prime} : p \leq x\}$. Since no prime lies strictly between $n$ and $n + 1$ (because consecutive integers $n < n + 1$ have no integer — hence no prime — strictly between them), every prime $p$ satisfies \begin{align*} p \leq x \iff p \leq n. \end{align*} Hence $\Theta(x) = \Theta(n)$. Therefore it suffices to prove \begin{align*} \Theta(n) \leq 4^n, \qquad \text{for every integer } n \geq 1, \end{align*} since then $\Theta(x) = \Theta(n) \leq 4^n \leq 4^x$ for $x \geq n$. [/step] [step:Prove the integer case by strong induction on $n$] We prove $\Theta(n) \leq 4^n$ for all integers $n \geq 1$ by strong induction. **Base case $n = 1$.** No prime is $\leq 1$, so $\Theta(1) = \prod_{\varnothing} p = 1 \leq 4 = 4^1$. **Inductive step.** Assume $\Theta(k) \leq 4^k$ for every integer $k$ with $1 \leq k < n$, and prove $\Theta(n) \leq 4^n$. We treat even and odd $n$ separately. [/step] [step:Handle even $n$ by reducing to the preceding odd integer] Suppose $n = 2m$ with $m \geq 1$, so $n \geq 2$. The integer $2m$ is prime only if $2m = 2$, i.e., $m = 1$, $n = 2$. For $n = 2$: $\Theta(2) = 2 \leq 16 = 4^2$, verifying the bound. For $n = 2m \geq 4$ (so $m \geq 2$), $n$ is not prime (since $2 \mid n$ and $n > 2$). Hence \begin{align*} \Theta(n) = \Theta(2m) = \prod_{p \leq 2m} p = \prod_{p \leq 2m - 1} p = \Theta(2m - 1) = \Theta(n - 1), \end{align*} since no prime equals $2m$. By the inductive hypothesis (applicable to $k = n - 1 < n$), \begin{align*} \Theta(n) = \Theta(n - 1) \leq 4^{n - 1} \leq 4^n. \end{align*} [/step] [step:Handle odd $n = 2m + 1$ via the binomial coefficient $\binom{2m+1}{m+1}$] Suppose $n = 2m + 1$ with $m \geq 1$ (so $n \geq 3$). The case $n = 3$: $\Theta(3) = 2 \cdot 3 = 6 \leq 64 = 4^3$, verifying the bound directly. We now handle $m \geq 1$ via the general argument, which in fact covers $n = 3$ too. We exploit the binomial coefficient \begin{align*} B := \binom{2m+1}{m+1} = \frac{(2m+1)!}{(m+1)! \, m!}. \end{align*} [claim:Every prime $p$ with $m + 2 \leq p \leq 2m + 1$ divides $B$] [proof] Let $p$ be a prime in $[m + 2, 2m + 1]$. We compute $\nu_p(B)$ directly from the factorial definition. **Numerator $(2m+1)!$.** Multiples of $p$ in $\{1, 2, \ldots, 2m + 1\}$: these are $p, 2p, \ldots, \lfloor (2m+1)/p \rfloor \cdot p$. Since $p \geq m + 2$, we have $(2m+1)/p \leq (2m+1)/(m+2) < 2$ (as $(2m+1)/(m+2) < 2 \iff 2m + 1 < 2m + 4$, which holds). And since $p \leq 2m + 1$, $(2m+1)/p \geq 1$. Hence $\lfloor (2m+1)/p \rfloor = 1$, so $p$ is the unique multiple of $p$ in $\{1, \ldots, 2m+1\}$. Moreover $p^2 \geq (m+2)^2 = m^2 + 4m + 4 > 2m + 1$ for $m \geq 1$ (since $m^2 + 4m + 4 > 2m + 1 \iff m^2 + 2m + 3 > 0$, always true). Hence no multiple of $p^2$ lies in $\{1, \ldots, 2m+1\}$, and $\nu_p((2m+1)!) = 1$. **Denominator $(m+1)! \, m!$.** Since $p \geq m + 2 > m + 1 \geq m$, no integer in $\{1, \ldots, m + 1\}$ or $\{1, \ldots, m\}$ is divisible by $p$. Hence $\nu_p((m+1)!) = 0$ and $\nu_p(m!) = 0$. Substituting, \begin{align*} \nu_p(B) = \nu_p((2m+1)!) - \nu_p((m+1)!) - \nu_p(m!) = 1 - 0 - 0 = 1, \end{align*} so $p \mid B$ (in fact $\nu_p(B) = 1$). [/proof] [/claim] From the claim, the primes in $[m + 2, 2m + 1]$ are distinct, each dividing $B$ exactly once. Since distinct primes are coprime, their product divides $B$: \begin{align*} \prod_{m + 2 \leq p \leq 2m + 1} p \text{ divides } B, \qquad \text{so} \qquad \prod_{m + 2 \leq p \leq 2m + 1} p \leq B. \end{align*} [guided] Why look at $B = \binom{2m+1}{m+1}$? Because the primes in the window $(m + 1, 2m + 1]$ divide it exactly once — the numerator $(2m+1)!$ picks up each such prime once (it appears in the range $\{1, \ldots, 2m+1\}$ exactly once, since twice any prime $p \geq m + 2$ exceeds $2m + 1$), while the denominator $(m+1)! m!$ is free of these primes (they are all greater than $m + 1$). Hence the primes in this window appear in $B$ with multiplicity exactly $1$, so their product is at most $B$. This is the core mechanism of the argument: we use $B$ as a "carrier" for the primes in $(m + 1, 2m + 1]$. The next task is to bound $B$ itself. [/guided] [/step] [step:Bound $B \leq 4^m$ using the binomial theorem] We show \begin{align*} B = \binom{2m+1}{m+1} \leq 4^m. \end{align*} Using the symmetry $\binom{2m+1}{k} = \binom{2m+1}{2m + 1 - k}$, \begin{align*} \binom{2m+1}{m} = \binom{2m+1}{m + 1} = B. \end{align*} By the binomial theorem applied to $(1 + 1)^{2m+1}$, \begin{align*} 2^{2m+1} = \sum_{k=0}^{2m+1} \binom{2m+1}{k}. \end{align*} The two terms $\binom{2m+1}{m}$ and $\binom{2m+1}{m+1}$ both equal $B$, and all terms are non-negative; hence \begin{align*} 2 B = \binom{2m+1}{m} + \binom{2m+1}{m+1} \leq \sum_{k=0}^{2m+1} \binom{2m+1}{k} = 2^{2m+1}. \end{align*} Dividing by $2$, \begin{align*} B \leq 2^{2m} = 4^m. \end{align*} [/step] [step:Combine the bounds and close the induction for odd $n$] Combining the previous two steps, \begin{align*} \prod_{m+2 \leq p \leq 2m+1} p \leq B \leq 4^m. \end{align*} We split $\Theta(2m+1)$ by the prime range: \begin{align*} \Theta(2m+1) = \prod_{p \leq 2m+1} p = \left( \prod_{p \leq m + 1} p \right) \cdot \left( \prod_{m + 2 \leq p \leq 2m + 1} p \right) = \Theta(m+1) \cdot \prod_{m+2 \leq p \leq 2m+1} p. \end{align*} (If no primes lie in $[m+2, 2m+1]$, the second factor is the empty product $1$, and the equality still holds.) Applying the induction hypothesis to $k = m + 1 < 2m + 1 = n$ (valid since $m \geq 1$ gives $m + 1 \geq 2 \geq 1$, and $m + 1 < 2m + 1$ for $m \geq 1$), \begin{align*} \Theta(m+1) \leq 4^{m+1}. \end{align*} Combining with $\prod_{m+2 \leq p \leq 2m+1} p \leq 4^m$, \begin{align*} \Theta(2m+1) \leq 4^{m+1} \cdot 4^m = 4^{2m + 1} = 4^n. \end{align*} This completes the inductive step for odd $n$. [/step] [step:Conclude the induction and lift to non-integer $x$] The base case $n = 1$ and the inductive steps for even and odd $n \geq 2$ together establish $\Theta(n) \leq 4^n$ for every integer $n \geq 1$. Lifting to $x \geq 1$: by the first step, $\Theta(x) = \Theta(\lfloor x \rfloor)$ and $4^{\lfloor x \rfloor} \leq 4^x$ (since $\lfloor x \rfloor \leq x$ and the exponential $4^{(\cdot)}$ is increasing). Hence \begin{align*} \Theta(x) = \Theta(\lfloor x \rfloor) \leq 4^{\lfloor x \rfloor} \leq 4^x, \end{align*} completing the proof of the Primorial Bound. [/step]