从《具体数学》第五章 二项式系数中选了一些个人认为比较 useful 的内容，添加了部分解释和证明。
组合数
在 \(n\) 个元素中选择 \(m\) 个的方案数，记作 \(\dbinom{n}{m}\)，定义为：
\[\dbinom{n}{m}=\dfrac{n!}{m!}{(n-m)!} \]其中 \(n,m\) 为非负整数。
当 \(m\) 为非负整数时，可以拓展定义：
\[\dbinom{n}{m}=\dfrac{n^{\underline{m}}}{m!} \]其中 \(n\) 为任意实数甚至复数。
事实上甚至可以拓展到 \(m\) 为复数：
\[\dfrac{1}{z!}=\lim\limits_{n \rightarrow \infty} \dfrac{n+z}{n} n^{-z} \]当 \(z\) 为负整数时 \(\dfrac{1}{z!}=0\)，故认为 \(m\) 为负整数时 \(\dbinom{n}{m}=0\)。
基本恒等式
下面基本只讨论 \(m\) 为整数的情况。
对称恒等式：\(\dbinom{n}{m}=\dbinom{n}{n-m}\)，其中 \(n \geq 0\)。
吸收/释放恒等式：\(\dfrac{n}{m}=\dfrac{n}{m} \dbinom{n-1}{m-1}\)。
加法公式：\(\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}\)。
平行求和：\(\sum\limits_{k=0}^{m} \dbinom{n+k}{k}=\dbinom{n+m+1}{n}\)，\(n\) 为非负整数。
上指标求和：\(\sum\limits_{k=0}^n \dbinom{k}{m}=\dbinom{n+1}{m+1}\)，\(n\) 为非负整数。
这个式子两边乘上 \(m\) 就可以得到有限积分的结果。
二项式定理：\((1+x)^r=\sum\limits_{k \geq 0} \dbinom{n}{k} x^k y^{n-k}\)，当 \(n\) 不为非负整数时需要 \(|x| \leq 1\) 来保证收敛。
上指标反转：\(\dbinom{n}{m}=(-1)^m \dbinom{n-m-1}{m}\)。
范德蒙德卷积：\(\sum\limits_{k=0}^n \dbinom{a}{k} \dbinom{b}{n-k}=\dbinom{a+b}{n}\)，\(n\) 为非负整数。
组合证明：左边 \(a\) 个球，右边 \(b\) 个球，一共选 \(n\) 个球，相当于枚举左边选 \(i\) 个球，右边选 \(n-i\) 个球。
代数证明：
\[\begin{aligned} LHS &= \sum\limits_{i=0}^n ([x^i] (1+x)^a) ([x^{n-i}] (1+x)^b)\\ &= [x^n](1+x)^{a+b}\\ &= \dbinom{a+b}{n} \end{aligned} \]反范德蒙德卷积：\(\sum\limits_{k=0}^n \dbinom{k}{a} \dbinom{n-k}{b}=\dbinom{n+1}{a+b+1}\)，\(n\) 为非负整数。
组合证明：共 \(n+1\) 个球排成一列，选出 \(a+b+1\) 个球，相当于枚举第 \(a+1\) 个球在 \(i+1\) 处。
代数证明：
\[\begin{aligned} LHS &= \sum\limits_{i=0}^n ([x^i] \dbinom{x^a}{(1-x)^{a+1}}) ([x^{n-i}] \dbinom{x^b}{(1-x)^{b+1}})\\ &= [x^n] \dbinom{x^{a+b}}{(1-x)^{a+b+2}}\\ &= \dbinom{n+1}{a+b+1} \end{aligned} \]一半组合数
下降幂加倍公式：
\[x^{\underline k}(x-\dfrac{1}{2})^{\underline k}=\dfrac{(2x)^{\underline {2k}}}{2^{2k}}(x \geq k) \]\[\dbinom{x-1/2}{k}=\dfrac{1}{k!} (x-1/2)^{\underline k}=\dfrac{(2x)^{\underline {2k}}}{k! x^{\underline k} 2^{2k}}=4^{-k} \dbinom{2x}{2k}\dbinom{2k}{k} \Big/ \dbinom{x}{k} \]Example 1
当 \(x=k=n\) 时有 \(\dbinom{n-1/2}{n}=4^{-n} \dbinom{2n}{n}\)。
用上指标反转可推出 \(\dbinom{-1/2}{n}=(-4)^{-n} \dbinom{2n}{n}\)，故有：
\[\sum \dbinom{2i}{i} x^i=(1-4x)^{-1/2} \]还可以算 \(\dbinom{1/2}{k}=\dfrac{1/2}{k} \dbinom{-1/2}{k-1}=\dfrac{1}{2k} (-4)^{k-1} \dbinom{2(k-1)}{k-1}\)，于是：
\[C(x)=\dfrac{1-(1-4x)^{1/2}}{2x}=\sum\limits_i [\dbinom{2i}{i} \Big/ (i+1)] x^i \]即卡特兰数的生成函数。
Example 2
在
\(\dbinom{x-1/2}{k} \dbinom{x}{k}=4^{-k} \dbinom{2x}{2k}\dbinom{2k}{k}\)
中令 \(x=n/2\) 得到：
\[\dbinom{(n-1)/2}{k} \dbinom{n/2}{k}=4^{-k} \dbinom{n}{2k}\dbinom{2k}{k} \]\[\sum\limits_{k} 4^{-k}\dbinom{n}{2k}\dbinom{2k}{k}=\sum\limits_{k} \dbinom{(n-1)/2}{k} \dbinom{n/2}{k} \]然后 \((n-1)/2\) 与 \(n/2\) 中至少有一个是非负整数。以 \(n/2\) 为非负整数为例：
\[\sum\limits_{k} \dbinom{(n-1)/2}{k} \dbinom{n/2}{k}=\sum\limits_{k} \dbinom{(n-1)/2}{k} \dbinom{n/2}{n/2-k}=\dbinom{n-1/2}{n/2} \]最后将两种情况合起来可以得到：
\[\sum\limits_{k} 4^{-k}\dbinom{n}{2k}\dbinom{2k}{k}=\dbinom{n-1/2}{\lfloor n/2 \rfloor} \]Example 3
还可以得到一些别的东西。已经得到：
\[\dbinom{-1/2}{n}=(-4)^{-n} \dbinom{2n}{n} \]对其求和有：
\[\sum\limits_k \dbinom{-1/2}{k} \dbinom{-1/2}{n-k}=\sum\limits_k (-4)^{-k} \dbinom{2k}{k} (-4)^{-(n-k)} \dbinom{2(n-k)}{n-k}=(-4)^{-n} \sum\limits_k \dbinom{2k}{k} \dbinom{2(n-k)}{n-k} \]而左式用范德蒙德卷积就是 \(\dbinom{-1}{n}=(-1)^n\)。于是：
\[\sum\limits_k \dbinom{2k}{k} \dbinom{2(n-k)}{n-k}=4^n \]差分和牛顿级数
这里涉及到有限微积分。考虑函数将序列放在值上的函数 \(f(x)\)，关心其在整数上的取值。
定义平移算子 \(E f(x)=f(x+1)\)，差分算子 \(\Delta f(x)=f(x+1)-f(x)\)，那么有 \(\Delta=E-1\)，及：
\[\Delta^n=\sum\limits_k \dbinom{n}{k} (-1)^{n-k} E^k \]\[\Delta^n f(x)=\sum\limits_k \dbinom{n}{k} (-1)^{n-k} f(x+k) \]Example
有限微积分中有结果 \(\Delta x^{\underline{k}}=k x^{\underline{k-1}}\)。
令 \(f(x)=(x-1)^{-1}=\dfrac{1}{x}\)，则：
\[\Delta^n f(x)=(-1)(-2) \cdots (-n) (x-1)^{-n-1}=(-1)^n \dfrac{n!}{x(x+1)\cdots (x+n)}=(-1)^n x^{-1} \dbinom{x+n}{n}^{-1} \]于是：
\[\sum\limits_k \dbinom{n}{k} \dfrac{(-1)^k}{x+k}=x^{-1} \dbinom{x+n}{n}^{-1} \]于是获得了右式的部分分式展开，不过其实直接设元解也能快速得到。
牛顿级数
考虑 \(n\) 次多项式 \(f(x)=\sum\limits_{k=0}^n a_k x^k\)。将其转为下降幂多项式后再给 \(x^k\) 系数乘上 \(k!\)，可以得到：
\[f(x)=\sum\limits_{k=0}^n c_k \dbinom{x}{k} \]所以任意多项式都可以唯一地表示成牛顿级数形式。
由于 \(\Delta \dbinom{x}{k}=\dbinom{x+1}{k}-\dbinom{x}{k}=\dbinom{x}{k-1}\)，故牛顿级数的导数很简单：
\[\Delta^m f(x)=\sum\limits_{k=0}^n c_k \dbinom{x}{k-m} \]令 \(x=0\)，则 \(\Delta^m f(0)=c_m\)。
Example 1
代入得：
\[f(x)=\sum\limits_{k=0}^n \Delta^k f(0) \dbinom{x}{k} \]于是若知道 \(f(0),f(1),\cdots,f(n)\) 就可以 \(O(n^2)\) 得到 \(f(n)\) 的牛顿级数形式，这即牛顿插值。
该式进一步还可以写成：
\[f(a+x)=\sum\limits_{k \geq 0} \dfrac{\Delta^k f(a)}{k!} x^{\underline{k}} \]可以看作有限微积分中的泰勒展开。
Example 2
还有另一个结果。将其代入 \(\Delta^n f(x)=\sum\limits_k \dbinom{n}{k} (-1)^{n-k} f(x+k)\) 可得：
\[\sum\limits_k (-1)^k \dbinom{n}{k} f(k)=(-1)^n c_n \]再把 \(f(n)\) 写回一般多项式 \(\sum\limits_k a_k\)，那么有 \(a_n=n! c_n\)，故：
\[\sum\limits_k (-1)^k \dbinom{n}{k} f(k)=(-1)^n n! a_n \]不过这个结果并不特别，其实就是下降幂多项式插求值的其中一个式子而已。
这给出一个启示：如果和式中出现 \((-1)^k \dbinom{n}{k}\) 并且剩下的是一个 \(n\) 次多项式，就可以直接化简。
广义二项级数与 Raney 引理
组合角度
该部分内容来自 7.5 卷积。
考虑这样一个问题：
求有多少个长为 \(2n\) 的序列 \(a_1,\cdots,a_{2n} \in \{-1,1\}\) 满足 \(\sum a_i=0\)，使得所有前缀和非负。
答案显然就是卡特兰数 \(C_n=\dbinom{2n}{n}/(n+1)\)。求法五花八门（比如经典折线翻转双射），这里有一种新的解释：
Raney 引理：若序列 \(a_1,\cdots,a_{n} \in \mathbb{Z}\) 满足 \(\sum a_i=1\)，那么其 \(n\) 个循环移位产生的序列中有且仅有一个满足所有前缀和为正。
证明：设前缀和为 \(s_k\)，设 \(x\) 为满足 \(s_k=\min\limits_t s_t\) 的最大的 \(k\)，则显然以 \(x\) 开头的循环移位序列合法。考虑以 \(y(y \neq x)\) 开头的循环移位序列：
- 若 \(y<x\)，则 \(s_y \geq s_x\)，不合法。
- 若 \(y>x\)，则 \(s_y > s_x\)，即 \(s_y \geq s_x+1=s_{x+n}\)，不合法。
那么考虑补上 \(a_0=1\)，限制就变成每个前缀和为正。由 Raney 引理就有：
\[C_n=\dfrac{1}{2n+1} \dbinom{2n+1}{n}=\dfrac{1}{n+1} \dbinom{2n}{n} \]此外，考虑最后一个 \(s_x=1\) 且 \(x<2n\) 的 \(x\)，那么 \([0,x]\) 与 \([x+1,n-1]\) 均为合法序列，故卡特兰数的生成函数满足：
\[C(x)=xC^2(x)+1 \]事实上这个东西可以拓展，比如考虑：
求有多少个长为 \(mn\) 的序列 \(a_1,\cdots,a_{nm} \in \{1-m,1\}\) 满足 \(\sum a_i=0\)，使得所有前缀和非负。
可以算出共 \(n\) 个 \((1-m)\) 和 \(mn-n\) 个 \(1\)。
同样设 \(a_0=1\)，再用 Raney 引理得到：
\[C^{(m)}_n=\dfrac{1}{mn+1} \dbinom{mn+1}{n}=\dfrac{1}{mn-n+1} \dbinom{mn}{n} \]这个数列的名字叫 富斯-卡特兰数。
设 \(b_t\) 为最大的 \(k\) 使得 \(s_k=t\) 且 \(k<mn\)（认为 \(b_0=-1\)），那么 \([b_t+1,b_{t+1}](0 \leq t<m)\) 都是合法序列。于是其生成函数 \(F(x)\) 满足：
\[F(x)=xF^m(x)+1 \]这是一个很厉害的东西，因为直接从这个方程很难得到封闭形式。
下面来考虑 \([x^n]F^d(x)\)。显然没法直接求，但这里有个巧妙的双射，其与下面这个问题的答案是一样的：
求有多少个长为 \(mn\) 的序列 \(a_1,\cdots,a_{nm+d-1} \in \{1-m,1\}\) 满足 \(\sum a_k=d-1(d > 0)\)，使得所有前缀和非负。
还是令 \(a_0=1\)，设 \(b_t\) 为最大的 \(k\) 使得 \(s_k=t\)（认为 \(b_0=-1\)），那么 \([b_t+1,b_{t+1}](0 \leq t<d)\) 都是合法序列。那么就相当于 \(d\) 个合法序列拼在一起了。
但是还是没法求出具体值。考虑 Raney 引理的一个推广：
若序列 \(a_1,\cdots,a_{n} \in (-\infty,1] \bigcap \mathbb{Z}\) 满足 \(\sum a_i=d\)，那么其 \(n\) 个循环移位产生的序列中有且仅有 \(d\) 个满足所有前缀和为正。
证明：设前缀和为 \(s_k\)。设 \(b_t\) 为最大的 \(k\) 使得 \(s_k=t\)（认为 \(b_0=0\)），那么所有 \([b_t+1,b_{t+1}](0 \leq t<d)\) 将整个序列分成 \(d\) 段。每一段里的位置最大的最小值均满足条件；其它位置同理易证不合法。
于是答案为：
\[[x^n]F^d(x)=\dfrac{d}{mn+d} \dbinom{mn+d}{n} \]代数角度
考虑上文中得到的方程：
\[F(x)=xF^m(x)+1 \]设 \(P(x)=F(x)-1\)，有：
\[P(x)=x (P(x)+1)^m \]其复合逆 \(Q(x)\) 满足：
\[x=(1+x)^m Q(x) \]\[Q(x)=x (1+x)^{-m} \]由拓展拉格朗日反演得到：
\[\begin{aligned} [x^n]F^d(x) &= \dfrac{1}{n} [x^{-1}] d(1+x)^{d-1} x^{-n} (1+x)^{mn}\\ &= \dfrac{d}{n} [x^{n-1}] (1+x)^{mn+d-1}\\ &= \dfrac{d}{n} \dbinom{mn+d-1}{n-1}\\ &= \dfrac{d}{mn+d} \dbinom{mn+d}{n}\\ \end{aligned} \]得到了同样的结果：
\[F^d(x)=\sum\limits_{k \geq 0} \dfrac{d}{mk+d} \dbinom{mk+d}{k} x^k \]并且对所有整数 \(m\) 及实数 \(d\) 成立。
该多项式被称为广义二项级数 \(\mathcal{B}_m(x)\)：
\[\mathcal{B}_m(x)=\sum\limits_{k \geq 0} (mk)^{\underline{k-1}} \dfrac{x^k}{k!} \]下面再证另一个恒等式：
\[\dfrac{F^d(x)}{1-m+mF^{-1}(x)}=\sum\limits_{k \geq 0} \dbinom{mk+r}{k} x^k \]考虑对 \(F^d(x)=\sum\limits_{k \geq 0} \dfrac{d}{mk+d} \dbinom{mk+d}{k} x^k\) 求导，有：
\[F^{d-1}(x)F'(x)=\sum\limits_{k \geq 0} \dfrac{k}{mk+d} \dbinom{mk+d}{k} x^k \]于是可以凑出要证的右式：
\[mF^{d-1}(x)F'(x)+F^d(x)=\sum\limits_{k \geq 0} \dbinom{mk+d}{k} x^k \]下面只需要证：
\[\Leftrightarrow (xmF^{-1}(x)F'(x)+1)(1-m+mF^{-1}(x))=1 \]考虑对 \(F(x)=xF^m(x)+1\) 求导，得：
\[F'(x)=F^m(x)+mxF^{m-1}(x)F'(x) \]\[F'(x)=\dfrac{F^m(x)}{1-mxF^{m-1}(x)} \]代入后只要证：
\[\Leftrightarrow \dfrac{1-m+mF^{-1}(x)}{1-mxF^{m-1}(x)}=1 \]\[\Leftrightarrow F^{-1}(x)-1=-xF^{m-1}(x) \]\[\Leftrightarrow F(x)=xF^{m}(x)+1 \]证毕。
将上述两个恒等式乘在一起可以获得一些拓展的恒等式。
例如用第一个恒等式自乘：
\[\dfrac{d+t}{mn+d+t} \dbinom{mn+d+t}{n} x^k= F^{d+t}(x)=\sum\limits_n x^n \sum\limits_{k \leq n} \dfrac{d}{mk+d} \dbinom{mk+d}{k} \dfrac{t}{m(n-k)+t} \dbinom{m(n-k)+t}{n-k} \]\[\sum\limits_{k \leq n} \dfrac{d}{mk+d} \dfrac{t}{m(n-k)+t} \dbinom{mk+d}{k} \dbinom{m(n-k)+t}{n-k}=\dfrac{d+t}{mn+d+t} \dbinom{mn+d+t}{n} \]这是拓展的范德蒙德卷积（\(t=0\) 时退化）。并且还有（不会证）：
\[\sum\limits_{k \leq n} \dbinom{n}{k} \dfrac{d}{mk+d} \dfrac{t}{m(n-k)+t} (mk+d)^k (m(n-k)+t)^{n-k}=\dfrac{d+t}{mn+d+t} (mn+d+t)^n \]这是拓展的二项式定理（\(t=0\) 时退化）。
两个恒等式乘在一起可以得到另一种结果：
\[\sum\limits_{k \leq n} \dfrac{d}{mk+d} \dbinom{mk+d}{k} \dbinom{m(n-k)+t}{n-k}=\dbinom{mn+d+t}{n} \]\[\sum\limits_{k \leq n} \dbinom{n}{k} \dfrac{d}{mk+d} (mk+d)^k (m(n-k)+t)^{n-k}=(mn+d+t)^n \]超几何级数
超几何级数的定义是：
\[F(a_1,\cdots,a_m;b_1,\cdots,b_n;x)=\sum\limits_{k \geq 0} \dfrac{a_1^{\overline{k}} \cdots a_m^{\overline{k}}}{b_1^{\overline{k}} \cdots b_n^{\overline{k}}} \dfrac{x^k}{k!} \]其中 \(b_k\) 均不为 \(0\) 或负整数。
记该级数为 \(t_0,t_1,\cdots\)。
注意到 \(t_0=1\)，且相邻两项比值：
\[\dfrac{t_{k+1}}{t_k}=\dfrac{(k+a_1) \cdots (k+a_m)x}{(k+b_1) \cdots (k+b_n) (k+1)} \]为关于 \(k\) 的有理函数（即两个多项式之商）。
另一方面，任意有理函数都能表示成该形式（因式分解后若分母无 \((k+1)\) 则补一个）。
接下来考虑超几何函数的各种具体形式。
当 \(m=n=0\) 时，就有最简单的：
\[F(;;x)=\sum\limits_{k \geq 0} \dfrac{x^k}{k!}=e^x \]当 \(m=1,n=0\) 时，有：
\[F(a;;x)=\sum\limits_{k \geq 0} a^{\overline{k}} \dfrac{x^k}{k!}=\sum\limits_{k \geq 0} \dbinom{a+k-1}{k} x^k=(1-x)^{-a} \]当 \(m=2,n=1\) 时，\(F(a,b;c;x)\) 被称为高斯超几何级数。
试着改写范德蒙德卷积：
\[\sum\limits_{k \geq 0} \dbinom{a}{k} \dbinom{b}{n-k}=\dbinom{a+b}{n} \]\[t_k=\dfrac{a!}{k!(a-k)!}\dfrac{b!}{(n-k)!(b-n+k)!} \]\[\dfrac{t_{k+1}}{t_k}=\dfrac{(k-a)(k-n)}{(k+1)(k+b-n+1)} \]\[\dbinom{b}{n} F(-a,-n;b-n+1;1)=\dbinom{a+b}{n} \]\[F(-a,-n;b-n+1;1)=\dfrac{(a+b)!(b-n)!}{(a+b-n)!b!} \]\[F(a,b;c;1)=\dfrac{(c-a-b-1)!(c-1)!}{(c-a-1)!(c-b-1)!} \]其中 \(b \in \mathbb{Z}\) 且 \(b \leq 0\)。
还可以写成：
\[F(a,-n;c;1)=\dfrac{(c-a)^{\overline{n}}}{c^{\overline{n}}}=\dfrac{(a-c)^{\underline{n}}}{(-c)^{\underline{n}}} \]还有更多内容，不过我没看懂就不写了
部分超几何和式
考虑这样一个问题：
给出超几何级数 \(f(k)\)，求其有限不定积分 \(\sum f(k) \delta k=g(k)+C\)（即满足 \(f(k)=\Delta g(k)=g(k+1)-g(k)\)）。
可惜的是不是所有这样的 \(g(k)\) 都具有简单形式，例如 \(g(k)+C=\sum \dbinom{n}{k} \delta k\)（通常都是用大家最熟悉的莫队算法做的）。
称超几何级数 \(f(k)\) 是可用超几何项求和的，如果其不定积分可用表示为超几何级数。
Gosper 算法：对于给定超几何级数，求出其超几何级数的不定积分或判定其不可用超几何项求和。
下面来介绍这个算法。设超几何级数 \(t(k)\) 的不定积分为 \(T(k)\)。
第一步是将比值表示成：
\[\dfrac{t(k+1)}{t(k)}=\dfrac{p(k+1)}{p(k)} \dfrac{q(k)}{r(k+1)} \]其中 \(q(k)\) 与 \(r(k)\) 满足：不存在 \(\alpha-\beta \in \mathbb{Z}^+\) 使得 \(q(-\alpha)=r(-\beta)=0\)。
那么先令 \(p(k)=1\)，将比值拆成分子 \(q(k)\) 与分母 \(r(k+1)\)。
接下来如果 \(q(k)\) 和 \(r(k)\) 分别有因子 \((k+\alpha)\) 与 \((k+\beta)\) 满足 \(\alpha-\beta \in \mathbb{Z}^+\)，就将它们从 \(q(k)\) 和 \(r(k)\) 中除掉再令：
\[p(k) \leftarrow p(k)(k+\alpha-1)^{\underline{\alpha-\beta-1}}=p(k) (k+\alpha-1) \cdots (k+\beta+1) \]容易发现仍然满足条件。不断重复即可得到合法的 \(p(k),q(k),r(k)\)。
第二步考虑将 \(T(k)\) 改写成 \(T(k)=\dfrac{r(k)s(k)t(k)}{p(k)}\)，代入有：
\[T(k+1)=\dfrac{r(k+1)s(k+1)t(k+1)}{p(k+1)}=\dfrac{q(k)s(k+1)t(k)}{p(k)} \]\[t(k)=T(k+1)-T(k)=\dfrac{q(k)s(k+1)t(k)}{p(k)}-\dfrac{r(k)s(k)t(k)}{p(k)} \]\[p(k)=q(k)s(k+1)-r(k)s(k) \]现在要求 \(s(k)\)。容易发现 \(s(k)\) 一定是有理函数，但事实上可以证明 \(s(k)\) 一定是多项式。
设 \(s(k)=f(k)/g(k)\)。代入可以得到：
\[p(k)g(k)g(k+1)=q(k)f(k+1)g(k)-r(k)f(k)g(k+1) \]\[r(-x)f(-x)g(-x+1)=q(-x-N)f(-x-N+1)g(-x-N)=0 \]证明：先消去 \(f(k)\) 与 \(g(k)\) 的公因子。设最大的 \(N\) 使存在 \(x\) 满足 \((k+x)\) 与 \((k+x+N-1)\) 均为 \(g(k)\) 因子（注意 \(N=1\) 一定满足）。
将 \(k=-x\) 及 \(k=-x-N\) 代入条件式得：
由于 \(f(k)\) 与 \(g(k)\) 无公因子，故 \(f(-x) \neq 0\)，\(f(-x-N+1) \neq 0\)。由于 \(N\) 的最大性，\(x-1\) 与 \(x+N\) 也不为 \(g(k)\) 的根。
故 \(r(-x)=q(-x-N)=0\)。这与第一步中的限制矛盾。证毕。
有这个结论就好办了。设 \(s(k)=\sum\limits_{t=0}^d \alpha_t k^t\)，代入解方程即可，若方程无解则说明原级数不可用超几何项求和。
最后一个问题：怎么确定 \(s(k)\) 的系数 \(d\)？
考虑 \(p(k)=q(k)s(k+1)-r(k)s(k)\)。令 \(Q(k)=q(k)-r(k)\)，\(R(k)=q(k)+r(k)\)，则有：
\[2p(k)=Q(k)(s(k+1)+s(k))+R(k)((s(k+1)-s(k)) \]这样有关 \(s(k)\) 的多项式次数可控了。
-
如果 \(deg(Q) \geq deg(R)\)，那么右式次数即为 \(d+deg(Q)\)，故 \(d=deg(p)-deg(Q)\) 唯一确定。
-
如果 \(deg(Q) < deg(R)=e\)，这时 \(d\) 可能很大（高位全消掉了）。设 \(Q(k)=A k^{e-1}+\cdots\)，\(R(k)=B k^e+\cdots\)，则右式为 \((2 \alpha_d \cdot A+d \alpha_d \cdot B) k^{d+e-1}+\cdots\)。
于是要么 \(d=deg(p)-deg(Q)+1\)，要么 \(d=-2A/B\)，至多两种情况，分别做即可。
至此整个问题得到解决。
还有一个推广 Gosper-Zeilberger 算法，通过加维在不同的 \(n\) 中尝试寻找递推关系来解决 Gosper 算法求不出来的和式。
我没学过组合数 /kk