问题

前几天在做探究性题目的时候碰到了一个组合恒等式： \[ \sum_{k=1}^nk2^k\binom{2n-k-1}{n-1}=n\binom{2n}{n} \] 这个恒等式的右边最初是 Mathematica 给出的，当时把就我惊到了，一开始想用 combinatorial proof 的方法来证，但是想了两个晚上也想不出，自己的数学实在是太烂啦 =_= 之后在翻《具体数学》的时候学了一点超几何函数的皮毛，总算使用超几何的方法诡异地证出来了。我又在 Math StackExchange 上发帖征集了一些初等的证明，在这里做一个汇总。

初等证明

引理 1： \[ \sum_{k=n}^{2n}2^{-k}\binom{k}{n}=1 \] 证明：源于这个帖子。这个式子等价于： \[ \sum_{k=n}^{2n}2^{2n-k}\binom{k}{n}=4^n \Rightarrow \sum_{k=0}^{n}2^{k}\binom{2n-k}{n}=4^n \] 利用数学归纳法，令 \[ \begin{aligned} S_n&=\sum_{k=0}^{n}2^{k}\binom{2n-k}{n}\\ &=\sum_{k=0}^{n}2^{k}\binom{2n-k}{n-k} \\ &=\sum_{k=0}^{n}2^{n-k}\binom{n+k}{n} \end{aligned} \] 于是 \[ \begin{aligned} S_{n+1} &= \sum_{k=0}^{n+1}2^{n+1-k}\binom{n+1+k}{n+1} \\ &= \sum_{k=0}^{n+1}2^{n+1-k}\left[\binom{n+k}{n+1} + \binom{n+k}{n}\right] \\ &= \binom{2n+1}{n} + 2\sum_{k=0}^{n}2^{n-k}\binom{n+k}{n} + \sum_{k=0}^{n+1}2^{n+1-k}\binom{n+k}{n+1}\\ &= \binom{2n+1}{n} + 2S_n + \binom{2n+1}{n+1} + \sum_{k=1}^{n}2^{n+1-k}\binom{n+k}{n+1} \\ &= \binom{2n+2}{n+1} + 2\cdot4^n + \sum_{k=0}^{n-1}2^{n-k}\binom{n+1+k}{n+1} \\ &= \binom{2n+2}{n+1} + 2\cdot4^n + \frac{1}{2}\left[\sum_{k=0}^{n+1}2^{n+1-k}\binom{n+1+k}{n+1}-2\binom{2n+1}{n+1}-\binom{2n+2}{n+1}\right] \\ &= 2\cdot4^n + \frac{1}{2}S_{n+1} \\ \Rightarrow S_{n+1}&=4^{n+1} \end{aligned} \]

结合数学归纳法，得证。

引理 2： \[ \sum_{p=m}^{2m}p2^{-p}\binom{p}{m} = (2m+1)-\frac{m+1}{2^{2m+1}}\binom{2m+2}{m+1} \] 证明：源于这个帖子。 \[ \begin{aligned} \sum_{p=m}^{2m}p2^{-p}\binom{p}{m} &= \sum_{p=m}^{2m}(p+1)2^{-p}\binom{p}{m} -\sum_{p=m}^{2m}2^{-p}\binom{p}{m} \\ &= \sum_{p=m}^{2m}(m+1)2^{-p}\binom{p+1}{m+1} - 1\\ &= (m+1) \left[2\sum_{p+1=m+1}^{2m+2}2^{-(p+1)}\binom{p+1}{m+1}-2^{-2m-1}\binom{2m+2}{m+1}\right] - 1 \\ &= (m+1)\left[2-\frac{1}{2^{2m+1}}\binom{2m+2}{m+1}\right] - 1\\ &= (2m+1)-\frac{m+1}{2^{2m+1}}\binom{2m+2}{m+1} \end{aligned} \] 得证。

原式证明：结合引理 1 和 2，令 \(m=n-1,p=2n-k-1\)： \[ \begin{aligned} \sum_{k=1}^nk2^k\binom{2n-k-1}{n-1}&=\sum_{p=m}^{2m}(2m+1-p)2^{2m+1-p}\binom{p}{m} \\ &=2^{2m+1}\sum_{p=m}^{2m}(2m+1-p)2^{-p}\binom{p}{m} \\ &= 2^{2m+1}\left[(2m+1)-(2m+1)+\frac{m+1}{2^{2m+1}}\binom{2m+2}{m+1}\right] \\ &= (m+1)\binom{2m+2}{m+1}\\ &= n\binom{2n}{n} \end{aligned} \] 整个证明神乎其技，学不来学不来，感觉自己实在是太菜了。

