微积分方法证明组合恒等式

摘要: 组合恒等式：微积分方法

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

---

在组合数学、概率、分析中，经常会在推导中使用组合恒等式，很多组合恒等式事先不知道的话，是不容易看出来的。在文章 组合恒等式-基于六个基本组合恒等式 中，我们介绍了六个基本组合恒等式，很多组合恒等式都是由基本恒等式经过简单推导得出的。

组合恒等式没有统一方法，在实践中根据具体问题，有组合变换的呼你公式、母函数、差分、复数、递推等方法。本文我们看一下通过微积分推导含和式的组合恒等式的方法。

在文章 对和式求导积分的处理方法，二项(泊松)分布求和转换为Beta(Gamma)分布积分 中我们讨论过类似的话题，那篇文章中的方法是根据微积分基本定理，先求导再积分，或先积分再求导来处理和式，凑出二项式定理。而本文的做法是从二项式定理出发，通过两边求导，或两边积分的方式凑出待证明的组合恒等式。可以理解为一种方法的两个方向，可以对比着看。

求导法解决 $\sum\limits_{k=0}\limits^{n}(k+t_{1})^{t_{2}}\binom{n}{k}$

我们经常会遇到下面这些形式的组合恒等式：

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

这类组合恒等式的特点是左端的形式都是 $\sum\limits_{k=0}\limits^{n}(k+t_{1})^{t_{2}}\binom{n}{k}$。证明这类组合恒等式时我们可以从二项式定理出发，通过两边求导的方式，凑成待证明的公式。具体步骤如下。

两边求导法过程

首先从二项式定理出发：

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

两端同乘 $x^{t_{1}}$，得到

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

然后两边求导，得：

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

记 $f_{1}(x) = t_{1}x^{t_{1}-1}(1 + x)^{n} + nx^{t_{1}}(1 + x)^{n-1}$，两边同乘 $x$ 然后求导，得：

