「学习笔记」浅谈离散微积分

微积分是数学分析中的有力工具,其核心是微分和积分,类比微积分中的一整套系统,《具体数学》中引入了一套研究差分和求和的工具——离散微积分 (discrete calculus)

回顾微积分

在微积分中,我们有微分算子 (differential operator) $Df(x)=\lim\limits_{\Delta x\rightarrow0}\frac{f(x+\Delta x)-f(x)}{\Delta x}$

若有 $DF(x)=f(x)$ 则称 $F(x)$ 是 $f(x)$ 的原函数

微积分的核心:牛顿 - 莱布尼茨公式 (Newton - Leibniz formula) $\int_a^bf(x)dx=F(b)-F(a)$

定义与记号

类比微分算子,定义差分算子 $\Delta f(x)=f(x+1)-f(x)$

类似地,若 $\Delta F(x)=f(x)$ 则称 $F(x)$ 是 $f(x)$ 的原函数,不难发现 $\sum\limits_{x=a}^{b-1}f(x)=F(b)-F(a)$

于是类比定积分,定义和式 $\sum\limits_a^bf(x)\delta x=\sum\limits_{x=a}^{b-1}f(x)=F(b)-F(a)$

类比不定积分,有不定和式 $\sum f(x)\delta x=F(x)+C$ 其中 $C$ 为常数

至此,我们类比定义了离散情况下的微分、积分和牛顿 - 莱布尼茨公式

从定义开始完善系统

仅靠定义和牛顿 - 莱布尼茨公式构建不起微积分的大厦,同样的,刚才定义的记号也无法帮助我们快速计算和式,我们需要进一步探究它的性质

首先,根据定义显然有差分算子对于加法、减法的分配率成立

幂法则

先从微积分中最简单的幂法则说起,寻找它的替代品

在微积分中,有 $Dx^n=nx^{n-1}$ 但显然 $\Delta x^n\neq nx^{n-1}$,但是我们有一种类似幂的数学工具:下降幂

定义下降幂 $x^\underline{n}=\frac{x!}{(x-n)!}$

发现 $\Delta x^\underline{n}=\frac{(x+1)!}{(x-n+1)!}-\frac{x!}{(x-n)!}=nx^\underline{n-1}$

同样的,在 $n\neq-1$ 时,有不定和式 $\sum x^\underline{n}\delta x=\frac{x^\underline{n+1}}{n+1}+C$

类似 $\int\frac{1}{x}dx=\ln x+C$,$n=1$ 时,有 $\sum x^{\underline{-1}}\delta x=H_x+C$,其中 $H_x$ 为调和级数前 $x$ 项和,不难发现 $x\rightarrow\infty$ 时 $H_x=\ln x+\gamma$ 其中 $\gamma$ 为 欧拉 - 马歇罗尼常数,这一点也印证了离散微积分和微积分密不可分的联系

例题:

求和 $\sum\limits_{x=1}^nx^2$

首先有 $x^2=x^\underline{2}+x^\underline{1}$

考虑求出原函数
$$\begin{aligned}\sum x^2\delta x=&\sum(x^\underline{2}+x^\underline{1})\delta x\\
=&\frac{x^{\underline{3}}}{3}+\frac{x^{\underline{2}}}{2}+C\\
=&\frac{x(x-1)(2x-1)}{6}+C
\end{aligned}$$

于是有
$$\begin{aligned}\sum\limits_{x=1}^nx^2
&=\sum\limits_1^{n+1}x^2\delta x\\
&=\frac{n(n+1)(2n+1)}{6}+C-(0+C)\\
&=\frac{n(n+1)(2n+1)}{6}
\end{aligned}$$

在 OI 中,我们可以将多项式转换为下降幂多项式,从而在 $\operatorname{O}(n\log^2n)$ 时间内求出 $n$ 次多项式的值的前缀和

至此,我们探究出了多项式的差分、求和并探寻了离散微积分在处理求和上的初步应用

指数函数

在微积分中,以 $e$ 为底的指数函数 $e^x$ 拥有良好的性质:$De^x=e^x$ 和 $\int e^xdx=e^x+C$ 那么在离散微积分中是否也有具备这种性质的函数呢?

答案是有的:$2^x$

不难发现 $D2^x=2^{x+1}-2^x=2^x$ 和 $\sum2^x\delta x=2^x+C$

在微积分中,对于任意底数的指数函数 $a^x$ 有 $Da^x=a^x\ln a$ 和 $\int a^xdx=\frac{a^x}{\ln a}+C$

首先 $a^x$ 的差分显然是 $a^x(a-1)$

考虑 $a^x$ 的不定和式,不妨设 $\sum a^x\delta x=ka^x+C$,两边求差分得 $k=\frac{1}{a-1}$,于是 $\sum a^x\delta x=\frac{a^x}{a-1}+C$

积法则

定义平移算子 $Ef(x)=f(x+1)$

不难发现

$$\begin{aligned}\Delta(u(x)v(x))&=u(x+1)v(x+1)-u(x)v(x)\\
&=u(x+1)v(x+1)-u(x+1)v(x)+u(x+1)v(x)-u(x)v(x)\\
&=u(x+1)\Delta v(x)+v(x)\Delta u(x)\\
&=u(x)\Delta v(x)+v(x+1)\Delta u(x)
\end{aligned}$$