生成函数证明

帖子里有，看起来非常短，我对于生成函数还不熟练，积极学习中～TODO: 看懂了整理上来。

组合证明

帖子里有，看起来非常不短，似乎用了很多 non-trivial 的论证方法，试图理解中～TODO: 看懂了整理上来。

超几何证明

这个证明是我在翻《基础数学》看到超几何函数那一节的时候想的，是这四个证明中唯一一个我原创的证明（悲）。用到了超几何函数，蒟蒻高中生感觉非常炫酷.jpg

首先把等式左边改成无限求和： \[ \begin{aligned} \sum_{k=1}^{n}k2^k\binom{2n-d-1}{n-1} &= \sum_{k=1}^{n}k2^k\binom{2n-k-1}{n-k} \\ &= \sum_{k=1}^{\infty}k2^k\binom{2n-k-1}{n-k} \\ &= \sum_{k=0}^{\infty}(k+1)2^{k+1}\binom{2n-k-2}{n-k-1} \end{aligned} \] 若令 \(t_k=(k+1)2^{k+1}\binom{2n-k-2}{n-k-1}\)，则观察到： \[ \begin{aligned} \frac{t_{k+1}}{t_k} &= \frac{(k+2)2^{k+2}\binom{2n-k-3}{n-k-2}}{(k+1)2^{k+1}\binom{2n-k-2}{n-k-1}} \\ &= \frac{2(k+2)[k+(1-n)]}{(k+1)[k+(2-2n)]} \\ \end{aligned} \] 是一个关于 \(k\) 的有理式，因此引入高斯超几何函数： \[ \begin{aligned} \mathrm{LHS} &=t_0\cdot {}_2F_1(2,1-n;2-2n;2)\\ &=2\binom{2n-2}{n-1} {}_2F_1(2,1-n;2-2n;2) \end{aligned} \] 考虑化简超几何项，利用如下 Kummer 二次变换（他 1836 年论文的 Eq.54）： \[ {}_2F_1(a,b;2b;z)=\frac{1}{(1-z)^{a/2}}{}_2F_1\left(\frac{1}{2}a,b-\frac{1}{2}a;b+\frac{1}{2};\frac{z^2}{4z-4}\right) \] 则得到： \[ {}_2F_1(2,1-n;2-2n;2)=-{}_2F_1(1,-n;\frac{3}{2}-n;1) \] 因为都是实参数且 \(1-n<\frac{3}{2}-n\)，因此运用高斯定理： \[ \begin{aligned} {}_2F_1(1,-n;\frac{3}{2}-n;1) &= \frac{\Gamma\left(\frac{3}{2}-n\right)\Gamma\left(\frac{1}{2}\right)}{\Gamma\left(\frac{1}{2}-n\right)\Gamma\left(\frac{3}{2}\right)} \\ &= 2\left(\frac{1}{2}-n\right) \\ &= 1-2n \end{aligned} \] 一路代回去： \[ \begin{aligned} \mathrm{LHS} &= 2\binom{2n-2}{n-1} {}_2F_1(2,1-n;2-2n;2) \\ &= 2(2n-1)\binom{2n-2}{n-1} \\ &= 2n\binom{2n-1}{n-1} \\ &= n\binom{2n}{n} = \mathrm{RHS} \end{aligned} \] 证毕。

整个证明过程颇有一种高射炮打蚊子的既视感。超几何函数各种公式一大堆还千奇百怪，套就完事了，然而无论是 Kummer 的二次变换还是高斯定理我都不知道怎么证（悲）。 我已经把 Ahlfors 的 Complex Analysis 存起来了，决定有空看看（不知道会不会有这方面的内容）。

嘛，在初等证明存在的情况下，用这种严重超纲的做法只能给人一种装逼的错觉虽然我感觉有点开心？，别人看你搞不好都跟关爱智障一样。MSE 上果然大佬太多，向大佬低头.jpg。