$$(xf_{1}(x))^{'} = (\sum\limits_{k=0}\limits^{n}(k + t_{1})\binom{n}{k}x^{k+t_{1}})^{'} \\ \Rightarrow f_{1}(x) + xf_{1}^{'}(x) = \sum\limits_{k=0}\limits^{n}(k + t_{1})^{2}\binom{n}{k}x^{k+t_{1}-1}$$

记 $f_{2}(x) = f_{1}(x) + xf_{1}^{‘}(x)$，然后继续两边同乘 $x$ 然后求导，得：

$$f_{3}(x) = f_{2}(x) + xf_{2}^{'}(x) = \sum\limits_{k=0}\limits^{n}(k + t_{1})^{3}\binom{n}{k}x^{k+t_{1}-1}$$

然后循环前面的【两边同乘 x 然后求导】的过程，$t_{2}$ 决定了循环次数。

记 $f_{i+1}(x) = f_{i}(x) + xf_{i}^{‘}(x)$，$i = 1,2,\cdots,t_{2}-1$，需要循环 $t_{2}-1$ 次，最终得到：

$$f_{t_{2}}(x) = f_{t_{2}-1}(x) + xf_{t_{2}-1}^{'}(x) = \sum\limits_{k=0}\limits^{n}(k + t_{1})^{t_{2}}\binom{n}{k}x^{k+t_{1}-1}$$

然后令 $x = 1$，得到了我们要解决的 $\sum\limits_{k=0}\limits^{n}(k+t_{1})^{t_{2}}\binom{n}{k}$。对 x 取不同的值可以得到不同的恒等式。

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

两边求导

对比前面的推导过程，本题就是 $t_{1} = 1, t_{2} = 2$ 的情况。按照流程来即可。

从二项式定理出发：

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

两端同乘 $x^{t_{1}} = x$ 然后求导，得：

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

再同乘 $x$ 然后求导，得：

$$f_{2}(x) = (xf_{1}(x))^{'} = \sum\limits_{i=0}\limits^{n}(k+1)^{2}\binom{n}{k}x^{k}$$

至此等式右边取 $x=1$ 就凑出了待求的 $\sum\limits_{i=0}\limits^{n}(k+1)^{2}\binom{n}{k}$，按步骤计算出等式左边的 $f_{2}(1)$ 即可：

$$\begin{align} f_{1}^{'}(x) &= n(1 + x)^{n-1} + (n(1+x)^{n-1} + nx(n-1)(1 + x)^{n-2}) \\ &= 2n(1+x)^{n-1} + n(n-1)x(1+x)^{n-2} \end{align}$$ $$\begin{align} f_{2}(x) &= (xf_{1}(x))^{'} \\ &= f_{1}(x) + xf_{1}^{'}(x) \\ &= (1+x)^{n} + 3nx(1+x)^{n-1} + n(n-1)x^{2}(1+x)^{n-2} \end{align}$$

取 $x=1$，有：

$$\begin{align} f_{2}(1) &= 2^{n} + 3n2^{n-1} + n(n-1)2^{n-2} \\ &= (4 + 5n + n^{2})2^{n-2} \end{align}$$

一边先积分再求导

本题也可以积分先积分再求导。先对原始待求公式变形：

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

变形的目标是凑出 $k(k+1)(k+2)\cdots$ 这种因子形式。这样在后续的积分中，这些因子会逐步销掉，以上面的为例。

记 $f_{1}(x) = \sum\limits_{k=0}\limits^{n}k(k+1)\binom{n}{k}x^{k-1}$, $f_{2}(x) = \sum\limits_{k=0}\limits^{n}(k+1)\binom{n}{k}x^{k}$。于是待求公式的答案为 $f_{1}(1) + f_{2}(1)$。

对 $f_{1}(x)$ 先积分两次：

$$\begin{align} \int(\int f_{1}(x)dx)dx &= \int (\int \sum\limits_{k=0}\limits^{n}k(k+1)\binom{n}{k}x^{k-1} dx)dx \\ &= \int \sum\limits_{k=0}\limits^{n}(k+1)\binom{n}{k}x^{k} dx \\ &= \sum\limits_{k=0}\limits^{n}\binom{n}{k}x^{k+1} \\ &= x(1 + x)^{n} \end{align}$$

然后再求导两次：

$$\begin{align} f_{1}(x) &= (x(1+x)^{n})^{''} \\ &= ((1+x)^{n} + xn(1+x)^{n-1})^{'} \\ &= (n(1+x)^{n-1} + (n(1+x)^{n-1} + nx(n-1)(1+x)^{n-2})) \\ &= 2n(1+x)^{n-1} + n(n-1)x(1+x)^{n-2} \end{align}$$

对于 $f_{2}(x)$，先积分再求导一轮即可。

$$\begin{align} f_{2}(x) &= (\int f_{2}(x) dx)^{'} \\ &= (\int \sum\limits_{k=0}\limits^{n}(k+1)\binom{n}{k}x^{k} dx)^{'} \\ &= (\sum\limits_{k=0}\limits^{n}\binom{n}{k}x^{k+1})^{'} \\ &= (x(1+x)^{n})^{'} \\ &= (1+x)^{n} + xn(1+x)^{n-1} \\ \end{align}$$

于是 $f_{1}(1) = 2n2^{n-1} + n(n-1)2^{n-2}$，$f_{2}(1) = 2^{n} + n2^{n-1}$。结果为：

$$\begin{align} \sum\limits_{k=0}\limits^{n}(k+1)^{2}\binom{n}{k} &= f_{1}(1) + f_{2}(1) \\ &= 2n2^{n-1} + n(n-1)2^{n-2} + 2^{n} + n2^{n-1} \\ &= (n^{2} + 5n + 4)2^{n-2} \\ \end{align}$$

积分法解决 $\sum\limits_{k=0}\limits^{n}\frac{\binom{n}{k}t^{k+m}}{(k+1)(k+2)\cdots(k+m)}$

先看几个例子：

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

这类组合恒等式的特点是左端的形式都是 $\sum\limits_{k=0}\limits^{n}\frac{\binom{n}{k}t^{k+m}}{(k+1)(k+2)\cdots(k+m)}$。证明这类组合恒等式时我们可以从二项式定理出发，通过两边积分的方式，凑成待证明的公式。具体步骤如下。

两边积分法过程

首先从二项式定理出发：

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

两端同时取 0 到 $t$ 的定积分，得到：

$$\int_{0}^{t}(1 + x)^{n}dx = \int_{0}^{t}\sum\limits_{k=0}\limits^{n}\binom{n}{k}x^{k}dx$$ $$\Rightarrow \frac{(1 + t)^{n+1}}{n+1} - \frac{1}{n+1} = \sum\limits_{k=0}\limits^{n}\frac{1}{k+1}\binom{n}{k}t^{k+1}$$

记 $f_{1}(t) = \frac{(1 + t)^{n+1}}{n+1} - \frac{1}{n+1}$，于是 $f_{1}(t) = \sum\limits_{k=0}\limits^{n}\frac{1}{k+1}\binom{n}{k}t^{k+1}$。

然后再两端取 0 到 t 的定积分，得：

$$f_{2}(t) = \int^{t}_{0}f_{1}(x)dx = \sum\limits_{k=0}\limits^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}t^{k+2}$$

循环 m 次，直至等式变形为：

$$f_{m}(t) = \int^{t}_{0}f_{m-1}(x)dx = \sum\limits_{k=0}\limits^{n}\frac{1}{(k+1)(k+2)\cdots(k+m)}\binom{n}{k}t^{k+m}$$

取 t 为不同的值可以得到不同的组合恒等式。

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

对比前面的推导过程，本题就是 $m = 2, t = 1$ 的情况。按照流程来即可。

从二项式定理出发，做两次两边取 0 到 t 的积分：

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

第一次两边取 0 到 t 的积分：

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

第二次两边取 0 到 t 的积分：

$$f_{2}(t) = \int^{t}_{0}f_{1}(x)dx = \sum\limits_{k=0}\limits^{n}\frac{1}{(k+1)(k+2)}\binom{n}{k}t^{k+2}$$

上式右边取 $t=1$ 得到目标结果，计算左边的 $f_{2}(1)$ 即可，结果如下：

$$f_{2}(t) = \frac{(1+t)^{n+2}}{(n+1)(n+2)} - \frac{t}{n+1} - \frac{1}{(n+1)(n+2)}$$

取 $t=1$ 得：

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

总结与综合应用

前面介绍的是比较定式化的简单问题，重在理解思想。对于复杂的问题，从待证公式凑已知公式，还是从已知公式凑待证公式；时先求导再积分、还是先积分再求导；是两边求导、还是两边积分等，各种选择都需要试。理论上一个方向能凑出来，反向也应该能凑出来，哪个好凑就走哪个。

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

这个例子在文章 对和式求导积分的处理方法，二项(泊松)分布求和转换为Beta(Gamma)分布积分 中我们讨论过，那篇文章中是从待证公式出发，通过先求导再积分的方式解决的，过程中凑了二项式定理、等比数列求和，详细过程可以看那篇文章。

这里用相反的方向推导，也就是从二项式定理出发，通过两边同时进行求导、积分等操作来凑待证公式。

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

当 $x \neq 0$，两边同除 $x$，得：

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

注意到 $\lim\limits_{x\rightarrow 0}\frac{(1+x)^{n}-1}{x} = \lim\limits_{x\rightarrow 0}\frac{n(1+x)^{n-1}}{1} = n$，可以补充定义 $f(0) = n$，这样 $f(x)$ 在 $[-1, 0]$ 上连续，从而可积，进而可以等式两边同时在 $[-1, 0]$ 上积分，从而凑到待证公式。

等式左端，做变量代换 $1 + x = t$，以及等比数列求和公式，得到：

$$\begin{align} \int_{-1}^{0}f(x)dx &= \int_{-1}^{0}\frac{(1 + x)^{n} - 1}{x}dx \\ &= \int_{0}^{1}\frac{t^{n}-1}{t-1}dt \\ &= \int_{0}^{1}(t^{n-1} + t^{n-2} + \cdots + t + 1)dt \\ &= 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} \\ \end{align}$$

等式右端：

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

本题最开始的对二项式定理两边同除 $x$，以及后来的在 $[-1, 0]$ 上积分都非常难想，可能还是对原公式求导去凑二项式定理更好找到路。

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

从二项式定理出发：

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

两边同乘 $x^{m}$：

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

两边同时在 $[0, 1]$ 上积分，即可凑到待证公式：

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

此时等式左端为 Beta 函数：

$$\begin{align} \int^{1}_{0}x^{m}(1 - x)^{n}dx &= Beta(m+1, n+1)\\ &= \frac{\Gamma(m+1)\Gamma(n+1)}{\Gamma(m+n+2)} \\ &= \frac{m!n!}{(m+n+1)!} \\ \end{align}$$

难点依然是两边同乘 $x^{m}$ 以及两边同时在 $[0, 1]$ 上积分的操作，目的很简单就是凑到待证公式，但是需要一点灵感才能发现。

---