组合恒等式-基于六个基本组合恒等式

摘要: 六个基本组合恒等式

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

组合的定义：

$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

二项式定理：

$$(1 + x)^{n} = \sum\limits_{i=0}\limits^{n}\binom{n}{i}x^{i}$$

基于组合的定义以及二项式定理，我们可以得到六个基本组合恒等式：

• (1) $\binom{n}{k} = \binom{n}{n-k}$
• (2) $\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$ （Pascal 恒等式）
• (3) $\binom{n}{k} = \frac{n}{k}\binom{n-1}{k-1}$
• (4) $\binom{n}{k}\binom{k}{m} = \binom{n}{m}\binom{n-m}{k-m} = \binom{n}{k-m}\binom{n-k+m}{m}$
• (5) $\sum\limits_{i=0}\limits^{n}\binom{n}{i} = 2^{n}$
• (6) $\sum\limits_{i=0}\limits^{n}(-1)^{i}\binom{n}{i} = 0$

这些组合恒等式中，(1)(2)(4) 可以直接从组合的定义式推导出；在 (4) 中令 $m = 1$ 即得到 (3)；在二项式定理中取 $x=1$ 和 $x=-1$ 可以得到 (5)(6)。

一些复杂的组合恒等式往往可以通过几个基本的组合恒等式，经过归纳、递推、指标变换等方法得到。

其中指标变换需要注意同事更换求和的上下限，例如：

$$\sum\limits_{n=0}\limits^{s}a_{n}x^{n} = \sum\limits_{n=2}\limits^{s+2}a_{n-2}x^{n-2} = \sum\limits_{n=1}\limits^{s+1}a_{n-1}x^{n-1}$$

下面我们看一些基于六个基本组合恒等式来推导别的组合恒等式的例子。

---

直接使用基本恒等式

$S_{n, m} = \sum\limits_{k=0}\limits^{m}(-1)^{k}\binom{n}{k}, m \leq n$

由基本恒等式 (6) 我们知道 $m = n$ 时，$S(n, m) = 0$；

下面考虑 $m < n$ 的情况。利用基本恒等式 (2)：

$$\begin{align} S_{n,m} &= \sum\limits_{k=0}\limits^{m}(-1)^{k}\binom{n}{k} \\ &= \sum\limits_{k=0}\limits^{m}(-1)^{k}(\binom{n-1}{k} + \binom{n-1}{k-1}) \\ &= 1 + \sum\limits_{k=1}\limits^{m}(-1)^{k}(\binom{n-1}{k} + \binom{n-1}{k-1}) \\ &= (-1)^{m}\binom{n-1}{m} \end{align}$$

---

$p_{n} = \sum\limits_{k=0}\limits^{n}\frac{1}{k+1}\binom{n}{k}$, $q_{n} = \sum\limits_{k=0}\limits^{n}(-1)^{k}\frac{1}{k+1}\binom{n}{k}$

由基本恒等式 (3)：

$$\frac{1}{k+1}\binom{n}{k} = \frac{1}{n+1}\binom{n+1}{k+1}$$

代入 $p_{n}$、$q_{n}$ 并应用基本恒等式 (5)(6) 即得：

$$p_{n} = \sum\limits_{k=0}\limits^{n}\frac{1}{k+1}\binom{n}{k} = \frac{1}{n+1}\sum\limits_{k=0}\limits^{n}\binom{n+1}{k+1} = \frac{1}{n+1}(2^{n+1}-1)$$ $$q_{n} = \sum\limits_{k=0}\limits^{n}(-1)^{k}\frac{1}{k+1}\binom{n}{k} = \frac{1}{n+1}\sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n+1}{k+1} = \frac{1}{n+1}$$

---

基本恒等式 + 指标变换

$\sum\limits_{k=0}\limits^{n}\binom{2n}{k} = 2^{2n-1} + \frac{1}{2}\binom{2n}{n}$

记 $a_{n} = \sum\limits_{k=0}\limits^{n}\binom{2n}{k}$，$b_{n} = \sum\limits_{k=n+1}\limits^{2n}\binom{2n}{k}$，由基本恒等式 (5)：

$$a_{n} + b_{n} = \sum\limits_{k=0}\limits^{2n}\binom{2n}{k} = 2^{2n}$$

对 $b_{n}$ 作指标变换：$k = 2n - l$：

$$\begin{align} b_{n} &= \sum\limits_{l = 0}\limits^{n-1}\binom{2n}{2n-l} = \sum\limits_{l = 0}\limits^{n-1}\binom{2n}{l} \\ &= \sum\limits_{l = 0}\limits^{n}\binom{2n}{l} - \binom{2n}{n} \\ &= a_{n} - \binom{2n}{n} \end{align}$$

