蛇油（Snake oil）方法学习笔记

Part 1 简介

Snake Oil 方法是一种用于推导组合恒等式的方法，该方法的大体思路为：

1. 对于某个组合求和式，设其参数为 $n$，结果为 $a_n$；
2. 写出 $a_n$ 的 OGF $f(x)$；
3. 根据组合求和式展开 $f(x)$，交换求和顺序，根据已有结论推导；
4. 求出 $f(x)$ 较简单形式后展开成序列；

需要注意的是，一般使用 Snake Oil 方法推导的组合恒等式中求和都是没有上下界的，并且默认当 $n<0$ 或 $m<0$ 或 $n<m$ 时 $\binom{n}{m}=0$。

Part 2 经典结论

2.1 公理

2.1.1 行求和

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

2.1.2 列求和

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

2.1.3 卡特兰

$\sum\limits_{k}\binom{2k}{k}x^k=\frac{1}{\sqrt{1-4x}}\qquad(2.1.3.1)$

$\sum\limits_{k}\frac{1}{k+1}\binom{2k}{k}x^k=\frac{1-\sqrt{1-4x}}{2x}\qquad(2.1.3.2)$

Part 3 经典样例

3.1 例 1：左斜求和

$a_n=\sum\limits_{k}\binom{k}{n-k}\qquad(n\ge 0)$

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

不难发现这其实是斐波那契的封闭形式，故 $\sum\limits_{k}\binom{k}{n-k}=fib_n$。

3.2 例 2

$a_{n,m}=\sum\limits_{k}\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}\qquad(n,m\ge 0)$

把 $m$ 看作常数，则：

$\begin{aligned} f(x)&=\sum\limits_{n}x^n\sum\limits_{k}\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}\\ &=\sum\limits_{k}(-1)^k\frac{\binom{2k}{k}}{k+1}\sum\limits_{n}x^n\binom{n+k}{m+2k}\\ &=\sum\limits_{k}(-1)^k\frac{\binom{2k}{k}}{k+1}x^{-k}\sum\limits_{n}x^{n+k}\binom{n+k}{m+2k}\\ &=\sum\limits_{k}(-1)^k\frac{\binom{2k}{k}}{k+1}x^{-k}\frac{x^{m+2k}}{(1-x)^{m+2k+1}}\qquad\text{套用 2.1.2}\\ &=\sum\limits_{k}(-1)^k\frac{\binom{2k}{k}}{k+1}\frac{x^{m+k}}{(1-x)^{m+2k+1}}\\ &=\frac{x^m}{(1-x)^{m+1}}\sum\limits_{k}(-1)^k\frac{\binom{2k}{k}}{k+1}\frac{x^k}{(1-x)^{2k}}\\ &=\frac{x^m}{(1-x)^{m+1}}\sum\limits_{k}\frac{\binom{2k}{k}}{k+1}\left(\frac{-x}{(1-x)^2}\right)^k\\ &=\frac{x^m}{(1-x)^{m+1}}\frac{1-\sqrt{1-\frac{-4x}{(1-x)^2}}}{\frac{-2x}{(1-x)^2}}\qquad\text{套用 2.1.3.2}\\ &=\frac{x^m(1-x)^2\left(\sqrt{1+\frac{4x}{(1-x)^2}}-1\right)}{2x(1-x)^{m+1}}\\ &=\frac{x^{m-1}\left(\sqrt{\frac{(1-x)^2+4x}{(1-x)^2}}-1\right)}{2(1-x)^{m-1}}\\ &=\frac{x^{m-1}\left(\frac{1+x}{1-x}-1\right)}{2(1-x)^{m-1}}\\ &=\frac{x^{m-1}\frac{2x}{1-x}}{2(1-x)^{m-1}}\\ &=\frac{x^{m}}{(1-x)^m} \end{aligned}$

展开：

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

所以：

$a_{n,m}=\binom{n-1}{m-1}$

3.3 例 3

$a_n=\sum\limits_{k}(-1)^k\binom{n-k}{k}y^{n-2k}\qquad(n\ge 0)$

$\begin{aligned} f(x)&=\sum\limits_{n}x^n\sum\limits_{k}(-1)^k\binom{n-k}{k}y^{n-2k}\\ &=\sum\limits_{k}(-1)^k\sum\limits_{n}x^n\binom{n-k}{k}y^{n-2k}\\ &=\sum\limits_{k}\frac{(-1)^k}{y^{2k}}\sum\limits_{n}\binom{n-k}{k}(xy)^n\\ &=\sum\limits_{k}\frac{(-1)^k}{y^{2k}}\frac{(xy)^{2k}}{(1-xy)^{k+1}}\\ &=\sum\limits_{k}\frac{(-1)^kx^{2k}}{(1-xy)^{k+1}}\\ &=\sum\limits_{k}\frac{1}{1-xy}\left(\frac{-x^2}{1-xy}\right)^k\\ &=\frac{1}{1-xy}\sum\limits_{k}\left(\frac{-x^2}{1-xy}\right)^k\\ \end{aligned}$

