关于Granville证明Sylvester-Schur定理中第一个不等式的推导疑问

阿华AIGC实验室

2026-4-16

Granville在他的著作《Number Theory Revealed: A Masterclass》中证明了Sylvester-Schur定理。以下是该证明的一部分：

Proof. [...] 当 $n \geq 3k$ 时，根据附录4D中的练习4.14.2，有
$$
\frac{\left(4^4 / 3^3\right)k}{e k} \leq\binom{4k}{k} \leq\binom{n+k}{k} \leq k^{\frac{1}{2} k^{3 / 4}} 4^{k-1}
$$
而这个式子对于所有 $k \geq 1$ 都不成立。

用到的练习题如下：

Exercise 4.14.2：证明当 $N \geq M$ 时，
$$
\frac{\left(\frac{N}{e}\right)^{N}{\left(\frac{M}{e}\right)}M} \leq \frac{N!}{M!} \leq \frac{\left(\frac{N}{e}\right)^{{N+1}}{\left(\frac{M}{e}\right)}{M+1}}.
$$

我已经完成了这道练习题的证明，但在理解它在Sylvester-Schur定理证明中的应用时，始终搞不懂第一个不等式 $\frac{\left(4^4 / 3^3\right)k}{e k} \leq\binom{4k}{k}$ 是怎么来的，其余部分的推导我都能理解。我自己尝试推导得到的内容是：F...

嘿，我来帮你捋清楚这个第一个不等式的来龙去脉！其实核心就是把练习4.14.2的阶乘上下界套到组合数上，而且Granville用的是一个比较宽松的下界，目的是让后续的矛盾推导更简单，咱们一步步来：

首先，组合数 $\binom{4k}{k}$ 可以写成阶乘的比值：
$$
\binom{4k}{k} = \frac{(4k)!}{k! \cdot (3k)!}
$$

接下来用练习4.14.2的公式：

对于分子 $(4k)!$，我们用下界：$\frac{(4k)!}{0!} \geq \left(\frac{4k}{e}\right)^{4k}$，也就是 $(4k)! \geq \left(\frac{4k}{e}\right)^{4k}$
对于分母里的 $k!$ 和 $(3k)!$，我们用上界：$k! \leq \left(\frac{k}{e}\right)^{k+1}$，$(3k)! \leq \left(\frac{3k}{e}\right)^{3k+1}$

现在把这些代入组合数的表达式，计算它的下界：
$$
\binom{4k}{k} \geq \frac{\left(\frac{4k}{e}\right)^{{4k}}{\left(\frac{k}{e}\right)}{k+1} \cdot \left(\frac{3k}{e}\right)^{3k+1}}
$$

咱们把这个式子展开化简：
$$
\begin{align*}
\frac{\left(\frac{4k}{e}\right)^{{4k}}{\left(\frac{k}{e}\right)}{k+1} \cdot \left(\frac{3k}{e}\right)^{3k+1}} &= \frac{4^{4k} k^{4k} e^{k+1} e^{3k+1}}{e{4k} k^{k+1} 3^{3k} k^{3k+1}} \
&= \frac{4^{4k} e^{4k+2}}{3{3k} e^{4k} k^{k+1+3k+1 -4k}} \
&= \frac{4^{4k} e^2}{3{3k} k^2}
\end{align*}
$$

哎，这得到的是一个比Granville给出的下界更紧的结果，但Granville用的是 $\frac{(4^4/33)^k}{e k}$，这明显比我们算出来的小很多啊？其实原因很简单——Granville故意用了一个更宽松的下界！因为只要这个宽松的下界小于等于组合数，后续的不等式链就能成立，而且更容易导出矛盾。

咱们可以验证一下：因为 $e^2 /k > 1/(e k)$（当k≥1时，$e^2≈7.389$，显然远大于1/e≈0.367），所以：
$$
\frac{(4^4/33)^k}{e k} < \frac{4^{4k} e^2}{3{3k} k^2} \leq \binom{4k}{k}
$$

这样一来，Granville的第一个不等式 $\frac{(4^4/33)^k}{e k} \leq\binom{4k}{k}$ 就自然成立了！他这么做是为了让后面的不等式推导更简洁，不用纠结于太精确的常数项，毕竟最终目的是要证明整个不等式链不成立，用一个宽松的下界完全足够。

如果还是觉得困惑，咱们换个角度用对数估计：
取组合数的自然对数：
$$
\ln \binom{4k}{k} = \ln(4k)! - \ln(k)! - \ln(3k)!
$$
用练习4.14.2的下界 $\ln N! \geq N\ln N - N$ 和上界 $\ln N! \leq (N+1)\ln N - N$ 代入，展开后合并同类项：
$$
\ln \binom{4k}{k} \geq k \ln\left(\frac{4^4}{33}\right) - \ln(3k)
$$
取指数后得到：
$$
\binom{4k}{k} \geq \frac{(4^4/33)^k}{3k}
$$
因为 $e < 3$，所以 $\frac{(4^4/33)^k}{e k} > \frac{(4^4/33)^k}{3k}$，那这个更宽松的下界当然也满足 $\leq \binom{4k}{k}$。