代入即得：

$$a_{n} = 2^{2n-1} + \frac{1}{2}\binom{2n}{n}$$

---

$\sum\limits_{k=1}\limits^{n}k^{2}\binom{n}{k}$

由基本恒等式 (3)：

$$\sum\limits_{k=1}\limits^{n}k^{2}\binom{n}{k} = n\sum\limits_{k=1}\limits^{n}k\binom{n-1}{k-1}$$

对右边作指标变换 k - 1 = l，得：

$$\begin{align} \sum\limits_{k=1}\limits^{n}k\binom{n-1}{k-1} &= \sum\limits_{l=0}\limits^{n-1}(l+1)\binom{n-1}{l} \\ &= \sum\limits_{l=0}\limits^{n-1}l\binom{n-1}{l} + \sum\limits_{l=0}\limits^{n-1}\binom{n-1}{l} \\ &= \sum\limits_{l=0}\limits^{n-1}l\binom{n-1}{l} + 2^{n-1} \\ &= (n-1)\sum\limits_{l=1}\limits^{n-1}\binom{n-2}{l-1} + 2^{n-1} \quad\quad (基本恒等式 (3)) \\ &= (n-1)\sum\limits_{s=0}\limits^{n-2}\binom{n-2}{s} + 2^{n-1} \quad\quad (指标变换 l - 1 = s) \\ &= (n-1)2^{n-2} + 2^{n-1} \quad\quad (基本恒等式 (6)) \end{align}$$

因此：

$$\sum\limits_{k=1}\limits^{n}k^{2}\binom{n}{k} = n(n+1)2^{n-2}$$

---

$S_{mn} = \sum\limits_{k=m}\limits^{n}(-1)^{k}\binom{n}{k}\binom{k}{m} = (-1)^{m}\delta_{mn}$

克罗内克(Kronecker)函数如下：

$$\delta_{mn} = \left\{ \begin{array}{**lr**} 1, \quad (m = n) \\ 0, \quad (m \neq n) \\ \end{array} \right.$$

$m = n$ 时，$S_{mn} = (-1)^{m}\binom{m}{m}\binom{m}{m} = (-1)^{m}$

$m \neq n$ 时，利用基本恒等式 (4)：

$$\begin{align} S_{mn} &= \sum\limits_{k=m}\limits^{n}(-1)^{k}\binom{n}{k}\binom{k}{m} \\ &= \sum\limits_{k=m}\limits^{n}(-1)^{k}\binom{n}{m}\binom{k-m}{n-m} \\ &= \binom{n}{m}\sum\limits_{k=m}\limits^{n}(-1)^{k}\binom{k-m}{n-m} \\ &= \binom{n}{m}\sum\limits_{l=0}\limits^{n-m}(-1)^{l+m}\binom{n-m}{l} \quad\quad (指标变换 k - m = l) \\ &= (-1)^{m}\binom{n}{m}\sum\limits_{l=0}\limits^{n-m}(-1)^{l}\binom{n-m}{l} \\ &= 0 \quad\quad (基本恒等式 (6)) \end{align}$$

---

基本恒等式 + 递推

$\sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n}{k}\frac{m}{m + k} = (\binom{m+n}{n})^{-1}$

令 $b_{n} = \sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n}{k}\frac{m}{m + k}$，利用基本恒等式 (2)(3)(6)：

$$\begin{align} b_{n} &= \sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n}{k}\frac{m}{m + k} \\ &= 1 + \sum\limits_{k=1}\limits^{n-1}(-1)^{k}(\binom{n-1}{k} + \binom{n-1}{k-1})\frac{m}{m+k} + (-1)^{n}\frac{m}{m+n} \\ &= b_{n-1} + \sum\limits_{k=1}\limits^{n}(-1)^{k}\binom{n-1}{k-1}\frac{m}{m+k} \\ &= b_{n-1} + \frac{m}{n}\sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n}{k}\frac{k}{m+k} \\ &= b_{n-1} + \frac{m}{n}(\sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n}{k} - \sum\limits_{k=0}\limits^{n}(-1)^{k}\binom{n}{k}\frac{m}{m+k}) \\ &= b_{n-1} - \frac{m}{n}b_{n} \end{align}$$

得到递推公式：

$$b_{n} = \frac{n}{m + n}b_{n-1}$$

由递推公式可以得到 $b_{n} = (\binom{m + n}{n})^{-1}$

---

$\sum\limits_{k=1}\limits^{n}(-1)^{k+1}\frac{1}{k}\binom{n}{k}=\sum\limits_{i=1}\limits^{n}\frac{1}{i}$

