贝特兰猜想

描述：对于任意正整数 $n$，在 $(n,2n]$ 间至少存在一个质数 $p$。

首先有一个引理：

对于任意 $x>1$，$\prod\limits_{p\le x}p\le 4^{x-1}$。

证明：

考虑数学归纳法，假设对于 $x\in\{2,3,\cdots,n\}$ 成立，证明其对于 $n+1$ 成立。

分类讨论奇偶性。如果 $n$ 为奇数，则显然成立，因为此时 $\prod\limits_{p\le n}p=\prod\limits_{p\le n+1}p$，而 $4^{n-1}<4^n$。

如果 $n$ 为偶数，设 $n=2m$，则要证 $\prod\limits_{p\le 2m+1}p\le 4^{2m}$。进行如下放缩：

$$\prod\limits_{p\le 2m+1}p=\prod\limits_{p\le m+1}p\cdot \prod\limits_{m+1<p\le 2m+1}p\le 4^m\cdot\binom{2m+1}{m}\le 4^m\cdot 2^{2m}=4^{2m}$$

其中涉及到一个不等式 $\prod\limits_{m+1<p\le 2m+1}p\le \binom{2m+1}{m}$，因为：

$$\binom{2m+1}{m}=\frac{(2m+1)!}{m!(m+1)!}=\frac{(m+2)(m+3)\cdots(2m+1)}{m!}$$

注意到，对于每个质数 $p\in (m+1,2m+1]$，分子都为 $p$ 的倍数而分母不是，所以 $\prod\limits_{m+1<p\le 2m+1}p$ 为 $\binom{2m+1}{m}$ 的因数，故小于等于后者。

考虑 $\binom{2n}{n}$ 的质因数分解，对于每个质数 $p$ 的次数。

有 $\binom{2n}{n}=\frac{(2n)!}{n!n!}$。由勒让德定理，对于每个质数 $p$，其在 $n!$ 中的次数等于 $\sum\limits_{k\ge 1} \left\lfloor\frac{n}{p^k}\right\rfloor$。所以对于每个质数 $p$，其在 $\binom{2n}{n}$ 中的出现次数等于 $\sum\limits_{k\ge 1} \left\lfloor\frac{2n}{p^k}\right\rfloor-2\left\lfloor\frac{n}{p^k}\right\rfloor$（分子减去分母）。容易证明，其中每一项都不超过 $1$，所以总的出现次数不超过项数 $\log_p(2n)$，所以对于每个 $p$ 的结果不超过 $p^{\log_p(2n)}=2n$。

特殊地，考虑 $\frac{2}{3}n<p\le n$ 的 $p$，发现 $p$ 一定不会出现在 $\binom{2n}{n}$ 内，因为 $\frac{(2n)!}{n!n!}$ 中 $p$ 在分子会在 $p,2p$ 处各出现一次（$3p>2n$，所以一共只有两次）；在分子中会在每个 $n!$ 里出现一次，所以总共两次。分子分母抵消，所以不会出现。

考虑 $n<p\le 2n$ 的 $p$，发现会且仅会出现一次。

综上所述，有：

$$\binom{2n}{n}\le \prod\limits_{p\le \sqrt{2n}} 2n\cdot \prod\limits_{\sqrt{2n}<p\le \frac{2}{3}n} p\cdot \prod\limits_{n<p\le 2n}p\le (2n)^{\sqrt{2n}}\cdot 4^{\frac{2}{3}n}\cdot \prod\limits_{n<p\le 2n}p$$

又有结论 $\binom{2n}{n}\ge \frac{4^n}{2n}$，所以：

$$\frac{4^n}{2n}\le (2n)^{\sqrt{2n}}\cdot 4^{\frac{2}{3}n}\cdot \prod\limits_{n<p\le 2n}p$$

$$4^{\frac{1}{3}n}\le (2n)^{\sqrt{2n}+1}\cdot \prod\limits_{n<p\le 2n}p$$

然后使用反证法：若 $(n,2n]$ 内不存在质数 $p$，则上式化为 $4^{\frac{1}{3}n}\le (2n)^{\sqrt{2n}+1}$，当 $n$ 充分大时一定不成立，所以只要 $n$ 充分大，$(n,2n]$ 内一定存在质数 $p$。而当 $n$ 较小的时候，可以通过枚举法证明猜想同样成立。