具体数学基本恒等式旁注

注：本节内容为《具体数学》(原书第二版) 第五章二项式系数 5.1 基本恒等式的旁注。

P129 关于超出范围的整数 $k$ 的讨论

$$
\binom{n}{k} = 0, k < 0
$$

$$
\binom{n}{k} = \frac {n^{\underline{k}}}{k!} = \frac {n!\times 0 \times (-1)^{k-n-1}(k-n-1)!}{k!} = 0, k > n \geq 0, n,k \in \mathbb Z
$$

帕斯卡定理的推论

我在其他文章里写过，这里就再写一遍吧。

$$
\sum_{i=0}^k \binom{n}{n+i} =\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} = \binom{n+k+1}{n+1}
$$

证明：

$$
\begin{aligned}
\sum_{i=0}^k \binom{n}{n+i} &=\binom{n}{n} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} \\
&= \binom{n+1}{n+1} + \binom{n+1}{n} + \cdots + \binom{n+k}{n} \\
&= \binom{n+2}{n+1} + \binom{n+2}{n} + \cdots + \binom{n+k}{n} \\
&= \cdots \\
&= \binom{n+k+1}{n+1}
\end{aligned}
$$

再列一下书上证明的其他推论：

$$
\sum_{i \leq n} \binom{n+i}{i} = \binom{n}{0} + \binom{n+1}{1} + \cdots + \binom{n + k}{k} = \binom{n+k+1}{k}
$$

$$
\sum_{i = 0}^k \binom{i}{n} = \binom{0}{n} + \binom{1}{n} + \cdots + \binom{k}{n} = \binom{k+1}{n+1}
$$

P135 证明二项式定理的级数收敛

二项式定理：

$$
(1+z)^r = \sum_{k=-\infty}^{+\infty} \binom{r}{k} z^k, |z| < 1
$$

证明：

令

$$
f(z) = (1+z)^r
$$

不难由归纳法证明

$$
f^{(k)} (z) = r^{\underline{k}}(1+z)^{r-k}
$$

根据泰勒级数：

$$
f(z) = \frac {f(0)} {0!} z^0 + \frac {f'(0)}{1!} z^1 + \frac {f''(0)}{2!} z^2 + \cdots = \sum_{k \geq 0} \frac {f^{(k)}(0)} {k!} z^k
$$

不难发现，

$$
(1+z)^r = \sum_{k=-\infty}^{-1} \binom{r}{k} z^k + \sum_{k=0}^{+\infty} \binom{r}{k} z^k = \sum_{k\geq 0} \binom{r}{k} z^k
$$

而其中的每一项都与泰勒级数对应：

$$
\binom{r}{k}z^k = \frac {f^{(k)}(0)} {k!}z^k
$$

故恒等式成立。接下来，我们要证明收敛。

不难发现：

$$
\sum_{k\geq 0} \binom{r}{k} z^k \leq \sum_{k\geq 0} \left | \binom{r}{k} z^k \right |
$$

根据比较审敛法，我们证明右侧那个级数收敛即可。右侧级数：

$$
u_k = \left | \binom{r}{k} z^k \right |
$$

$$
\frac {u_{k+1}} {u_k} = \left | \frac {\binom{r}{k+1} z^{k+1}} {\binom{r}{k} z^k} \right | = \left | \frac {r-k} {k+1} z \right | = \left | \left ( \frac {r+1} {k+1} - 1 \right) z \right|
$$

$$
\rho = \lim_{k \rightarrow \infty} \frac {u_{k+1}} {u_k} = |z| < 1
$$

故根据比值审敛法，收敛。故原级数收敛。

P137 证明 $(5.18)$

$$
\sum_{k\leq m} \binom rk \left ( \frac r 2 - k\right) = \frac {m+1} 2 \binom{r}{m+1}
$$

假设 $m$ 成立，归纳 $m+1$

$$
\begin{aligned}
&\sum_{k\leq m+1} \binom rk \left ( \frac r 2 - k\right) \\
=& \sum_{k\leq m} \binom rk \left ( \frac r 2 - k\right) + \binom{r}{m+1}\left( \frac r 2 - m - 1\right) \\
=& \frac {m+1} 2 \binom{r}{m+1} + \binom{r}{m+1}\left( \frac r 2 - m - 1\right) \\
=& \frac {r-m-1} {2} \binom{r}{m+1} \\
=& \frac {r-m-1} {2} \frac {m+2} {r-m-1} \binom{r}{m+2} = \frac {m+2}2\binom{r}{m+2}
\end{aligned}
$$

证毕。

P137 证明 $(5.19)$

P138, 递归式补充：这一页第二个和第三个公式：

$$
\sum_{k \leq m} \rightarrow \sum_{k \leq m-1} + \sum_{k=m}
$$

$$
\sum_{k \leq m} \rightarrow \sum_{k-1 \leq m-1}
$$

关于等式右侧的补充，记

$$
\begin{aligned}
S_m &= \sum_{k \leq m} \binom{-r}{k}(-x)^k(x+y)^{m-k} \\
&= \sum_{k \leq m-1} \binom{-r}{k}(-x)^k(x+y)^{m-k} + \binom{-r}{m}(-x)^m \\
&=(x+y)S_{m-1} + \binom{-r}{m}(-x)^m
\end{aligned}
$$

P138 $(5.19)$ 推论补充

取 $x=y=1$, $r=m+1$ 时：

$$
\sum_{k \leq m} \binom{2m+1}{k} = \sum_{k\leq m} \binom{-m-1}{k}(-1)^k 2^{m-k} = \sum_{k \leq m} \binom{m+k}{k}2^{m-k}
$$

后两步使用了上指标反转。

以及，左边之所以是上指标是 $2m+1$ 的二项式系数的一半，是因为我们看帕斯卡三角形，对于 $m$ 而言，$2m+1$ 层有 $2m+2$ 项（从零开始），所以 $0\sim m$ 正好记一半，$m+1$ 项。以及，这里还用到了：

$$
(1+1)^n = \sum_k \binom{n}{k}
$$

P139 多项式定理补充

二项式定理的多项式系数写法：

$$
(x+y)^n = \sum_{0\leq a, b \leq n, a+b=n} \frac {(a+b)!} {a!b!} x^ay^b = \sum_{0\leq a, b \leq n, a+b=n} \binom{a+b}{a,b} x^ay^b
$$

以及多项式系数的组合意义：

$$
\begin{aligned}
\binom{a_1+a_2+\cdots+a_m}{a_1,a_2,\cdots,a_m} &= \frac {(a_1+a_2+\cdots+a_m)!}{a_1!a_2!\cdots a_m!} \\
&= \binom{a_1+a_2+\cdots+a_m}{a_2+a_3+\cdots+a_m}\cdots\binom{a_{m-1}+a_m}{a_m}
\end{aligned}
$$

组合意义：