利用基本恒等式 (2)(3)：

$$\frac{1}{k}\binom{n}{k} = \frac{1}{k}(\binom{n-1}{k} + \binom{n-1}{k-1}) = \frac{1}{k}\binom{n-1}{k} + \frac{1}{n}\binom{n}{k}$$

记 $f_{n} = \sum\limits_{k=1}\limits^{n}(-1)^{k+1}\frac{1}{k}\binom{n}{k}$，则：

$$\begin{align} f_{n} &= \sum\limits_{k=1}\limits^{n-1}(-1)^{k+1}\frac{1}{k}\binom{n}{k} + (-1)^{n+1}\frac{1}{n} \quad\quad (基本恒等式 (2)(3))\\ &= \sum\limits_{k=1}\limits^{n-1}(-1)^{k+1}\frac{1}{k}\binom{n-1}{k} + \frac{1}{n}\sum\limits_{k=1}\limits^{n-1}(-1)^{k+1}\binom{n}{k} + (-1)^{n+1}\frac{1}{n} \\ &= f_{n-1} + \frac{1}{n}\sum\limits_{k=1}\limits^{n}(-1)^{k+1}\binom{n}{k} \quad\quad (基本恒等式 (6)) \\ &= f_{n-1} + \frac{1}{n} \end{align}$$

得到递推公式：

$$f_{n} = f_{n-1} + \frac{1}{n}$$

由递推公式得到：$f_{n} = 1 + \frac{1}{2} + \cdots \frac{1}{n}$

---

$\sum\limits_{k=0}\limits^{2n-1}(-1)^{k+1}(k+1)(\binom{2n}{k})^{-1}$

记 $y_{n} = \sum\limits_{k=0}\limits^{2n-1}(-1)^{k+1}(k+1)(\binom{2n}{k})^{-1}$，利用基本恒等式 (3)：

$$\frac{k + 1}{\binom{2n}{k}} = \frac{2n + 1}{\binom{2n+1}{k+1}} = \frac{2n + 1}{\binom{2n+1}{2n-k}} = \frac{2n - k}{\binom{2n}{2n-k-1}}$$

于是：

$$y_{n} = \sum\limits_{k=0}\limits^{2n-1}(-1)^{k+1}\frac{2n-k}{\binom{2n}{2n-k-1}}$$

作指标变换 $l = 2n-k-1$，当 $k$ 从 0 变到 $2n-1$ 时，$l$ 从 $2n-1$ 变到 0，因此：

$$y_{n} = \sum\limits_{l=0}\limits^{2n-1}(-1)^{2n-l}\frac{l+1}{\binom{2n}{l}} = \sum\limits_{l=0}\limits^{2n-1}(-1)^{l}\frac{l+1}{\binom{2n}{l}} = -y_{n}$$

因此 $y_{n} = 0$

类似的方法可以证明 $\sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}\frac{n-k}{\binom{2n}{k}} = 0$。

---

$\sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}(\binom{2n}{k})^{-1}$

记 $a_{n} = \sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}(\binom{2n}{k})^{-1}$，$b_{n} = \sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}k(\binom{2n}{k})^{-1}$。

则由前面的结论 $\sum\limits_{k=0}\limits^{2n-1}(-1)^{k+1}(k+1)(\binom{2n}{k})^{-1} = 0$：

$$\begin{align} a_{n} + b_{n} &= \sum\limits_{k=1}\limits^{2n-1}(-1)^{k+1}(k+1)(\binom{2n}{k})^{-1} \\ &= \sum\limits_{k=0}\limits^{2n-1}(-1)^{k+1}(k+1)(\binom{2n}{k})^{-1} + 1 \\ &= 1 \end{align}$$

再由前面的结论 $\sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}\frac{n-k}{\binom{2n}{k}} = 0$：

$$na_{n} - b_{n} = \sum\limits_{k=1}\limits^{2n-1}(-1)^{k-1}\frac{n-k}{\binom{2n}{k}} = 0$$

两式相加，得到 $a_{n} = \frac{1}{n+1}$，$b_{n} = na_{n} = \frac{n}{n+1}$

---

基本恒等式 + 归纳

$\sum\limits_{k=1}\limits^{n-1}\frac{1}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1}$

下面证明 $\sum\limits_{k=1}\limits^{n-1}\frac{1}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} = \frac{1}{n}\binom{2(n-1)}{n-1}, n=2,3,\cdots$

由于 $\frac{n}{k(n-k)} = \frac{1}{k} + \frac{1}{n-k}$，将待证明公式两边乘以 $n$：

