The Method of Snake Oil
进行组合求和的蛇油法。
- 确定求和所依赖的自由变量，例如 \(n\)。为您正在处理的求和命名；称之为 \(f_n\)。
- 让 \(F(x)\) 成为 \(f(n)\) 的生成函数，即您想要求和的和。
- 将和乘以 \(x^n\)，然后对 \(n\) 求和。您的生成函数现在表示为对 \(n\) 的双重求和，以及对任何首先用作虚拟求和变量的变量的双重求和。
- 交换您现在正在查看的两个求和的顺序，并以简单的闭式执行内部求和。为此，拥有一个已知和的系列目录会很有帮助。
- 尝试识别答案的生成函数的系数，因为这些系数就是你想要找到的。
以上来自谷歌翻译。
具体来说就是一个组合数求和的一种套路方法。
基本的
需要记住。
\[\begin{aligned} \sum_{n}\binom{m}{n}x^n&=(1+x)^m\\ \sum_{n}\binom{n}{m}x^n&=\frac{x^m}{(1-x)^{m+1}}\\ \sum_{n}\binom{n+m}{m}x^n&=\frac{1}{(1-x)^{m+1}}\\ \sum_{n}\binom{2n}{n}\frac{1}{1+n}x^n&=\frac{1}{2x}(1-\sqrt{1-4x})&(卡特兰数) \end{aligned}\]例一
给定 \(n\)，求：
\[\begin{aligned} \sum_{k\le 0}\binom{k}{n-k} \end{aligned}\]\[\begin{aligned} F(x)&=\sum_{n}x^n\sum_{k\le 0}\binom{k}{n-k}\\ &=\sum_{k\le 0}\sum_{n}x^n\binom{k}{n-k}\\ &=\sum_{k\le 0}x^{k}\sum_{n}x^{n-k}\binom{k}{n-k}\\ &=\sum_{k\le 0}x^{k}\sum_{r}x^{r}\binom{k}{r}\\ &=\sum_{k\le 0}x^{k}(1+x)^k\\ &=\sum_{k\le 0}(x+x^2)^k\\ &=\frac{1}{1-x-x^2}\\ \end{aligned}\]例二
给定 \(n,m\)，求：
\[\begin{aligned} \sum_{k}\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1} \end{aligned}\]\[\begin{aligned} F(x)&=\sum_{n}x^n\sum_{k}\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}\\ &=\sum_{k}\sum_{n}x^n\binom{n+k}{m+2k}\binom{2k}{k}\frac{(-1)^k}{k+1}\\ &=\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}\sum_{n}x^n\binom{n+k}{m+2k}\\ &=\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}x^{-k}\sum_{n}x^{n+k}\binom{n+k}{m+2k}\\ &=\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}x^{-k}\sum_{r}x^{r}\binom{r}{m+2k}\\ &=\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}x^{-k}\frac{x^{m+2k}}{(1-x)^{m+2k+1}}\\ &=\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}\frac{x^{m+k}}{(1-x)^{m+2k+1}}\\ &=\frac{x^{m}}{(1-x)^{m+1}}\sum_{k}\binom{2k}{k}\frac{(-1)^k}{k+1}\frac{x^{k}}{(1-x)^{2k}}\\ &=\frac{x^{m}}{(1-x)^{m+1}}\sum_{k}\binom{2k}{k}\frac{1}{k+1}(\frac{-x}{x^2-2x+1})^k\\ &=\frac{x^{m}}{(1-x)^{m+1}}\frac{x^2-2x+1}{-2x}(1-\sqrt{1-4\frac{-x}{x^2-2x+1}})\\ &=\frac{x^{m-1}}{-2(1-x)^{m-1}}(1-\sqrt{1-4\frac{-x}{x^2-2x+1}})\\ &=\frac{x^{m-1}}{-2(1-x)^{m-1}}(1-\frac{1+x}{1-x})\\ &=\frac{x^m}{(1-x)^m}\\ \end{aligned}\]其中：
\[\frac{x^m}{(1-x)^m}[x^n]=\binom{n-1}{m-1} \]例三
给定 \(y\)，求：
\[f_n=\sum_{k\le \frac{n}{2}}(-1)^k\binom{n-k}{k}y^{n-2k} \]的更简单的封闭形式。
\[\begin{aligned} F(x)&=\sum_{n}x^n\sum_{k\le \frac{n}{2}}(-1)^k\binom{n-k}{k}y^{n-2k}\\ &=\sum_{k}\sum_{n\ge 2k}x^n(-1)^k\binom{n-k}{k}y^{n-2k}\\ &=\sum_{k}(-1)^ky^{-k}x^{k}\sum_{n\ge 2k}(xy)^{n-k}\binom{n-k}{k}\\ &=\sum_{k}(-1)^ky^{-k}x^{k}\sum_{r}(xy)^{r}\binom{r}{k}\\ &=\sum_{k}(-1)^ky^{-k}x^{k}\frac{(xy)^k}{(1-(xy)^{k+1})}\\ &=\frac{1}{1-xy}\sum_{k}(\frac{-x^2}{1-xy})^k\\ &=\frac{1}{1-xy}\frac{1}{1+\frac{x^2}{1-xy}}\\ &=\frac{1}{1-xy+x^2}\\ \end{aligned}\]例四
给定 \(n\)，求：
\[\sum_{k}\binom{n+k}{2k}2^{n-k} \]\[\begin{aligned} F(x)&=\sum_{n}x^n\sum_{k}\binom{n+k}{2k}2^{n-k}\\ &=\sum_{k}\sum_{n}x^n\binom{n+k}{2k}2^{n-k}\\ &=\sum_{k}2^{-2k}x^{-k}\sum_{n}(2x)^{n+k}\binom{n+k}{2k}\\ &=\sum_{k}(4x)^{-k}\sum_{r}(2x)^{r}\binom{r}{2k}\\ &=\sum_{k}(4x)^{-k}\frac{(2x)^{2k}}{(1-2x)^{2k+1}}\\ &=\sum_{k}\frac{x^k}{(1-2x)^{2k+1}}\\ &=\frac{1}{1-2x}\sum_{k}(\frac{x}{(1-2x)^2})^k\\ &=\frac{1}{1-2x}\frac{1}{1-\frac{x}{(1-2x)^2}}\\ &=\frac{1-2x}{4x^2-5x+1}\\ \end{aligned}\]所以有递推式：
\[\begin{aligned} f_0&=1\\ f_1&=3\\ f_n&=5f_{n-1}-4f_{n-2}\\ \end{aligned}\]使用范围
Snake Oil 方法的成功取决于给出一个要计算的和，其中有一个自由变量只出现在一个地方。
然后，在交换求和的顺序后，人们会找到一个基本幂级数来求和。
尽管通过添加花招可能会在一定程度上降低该方法的魅力，但必须指出，在许多重要情况下，这种范围限制很容易克服。
这是因为经常发生这样的情况：
当呈现一个具有重复多次的自由变量的身份时，该身份变成了更一般身份的一个特例，其中自由变量的每次重复出现都被不同的自由变量所取代。
在放弃对某个给定问题的方法之前，应该探索这种可能性。
这可以通过 Snake Oil 方法轻松评估。
身份主题的特点是，证明特殊情况通常比证明一般定理更难。
自由变量的多次出现通常暗示人们应该尝试寻找合适的概括。
以上来自谷歌翻译。
具体来说，当自由变量多次出现的时候，我们可以使用更多的变量代替自由变量的出现，也就是用更加一般的情况代替特殊情况。
标签：那天,frac,求和,sum,2x,名字,binom,aligned,2k From： https://www.cnblogs.com/JiaY19/p/18252936