有限差分的离散微积分

形式陈述

对序列或函数定义平移 $Ef(x)=f(x+1)$ 和前向差分 $\Delta=E-I$ ，即 $\Delta f(x)=f(x+1)-f(x)$ 。重复作用 $k$ 次记为 $\Delta^k$ 。在特征零系数域中，

\Delta^k f(a)=\sum_{j=0}^k(-1)^{k-j}\binom kj f(a+j).

对次数不超过 $d$ 的多项式 $p$ ，Newton 前向展开是有限恒等式

p(x)=\sum_{k=0}^d\Delta^kp(0)\binom{x}{k}, \qquad \binom{x}{k}=\frac{x^{\underline k}}{k!}.

该二项式基满足 $\Delta\binom{x}{k}=\binom{x}{k-1}$ （ $k\ge1$ ），常数的差分为零。因此 $p$ 次数为 $d>0$ 时 $\Delta p$ 恰为 $d-1$ 次，最高系数乘 $d$ 。

若 $f:\mathbb Z\to K$ 是任意序列函数，则它在全部整数上等于某个次数至多 $d$ 的多项式，当且仅当 $\Delta^{d+1}f(m)=0$ 对每个 $m\in\mathbb Z$ 成立。这里只判断整数格上的值，不宣称任意实变量函数由整数样本唯一决定。

直觉

导数比较无限靠近的值；这里固定向前一步，比较的是精确差值。对普通幂， $(x+1)^d-x^d$ 有许多低阶项；对阶乘多项式，减法恰把整组因子降一阶。因此离散积分选择阶乘基，正如普通积分选择幂基。

由 $E$ 与 $I$ 交换，二项式展开直接给 $\Delta^k=(E-I)^k$ ，从而得到显式差分公式。再由 Pascal 恒等式的多项式版本证明 $\Delta\binom{x}{k}=\binom{x}{k-1}$ 。若 $p=\sum a_k\binom{x}{k}$ ，差分 $j$ 次后令 $x=0$ ，只有 $k=j$ 的项留下，因为 $\binom0r=0$ （ $r>0$ ），所以 $a_j=\Delta^jp(0)$ 。

次数判据的逆向也不能略掉。以 $f(0),\ldots,f(d)$ 作差分表构造上面的多项式 $p$ ，它在这 $d+1$ 个整数上等于 $f$ ：从样本 $f(0),\ldots,f(d)$ 到左端差分的变换是对角元为一的三角变换，而构造的 $p$ 具有同一组左端差分，所以样本也必相同。条件 $\Delta^{d+1}f(m)=0$ 是一个长度 $d+2$ 的线性递推，最前和最后项的系数都为 $\pm1$ 。所以这 $d+1$ 个初值既唯一确定向右所有值，也唯一确定向左所有值。 $p$ 满足同一递推，故与 $f$ 在全部整数上一致。

例子与边界

取 $p(x)=x^4$ ，在 $0,1,2,3,4$ 上依次作相邻差，得到

\begin{array}{c|rrrrr} p&0&1&16&81&256\\ \Delta p&1&15&65&175\\ \Delta^2p&14&50&110\\ \Delta^3p&36&60\\ \Delta^4p&24 \end{array}

每行最左值是 Newton 系数，所以

x^4=\binom x1+14\binom x2+36\binom x3+24\binom x4.

除回 $k!$ 后得到下降阶乘系数 $1,7,6,1$ ，独立吻合 $S(4,k)$ 。

要求 $\sum_{m=0}^{N-1}m^4$ ，只需把每个二项式下标升一：

\sum_{m=0}^{N-1}m^4 =\binom N2+14\binom N3+36\binom N4+24\binom N5.

因为 $\Delta\binom{m}{k+1}=\binom mk$ ，逐项求和后中间项望远镜抵消， $m=0$ 的端点全为零。 $N=4$ 时右侧为 $6+56+36=98$ ，左侧 $0+1+16+81$ 也为 $98$ 。这个表达无需先记忆展开后的五次幂和公式。

有限样本不能自动证明全局次数。例如函数 $x^4+c\,x(x-1)(x-2)(x-3)(x-4)$ 在前五个节点与 $x^4$ 一样，离开节点后可不同。另如 $\sin(2\pi x)$ 在所有整数上为零，却不是实变量上的零函数。差分表上的“观察到零”只有在给定次数界或已证明全格递推后才是完整证书。

在特征 $p$ 中， $x^p-x$ 是非零多项式，但 $\Delta(x^p-x)=0$ ；所以“每次恰降一次数”依赖特征零。等距网格 $a+mh$ 且 $h\ne0$ 可改用 $u=(x-a)/h$ ；对现有差商与 Newton 插值，等距时精确有 $f[a,a+h,\ldots,a+kh]=\Delta_h^kf(a)/(k!h^k)$ ，其中 $\Delta_hf(a)=f(a+h)-f(a)$ 。由差商递推归纳：相邻两项 $(k-1)$ 阶差商相减贡献 $\Delta_h^kf(a)/((k-1)!h^{k-1})$ ，再除最外节点差 $kh$ 即得。非等距节点没有这个共同分母，不能直接套同一差分表。

推论与应用

离散原函数总能在多项式中构造：若 $p=\sum a_k\binom{x}{k}$ ，则 $P=\sum a_k\binom{x}{k+1}$ 满足 $\Delta P=p$ ，任意两个多项式原函数只差常数。若扩大到实变量任意函数，差为一周期函数也可能具有零差分，唯一性边界随函数空间改变。

乘积法则也保留了平移：

\Delta(fg)(m)=f(m)\Delta g(m)+g(m+1)\Delta f(m).

逐项求和可得离散分部求和。漏掉 $g(m+1)$ 的平移会留下一个额外 $\Delta f\Delta g$ 项。这里研究精确离散代数；数值微分 stencil则把差商作为导数近似，还须分析步长、光滑性和舍入误差。

整值多项式进一步把 Newton 系数的整数性转成“所有整数输入都给整数”的有限证书。

参考资料

Richard P. Stanley，Enumerative Combinatorics, Vol. 1，作者第二版书稿，§1.9，式1.97–1.99、Proposition 1.9.2，书稿印页85–87：差分算子、四次差分表与次数判据。本页补出递推向两侧延拓及离散求和证明。
NIST DLMF，§3.3(iv)，Newton's Interpolation Formula：一般节点插值背景；等距的组合差分与数值误差任务应区分。

形式陈述 ​

反向链接

形式陈述