$$\begin{align} & \sum\limits_{k=1}\limits^{n-1}\frac{n}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} \\ = & \sum\limits_{k=1}\limits^{n-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} + \sum\limits_{k=1}\limits^{n-1}\frac{1}{n-k}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} \\ \end{align}$$

在右边第二个和式中令 $n - k = l$ 得：

$$\sum\limits_{k=1}\limits^{n-1}\frac{1}{n-k}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} = \sum\limits_{l=1}\limits^{n-1}\frac{1}{l}\binom{2(n-l-1)}{n-l-1}\binom{2(l-1)}{l-1}$$

因此可以看到，右边的两个和式是相同的，因此得到以下公式，该公式后面要用到，记为【公式 A】：

$$\begin{align} & \sum\limits_{k=1}\limits^{n-1}\frac{n}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} \\ = & 2\sum\limits_{k=1}\limits^{n-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} \\ \end{align}$$

于是，待证明公式变成：

$$\sum\limits_{k=1}\limits^{n-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} = \frac{1}{2}\binom{2(n-1)}{n-1}$$

上式可以用数学归纳法证明。首先 $n=2$ 时成立。假设 $n=m$ 时成立，当 $n=m+1$ 时，上式左端为：

$$\begin{align} & \sum\limits_{k=1}\limits^{m}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k)}{m-k} \\ = & \sum\limits_{k=1}\limits^{m-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k)}{m-k} + \frac{1}{m}\binom{2(m-1)}{m-1} \end{align}$$

注意到：

$$\begin{align} \binom{2(m-k)}{m-k} &= \frac{(2m-2k)!}{((m-k)!)^{2}} \\ &= \frac{(2m-2k)(2m-2k-1)}{(m-k)^{2}} \times \frac{(2m-2k-2)!}{((m-k-1)!)^{2}} \\ &= 2(2-\frac{1}{m-k})\binom{2(m-k-1)}{m-k-1} \end{align}$$

代入得：

$$\begin{align} & \sum\limits_{k=1}\limits^{m}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k)}{m-k} \\ = & \sum\limits_{k=1}\limits^{m-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k)}{m-k} + \frac{1}{m}\binom{2(m-1)}{m-1} \\ = & \sum\limits_{k=1}\limits^{m-1}\frac{2}{k}(2-\frac{1}{m-k})\binom{2(k-1)}{k-1}\binom{2(m-k-1)}{m-k-1} + \frac{1}{m}\binom{2(m-1)}{m-1} \\ = & 4\sum\limits_{k=1}\limits^{m-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k-1)}{m-k-1} \\ & - 2\sum\limits_{k=1}\limits^{m-1}\frac{1}{k(m-k)}\binom{2(k-1)}{k-1}\binom{2(m-k-1)}{m-k-1} + \frac{1}{m}\binom{2(m-1)}{m-1} \\ \end{align}$$

由归纳假定：

$$\sum\limits_{k=1}\limits^{m-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k-1)}{m-k-1} = \frac{1}{2}\binom{2(m-1)}{m-1} \\$$

以及前面的【公式 A】：

$$\sum\limits_{k=1}\limits^{m-1}\frac{m}{k(m-k)}\binom{2(k-1)}{k-1}\binom{2(m-k-1)}{m-k-1} = 2\sum\limits_{k=1}\limits^{m-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k-1)}{m-k-1} \\$$

得：

$$\begin{align} & \sum\limits_{k=1}\limits^{m}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k)}{m-k} \\ = & 4(1 - \frac{1}{m})\sum\limits_{k=1}\limits^{m-1}\frac{1}{k}\binom{2(k-1)}{k-1}\binom{2(m-k-1)}{m-k-1} + \frac{1}{m}\binom{2(m-1)}{m-1} \\ = & 4(1 - \frac{1}{m})\frac{1}{2}\binom{2(m-1)}{m-1} + \frac{1}{m}\binom{2(m-1)}{m-1} \\ = & (2 - \frac{1}{m})\binom{2(m-1)}{m-1} \\ = & \frac{2m(2m-1)}{m^{2}}\frac{(2m-2)!}{((m-1)!)^{2}} \\ = & \frac{1}{2}\binom{2m}{m} \end{align}$$

因此待证公式在 $n = m + 1$ 时成立。最终得证公式如下：

$$\sum\limits_{k=1}\limits^{n-1}\frac{1}{k(n-k)}\binom{2(k-1)}{k-1}\binom{2(n-k-1)}{n-k-1} = \frac{1}{n}\binom{2(n-1)}{n-1}, n=2,3,\cdots$$

该公式在推导 $\sqrt{1+x}$ 的展开式时需要用到。

---