差分与有限微积分

阅读这篇文章需要微积分基础。
从《具体数学》上看来的，感觉十分有用。
为了思维的连贯性，省略了大量细节。这些细节将在最后补充。

差分算子

首先，有一个关于“算子”的定义：

如果一个运算作用在函数上，则我们称这个运算为“算子”。

显然，多项式的卷积、狄利克雷卷积等都是算子。
在迈入高等数学的大门时，我们遇到过一个强劲的算子：微分算子。

微分算子$\text{D}$是这样定义的：$\text{D}f\left(x\right)=\underset{h\to 0}{lim}\frac{f(x+h)-f\left(x\right)}{h}$.它的几何意义是，对于某个$x$，以 ($x$加上无穷小) 处的函数值减去$x$的函数值。
因此，$\text{D}f\left(x\right)$就是$f\left(x\right)$的导函数。

由于微分算子使用了无穷小，所以微分算子用于连续数学。但是对于别的函数——它们只能在整数范围内取值，微分算子就无法通用。

面对离散数学，定义差分算子$\Delta$：$\Delta f\left(x\right)=f(x+1)-f\left(x\right)$.

它的几何意义如图：

容易看出，差分算子给出相邻的整数之间函数值的差。

有限微积分

众所周知，微分里有一个很妙的公式：$\text{D}\left(x^m\right)=m\cdot x^{m-1}$.
差分有没有类似的公式呢？

来考虑下降阶乘幂：$x^{\underset{–}{m}}=x\cdot (x-1)\cdot (x-2)\cdots (x-m+1)$.
手推一番，我们发现$\Delta \left(x^{\underset{–}{m}}\right)=m\cdot x^{\underset{–}{m-1}}$.
惊喜的是，差分的运算法则和微分的运算法则如出一辙。例如$\text{D}f\left(x\right)+\text{D}g\left(x\right)=\text{D}\left(f\right(x)+g(x\left)\right)$之类的导数运算，都可以直接套在差分上。

有什么用？

牛顿-莱布尼茨公式：若$g\left(x\right)=\text{D}f\left(x\right)$，则有${\int }_a^{b}g\left(x\right)=f\left(b\right)-f\left(a\right)$. 类似积分，可以构造出和式：

首先，我们令${\sum }_a^{b}f\left(x\right)=\sum _{i=a}^{b-1}f\left(x\right)$.注意两个$\Sigma$之间的区别。

那么有基本定理：

如果$g\left(x\right)=\Delta f\left(x\right)$,则有${\sum }_a^{b}g\left(x\right)=f\left(b\right)-f\left(a\right)$.

如何理解这个公式？举个例子。假设我们找到了$g\left(x\right)=\Delta f\left(x\right)$，那么我们可以快速求：
$\sum _{i=1}^{n}g\left(x\right)={\sum }_1^{n+1}g\left(x\right)=f(n+1)-f\left(1\right)$.

回到之前讨论的下降阶乘幂。我们有$\Delta \left(x^{\underset{–}{m}}\right)=m\cdot x^{\underset{–}{m-1}}$.
所以实践中，可以直接用下降阶乘幂来解决问题。

例子

求$\sum _{i=0}^{100}{x}^2$.

首先，我们把$x^2$表示成下降阶乘幂的形式。稍加计算得到：$g\left(x\right)=x^2=x(x-1)+x=x^{\underset{–}{2}}+x^{\underset{–}{1}}$.

然后构造$g\left(x\right)$的原函数：$f\left(x\right)=\frac{1}{3}{x}^{\underset{–}{3}}+\frac{1}{2}{x}^{\underset{–}{2}}=\frac{x(x-1)(x-2)}{3}+\frac{x(x-1)}{2}$.

于是有：$\sum _{i=0}^{100}{x}^2={\sum }_0^{101}g\left(x\right)=f\left(101\right)-f\left(0\right)=\frac{101\cdot 100\cdot 99}{3}+\frac{101\cdot 100}{2}=338350$.

这就是有限微积分。

一个例题

求$1^k+2^k+3^k\cdots +n^k$.

$n<1000,k<1000$
暴力。

$n<100000,k<1000000$
快速幂。

$n<{10}^8,k<10$
先写个程序推出$x^k$的下降阶乘幂形式，然后用有限微积分$O\left(1\right)$做。

$n<{10}^8,k<1000$
从有限微积分中可以知道，答案一定是一个$k+1$阶多项式。

故先$O\left(n\log k\right)$求出$n=1,2,3\cdots k+1$时的答案，然后$O\left(k^2\right)$插值回多项式(拉格朗日插值法)，然后$O\left(k\right)$计算答案(霍纳法则)。
总复杂度$O\left(k^2\right)$.

$n<={10}^8,k<{10}^5$
orz Gromah.

几个细节

差分表

原函数$f\left(x\right)$	差分函数$\Delta f\left(x\right)$
$x^{\underset{–}{m}}$	$m\cdot x^{\underset{–}{m-1}}$
$2^x$	$2^x$
$c^x$	$(c-1)c^x$

差分运算法则
下面的向量代表函数。

原函数$f\left(x\right)$	差分函数$\Delta f\left(x\right)$
$c\cdot \overrightarrow{u}$	$c\cdot \Delta \overrightarrow{u}$
$\overrightarrow{u}+\overrightarrow{v}$	$\Delta \overrightarrow{u}+\Delta \overrightarrow{v}$

序列差分

考虑一个序列的差分： $\{a_1,a_2,a_3\cdots \}\leftrightarrow \{a_2-a_1,a_3-a_2,\cdots \}$
记一阶差分的结果为$\overrightarrow{b}$，对$\overrightarrow{b}$再做一次差分，得到二阶差分：
$\{b_2-b_1,b_3-b_2,\cdots \}$

如果这个初始序列由$f\left(1\right),f\left(2\right)\cdots$给出，则有：
如果$f\left(x\right)$是$k$次多项式，那么$\overrightarrow{a}$的$k+1$阶差分全部相等，$k+2$阶差分全为$0$.

例如：$f\left(x\right)=x^3$

(0, 1, 8, 27, 64, 125)    ->
(1, 7, 19, 37, 61)        ->
(6, 12, 18, 24)           ->
(6, 6, 6)                 ->
(0, 0)

负指数下降幂

定义$x^{-\underset{–}{m}},m\in Z_{+}$为：
$x^{-\underset{–}{m}}=\frac{1}{(x+1)\cdot (x+2)\cdot (x+3)\cdots }$