「营业日志 2021.1.14」Zeilberger 老爷子的 T 恤上写了啥？
Elegia
·
·
个人记录
这是一张 Wikipedia 上找到的图。其中写的恒等式是这样的：
\sum_k \binom n k^2 \binom {3n+k}{2n} = \binom{3n}n^2
20 世纪 90 年代，组合学家 Wilf 和 Zeilberger 发展了组合恒等式机器证明的算法理论，即 WZ 理论。该理论彻底改变了组合恒等式与特殊函数研究的面貌。计算机科学大师 Knuth 认为该理论将数学中一些重要的部分从艺术转变成科学。在 1996 年，Wilf 和 Zeilberger 也因此项奠基性工作获得美国数学会的 Leroy P. Steel 奖。WZ 理论及其相关应用促进了组合数学与符号计算的交互。许多组合问题，如组合恒等式证明，格路计数问题，组合序列的同余、整除、单峰性质等等，可以借助符号计算的算法与软件得到解决或验证。
——组合恒等式机器证明中的 Wilf-Zeilberger 猜想的解决
不过其实这件 T 恤上的恒等式并不恐怖，让我们来简单推导一下。
\begin{aligned}
&\quad \sum_k \binom n k^2 \binom {3n+k}{2n}\\
&= \sum_k ([x^k](1+x)^n)([x^{n-k}](1+x)^n)[y^{2n}](1+y)^{3n+k}\\
&= [x^ny^{2n}] (1+x)^n((1+y)+x)^n(1+y)^{3n}\\
&= [x^ny^{2n}] (1+x)^n(1+x+y)^n(1+y)^{3n}
\end{aligned}
接下来我们改为枚举第二个括号中的 y，就会得到
\begin{aligned}
&= \sum_k \binom n k\binom {n+k}n \binom{3n}{2n-k}\\
&= \sum_k \binom n k\binom{3n}{2n-k,n,k}\\
&= \sum_k \binom n k\binom {2n}{2n-k} \binom{3n}{n}\\
&= \binom{3n}n^2
\end{aligned}