更为简单的表示为:$\Delta(uv)=u\Delta v+Ev\Delta u=Eu\Delta v+v\Delta u$

分部求和

在微积分中有分部积分公式:$\int udv=uv-\int vdu$

这一公式是对微分的积法则移项后左右积分得到的

同理也可以得到分部求和的公式:

$$\begin{aligned}
\Delta(uv)&=u\Delta v+Ev\Delta u \\
\Rightarrow u\Delta v&=\Delta(uv)-Ev\Delta u \\
\Rightarrow\sum u\Delta v&=uv-\sum Ev\Delta u
\end{aligned}$$

例题与应用

求和 $\sum\limits_{x=0}^nx2^x$

先求原函数,考虑带入 $u=x,\Delta v=2^x,\Delta u=1,v=2^x$:
$$\begin{aligned}&\sum x2^x\delta x\\
=&x2^x-\sum2^{x+1}\delta x\\
=&x2^x-2^{x+1}+C
\end{aligned}$$

于是有:
$$\begin{aligned}\sum\limits_{x=0}^nx2^x&=\sum_0^{n+1}x2^x\delta x\\
&=(n+1)2^{n+1}-2^{n+2}+C-(0-2+C)\\
&=(n-1)2^{n+1}+2\end{aligned}$$

求和 $\sum\limits_{x=1}^n(-1)^xx^2$

先求原函数,考虑带入 $u=x^2,\Delta v=(-1)^x,\Delta u=2x+1,v=-\frac{(-1)^x}{2}$:
$$\begin{aligned}&\sum x^2(-1)^x\delta x\\
=&-\frac{x^2(-1)^x}{2}-\sum-\frac{(-1)^{x+1}(2x+1)}{2}\delta x\\
=&-\frac{x^2(-1)^x}{2}-\sum\frac{2x+1}{2}(-1)^x\delta x
\end{aligned}$$

对于后一项继续分部求和,带入 $u=\frac{2x+1}{2},\Delta v=(-1)^x,\Delta u=1,v=-\frac{(-1)^x}{2}$:

$$\begin{aligned}&\sum\frac{2x+1}{2}(-1)^x\delta x\\
=&-\frac{(2x+1)(-1)^x}{4}-\sum-\frac{(-1)^{x+1}}{2}\delta x\\
=&-\frac{(2x+1)(-1)^x}{4}-\frac{1}{2}\sum(-1)^x\delta x\\
=&-\frac{(2x+1)(-1)^x}{4}+\frac{1}{4}(-1)^x+C\\
=&-\frac{(-1)^xx}{2}+C
\end{aligned}$$

带回上式:
$$\begin{aligned}&\sum(-1)^xx^2\delta x\\
=&-\frac{x^2(-1)^x}{2}+\frac{(-1)^xx}{2}+C\\
=&-\frac{(-1)^xx(x-1)}{2}+C
\end{aligned}$$

求和:
$$\begin{aligned}&\sum\limits_{i=1}^n(-1)^xx^2\\
=&-\frac{(-1)^{n+1}n(n+1)}{2}-\left(-\frac{-1\times1\times0}{2}\right)\\
=&\frac{(-1)^nn(n+1)}{2}
\end{aligned}$$

HEOI/TJOI 2016 求和:洛谷 LOJ

求和 $\sum\limits_{i=0}^n\sum\limits_{j=0}^i\left\{\begin{matrix}i\\j\end{matrix}\right\}\times2^j\times(j!)$

首先进行变形:
$$\begin{aligned}&\sum\limits_{i=0}^n\sum\limits_{j=0}^i\left\{\begin{matrix}i\\j\end{matrix}\right\}\times2^j\times(j!)\\
=&\sum\limits_{i=0}^n\sum\limits_{j=0}^n\left\{\begin{matrix}i\\j\end{matrix}\right\}\times2^j\times(j!)\\
=&\sum\limits_{i=0}^n\sum\limits_{j=0}^n2^j\sum\limits_{k=0}^j(-1)^{j-k}\binom{j}{k}k^i\\
=&\sum\limits_{k=0}^nf(k)(-1)^k\sum\limits_{j=0}^n(-2)^j\binom{j}{k}
\end{aligned}$$

其中 $f(k)=\sum_{i=0}^nk^i$,特别地 $0^0=1$

考虑用离散微积分简化后一个和式,于是求原函数,考虑带入$u=\binom{j}{k},\Delta v=(-2)^j,\Delta u=\binom{j}{k-1},v=\frac{(-2)^j}{-3}$:
$$\sum(-2)^j\binom{j}{k}\delta j=\frac{(-2)^j}{-3}\binom{j}{k}-\frac{-2}{-3}\sum(-2)^j\binom{j}{k-1}\delta j$$

另外有:
$$\sum(-2)^j\binom{j}{0}\delta j=\sum\frac{(-2)^j}{-3}$$

于是对于每一个 $k$ 递推出它的原函数在 $n+1$ 和 $0$ 处的值,相减即可

用线性筛筛出 $f(k)$ 即可在 $\operatorname{O}(n)$ 时间内得到答案

完。

本博客采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可
本文链接:https://blog.seniorious.cc/2020/Discrete-Calculus/