背景：
对于二项式系数\(\require{AMSmath} \binom{x}{k}\)，我们已经清楚其基本定义如下：
$$
\binom{x}{k} = \frac{x(x-1)\cdots (x-k+1)}{k!}
$$
虽然我们总是可以通过上述基本定义出发确定一个二项式系数的大小，但往往显得不方便，因此就需要快速确定一个关于其大小的上限！
问题：
证明下面关于二项式系数\(\require{AMSmath} \binom{n}{k},\quad n \ge k \ge 0\)的上限：
$$
\binom{n}{k} \le \left( \frac{ne}{k}\right) ^k
$$
解构：
因为上述不等式中涉及到了自然底数e，因此自然而然想到的就是对数函数\(\phi(x) = lnx\)，所以问题转移至如何将上述不等式与对数函数关联起来？
既然对数函数\(\phi(x)\)是一个单调递增的函数，如果能够判定\(ln{\binom{n}{k}} \le ln{\left( \frac{ne}{k}\right) ^k}\)，则题干中的不等式即可成立！
详细解构过程如下：
左侧部分：
$$
\begin{align}
ln{\binom{n}{k}} &= ln{\frac{n!}{k!(n-k)!}} \\
&= \sum_{j=1}^{n}lnj – \sum_{i=1}^{k}lni-\sum_{l=1}^{n-k} lnl \\
&= \sum_{j=n-k+1}^{n}lnj – \sum_{l=1}^{k} lnl \\
&= \sum_{\lambda=1}^{k} \left( ln(n-k+\lambda) – ln {\lambda} \right) \\
&= \sum_{\lambda=1}^{k} ln(1+\frac{n-k}{\lambda}) \\
& \le k \cdot ln(1+n-k)
\end{align}
$$
右侧部分：
$$
\begin{align}
ln{\left( \frac{ne}{k} \right)^k}
&= k\cdot ln{\frac{ne}{k}} \\
\end{align}
$$
因此，如果能够证明\(k\cdot ln(1+n-k) \le k\cdot ln{\frac{ne}{k}}\)，那么我们就完成了关于原命题的论证工作！
记\(\phi(x) = ln(1+n-x)-lnn-1+lnx\)，则关于函数\(\phi(x)\)求导如下：
$$
\begin{align}
\phi'(x) &=\frac{1}{x} – \frac{1}{1+n-x} \\
&= \frac{1+n-2x}{x(1+n-x)} \\
\end{align}
$$
因此，函数\(\phi(x)\)的在区间\([0,\frac{1+n}{2}]\)上单调递增，在区间\([\frac{1+n}{2},n]\)上单调递减，则可以判断函数\(\phi(x)\)的上边界如下：
$$
\begin{align}
\phi(x) &\le \phi(\frac{n+1}{2}) \\
&= ln(1+n)-lnn – 1 \\
&\le 0 \\
\end{align}
$$
至此，我们已经完成了原命题的证明工作！
发表评论