注意到 $k$ 是大于等于 $0$ 的，所以：

$\begin{aligned} f(x)&=\frac{1}{1-xy}\frac{1}{1-\frac{-x^2}{1-xy}}\\ &=\frac{1}{1-xy}\frac{1-xy}{1-xy+x^2}\\ &=\frac{1}{1-xy+x^2} \end{aligned}$

使用待定系数法，设：

$\frac{1}{1-xy+x^2}=\frac{1}{(1-ax)(1-bx)}=\frac{a}{(a-b)(1-ax)}-\frac{b}{(a-b)(1-bx)}$

那么有：

$\begin{cases} a+b=y\\ ab=1 \end{cases}$

解得：

$\begin{cases} a=\frac{y+\sqrt{y^2-4}}{2}\\ b=\frac{y-\sqrt{y^2-4}}{2}\\ \end{cases}$

那么有：

$a_n=\frac{1}{\sqrt{y^2-4}}\left(\left(\frac{y+\sqrt{y^2-4}}{2}\right)^{n+1}-\left(\frac{y-\sqrt{y^2-4}}{2}\right)^{n+1}\right)$

3.4 例 4

$a_n=\sum\limits_{k}\binom{n+k}{2k}2^{n-k}\qquad(n\ge 0)$

3.5 例 5

$a_n=\sum\limits_{k}\binom{n}{k}\binom{2k}{k}y^k\qquad (n\ge 0)$

$\begin{aligned} f(x)&=\sum\limits_{n}\sum\limits_{k}\binom{n}{k}\binom{2k}{k}y^kx^n\\ &=\sum\limits_{k}\binom{2k}{k}y^k\sum\limits_{n}\binom{n}{k}x^n\\ &=\sum\limits_{k}\binom{2k}{k}y^k\frac{x^k}{(1-x)^{k+1}}\qquad\text{套用 2.1.2}\\ &=\frac{1}{1-x}\sum\limits_{k}\binom{2k}{k}\left(\frac{xy}{1-x}\right)^k\\ &=\frac{1}{1-x}\frac{1}{\sqrt{1-\frac{4xy}{1-x}}}\qquad\text{套用 2.1.3.1}\\ &=\frac{1}{1-x}\frac{1-x}{\sqrt{1-x-4xy}}\\ &=\frac{1}{\sqrt{(1-x)(1-x-4xy)}}\\ &=\frac{1}{\sqrt{1-x-4xy-x+x^2+4x^2y}}\\ &=\frac{1}{\sqrt{1-(4y+2)x+(4y+1)x^2}}\\ \end{aligned}$

这个式子有一个有趣的拓展：

带入 $y=-\frac{1}{2}$ 得：

$\sum\limits_{k}\binom{n}{k}\binom{2k}{k}\left(-\frac{1}{2}\right)^k=[x^n]\frac{1}{\sqrt{1-x^2}}=[x^n]\sum\limits_{k}\binom{2k}{k}\left(\frac{x}{2}\right)^{2k}\qquad (n\ge 0)$

那么：

$\sum\limits_{k}\binom{n}{k}\binom{2k}{k}\left(-\frac{1}{2}\right)^k=\begin{cases}\binom{n}{\frac{n}{2}}&n\text{ mod }2=0\\0&n\text{ mod }2=1\end{cases}\qquad (n\ge 0)$

3.6 例 6：下降幂和

$a_{n,m}=\sum\limits_{i=m}^ni^{\underline m}\qquad(n\ge m\ge 0)$

$\begin{aligned}F_{m}(x)&=\sum\limits_{n=m}^\infin \sum\limits_{i=m}^{n}\frac{i!}{(i-m)!}x^n\\ &=\sum\limits_{i=m}^{\infin}\frac{i!}{(i-m)!}\sum\limits_{n=i}^\infin x^n\\ &=\sum\limits_{i=m}^{\infin}\frac{i!}{(i-m)!}\frac{x^i}{1-x}\\ &=\left(\sum\limits_{i=m}^{\infin}\frac{i!}{(i-m)!}x^i\right)\frac{1}{1-x}\\&=m!\left(\sum\limits_{i=m}^{\infin}\frac{i!}{(i-m)!m!}x^i\right)\frac{1}{1-x}\\ &=m!\left(\sum\limits_{i=m}^{\infin}\binom{i}{m}x^i\right)\frac{1}{1-x}\\ &=m!\frac{x^m}{(1-x)^{m+1}}\frac{1}{1-x}\\ &=m!\frac{x^m}{(1-x)^{m+2}}\\ \end{aligned}$

所以：

$a_{n,m}=\frac{(n+1)!}{(m+1)(n-m)!}$