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

  |  

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

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


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

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

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

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

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

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

两边求导法过程

首先从二项式定理出发:

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

然后两边求导,得:

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

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

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

记 $f_{i+1}(x) = f_{i}(x) + xf_{i}^{‘}(x)$,$i = 1,2,\cdots,t_{2}-1$,需要循环 $t_{2}-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$ 的情况。按照流程来即可。

从二项式定理出发:

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

再同乘 $x$ 然后求导,得:

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

取 $x=1$,有:

一边先积分再求导

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

变形的目标是凑出 $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)$ 先积分两次:

然后再求导两次:

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

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

积分法解决 $\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{\binom{n}{k}t^{k+m}}{(k+1)(k+2)\cdots(k+m)}$。证明这类组合恒等式时我们可以从二项式定理出发,通过两边积分的方式,凑成待证明的公式。具体步骤如下。

两边积分法过程

首先从二项式定理出发:

两端同时取 0 到 $t$ 的定积分,得到:

记 $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 的定积分,得:

循环 m 次,直至等式变形为:

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

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

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

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

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

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

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

取 $t=1$ 得:

总结与综合应用

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

$\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)分布积分 中我们讨论过,那篇文章中是从待证公式出发,通过先求导再积分的方式解决的,过程中凑了二项式定理、等比数列求和,详细过程可以看那篇文章。

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

当 $x \neq 0$,两边同除 $x$,得:

注意到 $\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$,以及等比数列求和公式,得到:

等式右端:

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

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

从二项式定理出发:

两边同乘 $x^{m}$

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

此时等式左端为 Beta 函数:

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


Share