有限差分与高阶等差数列

连续作差把多项式数列降次。它既能求通项，也能把多项式求和变成有限的组合数运算，不需要使用无穷级数或微积分。

定义、阶数与零差分

定义向前差分 $\Delta a_n=a_{n+1}-a_n$ ，递归定义 $\Delta^{r+1}a_n=\Delta^ra_{n+1}-\Delta^ra_n$ ，并令 $\Delta^0a_n=a_n$ 。

若 $\Delta^pa_n$ 对所有 $n\ge1$ 等于同一个非零常数，称为恰好 $p$ 阶等差数列。若只知道 $\Delta^{p+1}a_n=0$ ，则阶数至多为 $p$ ，可能退化为低阶或常数数列。零数列单独视作所有差分为零的退化情形。

例如 $a_n=n^2$ 的一阶差为 $2n+1$ ，二阶差为 $2$ ，三阶差为 $0$ 。这里的“高阶”指重复作差，与高等数学中的导数不是同一操作。

差分的二项式表达

对非负整数 $r$ ，有

\Delta^ra_n=\sum_{j=0}^r(-1)^{r-j}\binom rj a_{n+j}.

$r=0$ 时显然成立。归纳时把右式在 $n+1$ 与 $n$ 的值相减，同下标项的系数用帕斯卡恒等式合并，即得到 $r+1$ 的形式。

因此二阶差为 $a_{n+2}-2a_{n+1}+a_n$ ，三阶差为 $a_{n+3}-3a_{n+2}+3a_{n+1}-a_n$ 。注意符号和下标方向；换成向后差分时公式须相应改变。

多项式通项与牛顿有限展开

若 $a_n=P(n)$ 且 $P$ 恰为 $p$ 次多项式、首项系数为 $c\ne0$ ，二项式展开给 $P(n+1)-P(n)$ 的最高项为 $pcn^{p-1}$ 。反复作差得 $\Delta^pa_n=p!c$ ，下一阶为零。

反之，若所有 $n\ge1$ 都满足 $\Delta^{p+1}a_n=0$ ，则

a_n=\sum_{j=0}^{p}\binom{n-1}{j}\Delta^ja_1.

约定当整数 $n-1<j$ 时组合数为零；作为多项式， $\binom{n-1}{j}=(n-1)(n-2)\cdots(n-j)/j!$ 。帕斯卡恒等式说明它的一阶差为 $\binom{n-1}{j-1}$ 。因此右侧多项式的各阶初始差与左侧一致，且同样满足第 $p+1$ 阶差为零。这个条件是确定后继项的递推式，前 $p+1$ 个初值相同就逐项相同，证明完毕。

求和与完整算例

利用 $\sum_{k=1}^n\binom{k-1}{j}=\binom n{j+1}$ ，有

S_n=\sum_{j=0}^{p}\binom n{j+1}\Delta^ja_1.

组合恒等式可由帕斯卡关系裂项相消证明。若最高阶差非零， $S_n$ 恰为 $p+1$ 次多项式。

设数列前四项为 $2,5,12,23$ ，并已知二阶差恒为 $4$ 。一阶差从 $3,7,11$ 开始，故

a_n=2+3\binom{n-1}1+4\binom{n-1}2=2n^2-3n+3,

S_n=2n+3\binom n2+4\binom n3.

例如 $S_4=8+18+16=42$ ，与四项直接相加一致。

有限样本不能确定无限规律

从几个已知数算出差分表，只能提示一种候选规律。若 $P(n)$ 匹配前 $m$ 项，则对任意常数 $c$ ，

Q(n)=P(n)+c\prod_{j=1}^m(n-j)

也匹配前 $m$ 项，后续却可能不同。使用高阶等差通项前，必须有“全体下标上差分恒定”的条件或证明，不能仅由前几项相同推出。

任意有限数表的重建

对任意数列 $a_0,a_1,\ldots$ ，定义 $\Delta a_n=a_{n+1}-a_n$ 。不要求数列来自多项式，对每个非负整数 $n$ 都有

a_n=\sum_{j=0}^n\binom nj\Delta^ja_0.

将 $\Delta^ja_0=\sum_{i=0}^j(-1)^{j-i}\binom ji a_i$ 代入， $a_i$ 的系数为

\sum_{j=i}^n(-1)^{j-i}\binom nj\binom ji =\binom ni\sum_{r=0}^{n-i}(-1)^r\binom{n-i}{r}.

由二项式定理， $i<n$ 时为零， $i=n$ 时为一。因而差分表与原始有限数表携带相同信息。若高阶差分恒为零，重建式才进一步缩短成固定项数的多项式形式。

差分乘积法则

对任意两数列，直接添减 $a_{n+1}b_n$ 得

\Delta(a_nb_n)=a_{n+1}\Delta b_n+b_n\Delta a_n.

一般地，对非负整数 $m$ ，

\Delta^m(a_nb_n)=\sum_{j=0}^m\binom mj(\Delta^ja_n)(\Delta^{m-j}b_{n+j}).

证明对 $m$ 归纳。对求和中的每个乘积使用 $\Delta(uv)=(\Delta u)v_{n+1}+u\Delta v$ ，再将第一组的下标移一位；相邻系数按帕斯卡公式相加，恰得到 $m+1$ 的式子。

与导数乘积公式相比，差分公式中的平移 $n+j$ 不能删去。取 $a_n=b_n=n$ ，一阶差分为 $2n+1$ ，不是 $2n$ 。