贡献者： int256
预备知识 数论函数
，渐进估计与阶
，最大公约数与最小公倍数
，二项式定理
本文默认若对 $n$ 求和或求积，则范围均满足 $n \ge 1$。符号 $\lfloor n \rfloor$ 表示 $n$ 的整数部分。
1. 阶
定理 1
函数 $\vartheta(x)$ 与 $\psi(x)$ 的阶是 $x$：
对于足够大的 $x$（$x \ge 2$），
\begin{equation}
Ax < \vartheta(x) < Bx, ~ Cx < \psi(x) < Dx ~ ~.
\end{equation}
2. 证明
我们首先引入一个引理并予以证明。
引理 1
\begin{equation}
\psi(x) = \vartheta(x) + \mathcal O\left( x^{1/2} (\ln x)^{2} \right) ~.
\end{equation}
证明：考虑 $\psi(x)$ 的定义，由于 $p^2 \le x$, $p^3 \le x$, $\dots$ 等价于 $p \le x^{1/2}$, $p \le x^{1/3}$, $\dots$, 故
\begin{equation}
\psi(x) = \vartheta(x) + \vartheta(x^{1/2}) + \vartheta(x^{1/3}) + \cdots = \sum_{m} \vartheta(x^{1/m}) ~.
\end{equation}
当 $x^{1/m} < 2$，也就是
\begin{equation}
m > \frac{\ln x}{\ln 2} ~~
\end{equation}
时，求和结束。由 $\vartheta(x)$ 的定义显然有 $x$ 足够大时 $\vartheta(x) < x \ln x$，故 $m \ge 2$ 时有
\begin{equation}
\vartheta(x^{1/m}) < x^{1/m} \ln x \le x^{1/2} \ln x~,
\end{equation}
且
\begin{equation}
\sum_{m \ge 2} \vartheta(x^{1/m}) = \mathcal O\left( x^{1/2} (\ln x)^{2} \right) ~.
\end{equation}
这等式成立是因为由于
式 4 ，这级数仅有 $\mathcal O(\ln x)$ 项。
将式 6 与 $\vartheta(x)$ 相加，就得到了式 3 ，就完成了证明。
这引理指出，当 $x$ 足够大时，$\vartheta(x)$ 与 $\psi(x)$ 大致相等。根据这个引理，我们只需证明对足够大的 $x$ 有 $\vartheta(x) < Bx$ 与 $\psi(x) > Cx$。因为上界与下界只需用两个数论函数中的一者约束即可。引入
\begin{equation}
M = \frac{(2m+1)!}{m! (m+1)!} = \frac{(2m+1)(2m)\cdots(m+2)}{m!} ~,
\end{equation}
这将是一个整数，且由于组合数性质，将在 $(1+1)^{2m+1}$ 的二项式展开中出现两次，故 $2M < 2^{2m+1}$ 即 $M < 2^{2m}$。考虑对于某素数 $p$，若 $m+1 < p \le 2m+1$，那么 $p$ 是 $M$ 的分子的因子，但并不是分母的因子。也就是说，
\begin{equation}
\left( \prod_{m+1 < p \le 2m+1} p \right) \mid M ~.
\end{equation}
且
\begin{equation}
\vartheta(2m+1) - \vartheta(m+1) = \sum_{m+1 < p \le 2m+1} \ln p \le \ln M < 2 m \ln 2 ~.
\end{equation}
通过归纳法可以立刻得出 $\vartheta(x) < 2x \ln 2$。就证明了 $\vartheta(x) < Bx$，另外还得到了一个更严的估计。
推论 1
对于足够大的 $n$，
\begin{equation}
\vartheta(n) < 2 n \ln n ~.
\end{equation}
下面考虑 $\psi(x)$，我们要证明 $\psi(x) > Cx$。为此引入另一引理。
引理 2
记
\begin{equation}
k(n, p) = \sum_{m\ge 1} \left\lfloor \frac{n}{p^m} \right\rfloor ~,
\end{equation}
则
\begin{equation}
n! = \prod_p p^{k(n, p)} ~.
\end{equation}
证明：这是因为 $1, 2, \dots, n$ 各数恰好包含 $\lfloor n/p \rfloor$ 个 $p$ 的倍数，恰好包含 $ \lfloor n/p^2 \rfloor$ 个 $p^2$ 的倍数，...... 依此类推。就直接完成了证明。
记
\begin{equation}
N = \frac{(2n)!}{(n!)^2} = \prod_{p \le 2n} p^{\alpha_p} ~,
\end{equation}
则利用这引理，立刻有
\begin{equation}
\alpha_p = \sum_{m=1}^{+\infty} \left( \left\lfloor \frac{2n}{p^m} \right\rfloor - 2 \left\lfloor \frac{n}{p^m} \right\rfloor\right) ~.
\end{equation}
这里指出，括号内的每一项要么是 $1$，要么是 $0$，这是由 $\lfloor 2n/p^m \rfloor$ 的奇偶性决定的。
我们考虑 $\psi(x)$ 的另一等价表达形式，是对于可能的最大的 $m$ 可以等价表示为
\begin{equation}
\psi(x) = \sum_{p^m \le x} m \ln p ~,
\end{equation}
从而这是一个最小公倍数的表示，故等价于
\begin{equation}
\psi(x) = \ln\left( [1, 2, 3, \dots, x] \right)~,
\end{equation}
或
\begin{equation}
\psi(x) = \sum_{p \le x} \left\lfloor \frac{\ln x}{\ln p} \right\rfloor \ln p ~.
\end{equation}
利用这式重新审视式 14 将不难得到
\begin{equation}
\alpha_p \le \left \lfloor \frac{\ln 2n}{\ln p} \right \rfloor ~,
\end{equation}
以及
\begin{equation}
\ln N = \sum_{p \le 2n} \alpha_p \ln p \le \sum_{p \le 2n} \left\lfloor \frac{\ln 2n}{\ln p} \right \rfloor \ln p= \psi(2n) ~.
\end{equation}
而其中，$N = (2n)!/n! \ge 2^n$，故 $\psi(2n) \ge n \ln 2$，这可以立刻得到 $\psi(x) \ge (x \ln 2)/4$，证毕！
致读者： 小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此，我们请求广大读者
热心打赏 ，使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损， 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款， 他们的付出帮助了 99% 的读者免费获取知识， 我们在此表示感谢。