前言

本文参考自《具体数学》。

如有错漏敬请读者一一指出或喷作者。

可能的前置知识：

• 组合数及其处理技巧。
• 两类斯特林数。
• 拉格朗日插值。

当然不知道也没关系，与这些相关的大多是证明方面的东西。

问题引入

对于数列求和，我们有以下耳熟能详的公式：

1+2+3+\cdots+n=\sum_{k=1}^n k=\dfrac{n(n+1)}{2} 1+a+a^2+\cdots+a^{n-1}=\sum_{k=0}^{n-1}a^k=\dfrac{a^n-1}{a-1}

但这些公式缺乏一般性，例如将等差数列求和公式的 k 变为 k^2 或 k^3：

1^2+2^2+\cdots+n^2=\sum_{k=1}^nk^2=\dfrac{n(n+1)(2n+1)}{6} 1^3+2^3+\cdots+n^3=\sum_{k=1}^nk^3={\left(\sum_{k=1}^n k\right)}^2=\dfrac{n^2(n+1)^2}{4}

尽管我们可以用数学归纳法证明这些东西然后背下来，
但对于每一个新的数列和都去猜测结果然后证明，无疑是一件低效的做法。

这里将介绍《具体数学》中的系统方法——有限微积分，
解决非组合形式的数列求和问题。

裂项相消法

对于数列求和，有一个很重要的方法叫裂项相消法。

例如对于 \displaystyle\sum_{k=1}^n\dfrac{1}{k(k+1)}，我们有

\sum_{k=1}^n\dfrac{1}{k(k+1)}=\sum_{k=1}^n\dfrac{1}{k}-\dfrac{1}{k+1} ={\left(\dfrac{1}{1}-\dfrac{1}{2}\right)}+{\left(\dfrac{1}{2}-\dfrac{1}{3}\right)}+{\left(\dfrac{1}{3}-\dfrac{1}{4}\right)}+\cdots+{\left(\dfrac{1}{n}-\dfrac{1}{n+1}\right)} =1-\dfrac{1}{n+1}

可以看到，原数列被拆成了两个数列的差，然后首尾相消。

这一做法仍需要人类智慧，但它无疑告诉我们：求和和求差是一对互逆的运算。

而在微积分中，求导和积分也是一对互逆的运算，
并且它们分别对应差的极限与和的极限。

因此，我们可以利用微积分中的方法来解决求和问题。

差分

\Delta f(x)=f(x+1)-f(x)

意思是，\Delta f(x) 是一个新的函数，它等于 f(x) 的差。

接下来我们研究下差分的运算法则：

• 加法法则：\Delta (u+v)=\Delta u+\Delta v
  意思是，两个函数的和的差分等于两个函数的差分的和。
  直接套用定义即可证明：

  \Delta(f(x)+g(x))=f(x+1)+g(x+1)-f(x)-g(x) =f(x+1)-f(x)+g(x+1)-g(x)=\Delta f(x)+\Delta g(x)

• 减法法则：\Delta (u-v)=\Delta u-\Delta v
  同上。

• \Delta(Cu)=C\Delta u

  其中 C 为一个与 x 无关的常数。
  亦可直接套用定义证明，此处不再赘述。

• 乘法法则：\Delta(uv)=u\Delta v+\mathrm{E}v\Delta u
  其中 \mathrm{E}f(x)=f(x+1)。
  证明：\Delta(f(x)g(x))=f(x+1)g(x+1)-f(x)g(x)

  $$ =f(x+1)g(x+1)-f(x)g(x+1)+f(x)g(x+1)-f(x)g(x) $$ $$ =(f(x+1)-f(x))g(x+1)+(g(x+1)-g(x))f(x) $$ $$ =g(x+1)\Delta f(x)+f(x)\Delta g(x) $$ $$ =f(x)\Delta g(x)+\mathrm{E} g(x)\Delta f(x) $$

遗憾的是，相比于无限微积分，有限微积分没有除法法则和链式法则。

定和式

有了差分之后，我们开始系统性的解决求和问题。定义定和式

{\sum}_a^bf(x)\delta x=\sum_{k=a}^{b-1}f(k)=f(a)+f(a+1)+f(a+2)+\cdots f(b-1)

它与差分是一对互逆的运算。具体的，根据裂项相消法，有微积分基本定理

{\sum}_a^b\Delta f(x)\delta x=f(b)-f(a)

同样套用定义，可知定和式满足以下性质：

• \displaystyle{\sum}_a^af(x)\delta x=0,{\sum}_a^bf(x)\delta x=-{\sum}_b^af(x)\delta x
• \displaystyle{\sum}_a^b f(x)\delta x+{\sum}_b^cf(x)\delta x={\sum}_a^c f(x)\delta x
• \displaystyle{\sum}_a^bf(x)\delta x \pm{\sum}_a^b g(x)\delta x={\sum}_a^b(f(x)\pm g(x))\delta x
• \displaystyle{\sum}_a^b Cf(x)\delta x=C{\sum}_a^b f(x)\delta x

例题 1：求解等比数列和 \displaystyle\sum_{k=0}^{n-1}a^k\quad(a\not= 1) 。
解：首先考虑指数函数的差分

\Delta(a^x)=a^{x+1}-a^x=(a-1)a^x

套用运算法则得到

a^x=\Delta{\left(\dfrac{a^x}{a-1}\right)}

因此

\sum_{k=0}^{n-1}a^k={\sum}_0^na^x\delta x={\sum}_0^n\Delta{\left(\dfrac{a^x}{a-1}\right)}\delta x=\dfrac{a^n}{a-1}-\dfrac{a^0}{a-1}=\dfrac{a^n-1}{a-1}

由此得到了等比数列求和公式。

下降幂

直接套用运算法则能迅速求解指数函数的和，幂函数却并不能这么干

\Delta(x^n)=(x+1)^n-x^n=\sum_{k=0}^{n-1}\dbinom{n}{k}x^k

同样的做法在无限微积分中却得到了极为优美的结论：(x^n)'=nx^{n-1}

问题出在 “幂” 上。具体的，对于下降幂

x^{\underline{n}}=\begin{cases} x(x-1)(x-2)\cdots(x-n+1) & (n>0)\\ 1 &(n=0)\\ \dfrac{1}{(x+1)(x+2)\cdots (x+(-n))}&(n<0) \end{cases}

有一个同等优美的结论：

\Delta(x^{\underline{n}})=(x+1)^{\underline{n}}-x^{\underline{n}}=((x+1)-(x-n+1))x^{\underline{n-1}}=nx^{\underline{n-1}}

作跟指数函数一样的变形，就可得到

x^{\underline{n}}=\Delta{\left(\dfrac{x^{\underline{n+1}}}{n+1}\right)}

例题 2：求解等差数列和 \displaystyle\sum_{k=1}^n k 。
解：\displaystyle\sum_{k=1}^nk={\sum}_1^{n+1}x\delta x=\dfrac{1}{2}(n+1)^{\underline{2}}-\dfrac{1}{2}1^{\underline{2}}=\dfrac{n(n+1)}{2}

例题 3：求解 \displaystyle\sum_{k=1}^n\dfrac{1}{k(k+1)} 。
解：\displaystyle\sum_{k=1}^n\dfrac{1}{k(k+1)}=\sum_{k=0}^{n-1}k^{\underline{-2}}={\sum}_0^nx^{\underline{-2}}\delta x=\dfrac{n^{\underline{-1}}-0^{\underline{-1}}}{-1}=1-\dfrac{1}{n+1}

例题 4：P1625 求和
解：\displaystyle\sum_{i=1}^n\left(\prod_{j=i}^{i+m-1}j\right)^{-1}=\sum_{i=0}^{n-1}\left(\prod_{j=i+1}^{i+m}j\right)^{-1}=\sum_{i=0}^{n-1}\dfrac{1}{(i+m)^{\underline{m}}}

={\sum}_0^nx^{\underline{-m}}\delta x=\dfrac{n^{\underline{-m+1}}-0^{\underline{-m+1}}}{-m+1}=\dfrac{(n+m-1)^{\underline{n}}-n!}{(m-1)(n+m-1)!}

高精算出上面，下面分解质因数约分即可。

例题 5：求证上指标求和公式 \displaystyle\sum_{k=0}^n\dbinom{k}{m}=\dbinom{n+1}{m+1} 。
证明：\displaystyle\sum_{k=0}^n\dbinom{k}{m}=\sum_{k=0}^n\dfrac{k^{\underline{m}}}{m!}=\dfrac{1}{m!}{\sum}_0^{n+1}x^{\underline{m}}\delta{x}

=\dfrac{(n+1)^{\underline{m+1}}-0^{\underline{m+1}}}{m!(m+1)}=\dfrac{(n+1)^{\underline{m+1}}}{(m+1)!}=\dbinom{n+1}{m+1}

例题 6：求解 \displaystyle\sum_{k=1}^n k^2。
解：\displaystyle\sum_{k=1}^nk^2=\sum_{k=0}^nk^2={\sum}_0^{n+1}(x^{\underline{2}}+x)\delta x=\dfrac{1}{3}(n+1)^{\underline{3}}+\dfrac{1}{2}(n+1)^{\underline{2}}

=(n+1)n{\left(\dfrac{1}{3}(n-1)+\dfrac{1}{2}\right)}=\dfrac{(n+1)n(2n+1)}{6}

例题 7：求解 \displaystyle\sum_{k=1}^n k^3 。
解：\displaystyle\sum_{k=1}^nk^3=\sum_{k=0}^nk^3={\sum}_0^{n+1}(x^{\underline{3}}+3x^{\underline{2}}+x)\delta x

=\dfrac{1}{4}(n+1)^{\underline{4}}+(n+1)^{\underline{3}}+\dfrac{1}{2}(n+1)^{\underline{2}}=\dfrac{n^2(n+1)^2}{4}

由后两个例题可知，对于带幂函数的和式，首先要将普通幂转为下降幂。

两类斯特林数已经给出了二者间的转化关系：

x^n=\sum_{k=0}^n{n\brace k}x^{\underline{k}} x^{\underline{n}}=\sum_{k=0}^n{n\brack k}(-1)^{n-k}x^k

由此得到自然数幂和的一个公式

\sum_{i=0}^{n-1}i^m=\sum_{k=0}^m{m\brace k}\sum_{i=0}^{n-1}i^{\underline{k}}=\sum_{k=0}^m{m\brace k}{\sum}_0^nx^{\underline{k}}\delta x=\sum_{k=0}^m{m\brace k}\dfrac{n^{\underline{k+1}}}{k+1}

另一公式为伯努利数，二者的区别在于一个形式为下降幂，一个形式为普通幂。

不定和式与分部求和

有了定和式，相应的，有不定和式：

f(x)=\sum\Delta f(x)\delta x+C

其中 C 为计算完成后确定的常数。

对于差分的乘法法则 \Delta(uv)=u\Delta v+\mathrm{E}v\Delta u，移项再取和式可得分部求和法则

\sum u\Delta v=uv-\sum\mathrm{E}v\Delta u

使用时切记是 \mathrm{E}v 而非 \mathrm{E}\Delta v。

例题 8：求解 \displaystyle\sum_{i=0}^{n-1} i^{\underline{k}}a^i,a\not= 1,k 较小。
解：由分部求和法则得

\sum x^{\underline{k}}a^x\delta x=\dfrac{x^{\underline{k}}a^x}{a-1}-\sum \dfrac{a^{x+1}}{a-1}kx^{\underline{k-1}}\delta x =\dfrac{x^{\underline{k}}a^x}{a-1}-\dfrac{ka}{a-1}\sum a^xx^{\underline{k-1}}\delta x =\dfrac{a^x}{a-1}\sum_{i=0}^k{\left(\dfrac{-a}{a-1}\right)}^ik^{\underline{i}}x^{\underline{k-i}}

因此 \displaystyle\sum_{i=0}^{n-1}i^{\underline{k}}a^i={\sum}_0^nx^{\underline{k}}a^x\delta x=\dfrac{1}{a-1}\sum_{i=0}^k{\left(\dfrac{-a}{a-1}\right)}^ik^{\underline{i}}(a^nn^{\underline{k-i}}-a^00^{\underline{k-i}})

这一公式应用性较强：

例题 9：P4948 数列求和
例题 10：P5349 幂

高阶差分

与高阶导数相应的，可定义高阶差分

\Delta^0f=f,\Delta^n f=\Delta^{n-1}(\Delta f)

由 \Delta f(x)=f(x+1)-f(x),\mathrm{E}f(x)=f(x+1) 得 \Delta=\mathrm{E}-1，因此

\Delta^n f=(\mathrm{E}-1)^nf=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}\mathrm{E}^kf

其中 \mathrm{E}^n 的定义同 \Delta^n。

与泰勒展开类似的，对 f(x) 某一点不断求差分，就可得到等间距牛顿插值公式

f(x)=\sum_{k=0}^{\infty}\dfrac{\Delta^kf(x_0)}{k!}(x-x_0)^{\underline{k}}=\sum_{k=0}^{\infty}\dbinom{x-x_0}{k}\Delta^{k}f(x_0)

之所以称为插值，是因为对于多项式函数，其与拉格朗日插值等价。

证明：设 \deg f=n，综合以上两个公式得

f(x)=\sum_{k=0}^\infty\dbinom{x}{k}\sum_{i=0}^k\dbinom{k}{i}(-1)^{k-i}\mathrm{E}^if(x_0) f(x)=\sum_{k=0}^n\sum_{i=0}^k\dbinom{x}{k}\dbinom{k}{i}(-1)^{k-i}f(i) f(x)=\sum_{k=0}^n\sum_{i=0}^k\dbinom{x}{i}\dbinom{x-i}{k-i}(-1)^{k-i}f(i)

此处使用了三项式版恒等式 \dbinom{n}{m}\dbinom{m}{k}=\dbinom{n}{k}\dbinom{n-k}{m-k} 。

调换下求和顺序

f(x)=\sum_{i=0}^n\dbinom{x}{i}f(i)\sum_{k=i}^n\dbinom{x-i}{k-i}(-1)^{k-i} f(x)=\sum_{i=0}^n\dbinom{x}{i}f(i)\sum_{k=0}^{n-i}\dbinom{x-i}{k}(-1)^k

使用上指标翻转 \dbinom{r}{k}=\dbinom{k-r-1}{k}(-1)^k，

f(x)=\sum_{i=0}^n\dbinom{x}{i}f(i)\sum_{k=0}^{n-i}\dbinom{k-(x-i)-1}{k}

使用平行求和法 \displaystyle\sum_{k=0}^n\dbinom{r+k}{k}=\dbinom{r+n+1}{n}，

f(x)=\sum_{i=0}^n\dbinom{x}{i}f(i)\dbinom{n-i-(x-i)-1+1}{n-i} f(x)=\sum_{i=0}^nf(i)\dbinom{x}{i}\dbinom{n-x}{n-i} f(x)=\sum_{i=0}^nf(i)\left(\prod_{j=0}^{i-1}\dfrac{x-j}{i-j}\right)\left(\prod_{j=i+1}^n\dfrac{x-j}{i-j}\right) f(x)=\sum_{i=0}^nf(i)\prod_{j\not=i}\dfrac{x-j}{i-j}

由此得到其与拉格朗日插值等价。

实际应用中，f(x)\displaystyle=\sum_{i=0}^nf(i)\dbinom{x}{i}\dbinom{n-x}{n-i} 较好记且便于实现。

例题 11：P5907 数列求和加强版 / SPOJ MOON4

偏差分

对于二元函数 f(x,y)，我们可以分别定义其对 x,y 的 偏差分

\Delta_x f(x,y)=f(x+1,y)-f(x,y) \Delta_y f(x,y)=f(x,y+1)-f(x,y)

那么，自然有

\Delta_x\Delta_y f(x,y)=\Delta_y\Delta_x f(x,y)=f(x+1,y+1)-f(x+1,y)-f(x,y+1)+f(x,y)

也就是说 \Delta_x\Delta_y=\Delta_y\Delta_x，即对不同变量的偏差分是可交换的。

相应地，可以定义 n 元函数 f(x_1,x_2,\cdots,x_n) 的偏差分，
而我们一般所说的 n 维差分，其实就是

\Delta_{x_1}\Delta_{x_2}\cdots\Delta_{x_n}f

与高阶差分的计算类似的，\Delta_x=\mathrm{E}_x-1，即可得到

\Delta_{x_1}\Delta_{x_2}\cdots\Delta_{x_n}f=(\mathrm{E}_{x_1}-1)(\mathrm{E}_{x_2}-1)\cdots(\mathrm{E}_{x_n}-1)f\\ =\sum_{c_1,c_2,\cdots,c_n\in\{0,1\}}(-1)^{n-\sum_{k=1}^nc_k}\mathrm{E}_{x_1}^{c_1}\mathrm{E}_{x_2}^{c_2}\cdots\mathrm{E}_{x_n}^{c_n}f $$ {\sum}_{a_n}^{b_n}{\sum}_{a_{n-1}}^{b_{n-1}}\cdots{\sum}_{a_1}^{b_1}\Delta_{x_1}\Delta_{x_2}\cdots\Delta_{x_n}f(x_1,x_2,\cdots,x_n)\delta x_1\delta x_2\cdots\delta x_n\\ =\sum_{c_1,c_2,\cdots,c_n\in\{0,1\}}(-1)^{\sum_{k=1}^nc_k}f(b_1+c_1(a_1-b_1),b_2+c_2(a_2-b_2),\cdots,b_n+c_n(a_n-b_n)) $$ # Stolz 定理 接下来需要涉及部分无限微积分方面的知识。 与无限微积分中求函数极限的洛必达法则类似，我们在有限微积分中有求数列极限的 **Stolz 定理** 。 - **Stolz 第一公式**：若 $\{b_n\}$ **严格单调且发散**，且 $\displaystyle\lim_{n\rightarrow+\infty}\dfrac{\Delta a_n}{\Delta b_n}$ 为有限数或 $\pm\infty$，则 $$ \lim_{n\rightarrow+\infty}\dfrac{a_n}{b_n}=\lim_{n\rightarrow+\infty}\dfrac{\Delta a_n}{\Delta b_n} $$ - **Stolz 第二公式**：若 $\displaystyle\lim_{n\rightarrow+\infty}a_n=\lim_{n\rightarrow+\infty}b_n=0$，且 $\{b_n\}$ **严格单调**，$\displaystyle\lim_{n\rightarrow+\infty}\dfrac{\Delta a_n}{\Delta b_n}$ 为有限数或 $\pm\infty$，则 $$ \lim_{n\rightarrow+\infty}\dfrac{a_n}{b_n}=\lim_{n\rightarrow+\infty}\dfrac{\Delta a_n}{\Delta b_n} $$ 限于篇幅，Stolz 定理的证明略去。 需注意的是，该定理的逆命题并不成立，即不能用 $\displaystyle\lim_{n\rightarrow+\infty}\dfrac{\Delta a_n}{\Delta b_n}$ 不存在推出 $\displaystyle\lim_{n\rightarrow+\infty}\dfrac{a_n}{b_n}$ 不存在。 # [调和数](https://www.luogu.com.cn/problem/P5702) $$ H_n=\sum_{i=1}^n\dfrac{1}{i}={\sum}_0^nx^{\underline{-1}}\delta x $$ 这是有限微积分唯一一个瑕点，它没有初等的通项公式。 但我们可以估计它的增长率。首先，我们有 $$ 1+\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{8}+\dfrac{1}{8}+\dfrac{1}{8}+\dfrac{1}{8}+\cdots $$ $$ <1+\dfrac{1}{2}+\dfrac{1}{3}+\dfrac{1}{4}+\dfrac{1}{5}+\dfrac{1}{6}+\dfrac{1}{7}+\dfrac{1}{8}+\cdots< $$ $$ 1+\dfrac{1}{2}+\dfrac{1}{2}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{8}+\cdots $$ $$ 1+\dfrac{1}{2}\lfloor\log_2 n\rfloor\le H_n\le \lceil\log_2 (n+1)\rceil $$ 因此调和数呈对数增长。 更进一步的估计是使用 Stolz 第二公式： $$ \lim_{n\rightarrow+\infty}\dfrac{\ln n}{H_n}=\lim_{n\rightarrow+\infty}\dfrac{\ln (n+1)-\ln n}{\dfrac{1}{n+1}}=\lim_{n\rightarrow+\infty}\dfrac{-\ln\left(1-\dfrac{1}{n+1}\right)}{\dfrac{1}{n+1}} $$ 对分子进行泰勒展开，得 $$ \lim_{n\rightarrow+\infty}\dfrac{-\ln\left(1-\dfrac{1}{n+1}\right)}{\dfrac{1}{n+1}}=\lim_{n\rightarrow+\infty}\dfrac{\displaystyle\sum_{k=1}^{+\infty}\dfrac{1}{k(n+1)^k}}{\dfrac{1}{n+1}}=\lim_{n\rightarrow+\infty}\dfrac{\displaystyle\sum_{k=1}^{+\infty}\dfrac{1}{k(n+1)^k}}{\dfrac{1}{n+1}} $$ $$ =\lim_{n\rightarrow+\infty}\sum_{k=1}^{+\infty}\dfrac{1}{k(n+1)^{k-1}}=\lim_{n\rightarrow+\infty}\sum_{k=0}^{+\infty}\dfrac{1}{k+1}\left(\dfrac{1}{n+1}\right)^k=1 $$ 因此调和级数与自然对数渐进等价，即 $$ \lim_{n\rightarrow+\infty}\dfrac{\ln n}{H_n}=1 $$ 同样用作差分再泰勒展开的方法，可以证明调和数有渐进公式 $$ H_n=\ln n+\gamma+\varepsilon_n $$ $\gamma$ 称为欧拉-马歇罗尼常数，$\varepsilon_n$ 约等于 $\dfrac{1}{2n}$。 # 总结 $$ \Delta f(x)=f(x+1)-f(x),{\sum}_a^bf(x)\delta x=\sum_{k=a}^{b-1}f(k) $$ $$ {\sum}_a^b\Delta f(x)\delta x=f(b)-f(a) $$ $$ \Delta(a^x)=(a-1)a^x,\Delta(x^{\underline{n}})=nx^{\underline{n-1}} $$ $$ f(x)=\sum\Delta f(x)\delta x+C,\sum u\Delta v=uv-\sum\mathrm{E}v\Delta u $$ $$ \Delta^n f=(\mathrm{E}-1)^nf=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}\mathrm{E}^kf $$ $$ f(x)=\sum_{k=0}^{\infty}\dbinom{x-x_0}{k}\Delta^{k}f(x_0)=\sum_{i=0}^nf(i)\dbinom{x}{i}\dbinom{n-x}{n-i} $$ $$ \Delta_xf(x,y)=f(x+1,y)-f(x,y),\Delta_yf(x,y)=f(x,y+1)-f(x,y) $$ $$ \Delta_{x_1}\Delta_{x_2}\cdots\Delta_{x_n}f=\sum_{c_1,c_2,\cdots,c_n\in\{0,1\}}(-1)^{n-\sum_{k=1}^nc_k}\mathrm{E}_{x_1}^{c_1}\mathrm{E}_{x_2}^{c_2}\cdots\mathrm{E}_{x_n}^{c_n}f $$ $$ {\sum}_{a_n}^{b_n}{\sum}_{a_{n-1}}^{b_{n-1}}\cdots{\sum}_{a_1}^{b_1}\Delta_{x_1}\Delta_{x_2}\cdots\Delta_{x_n}f(x_1,x_2,\cdots,x_n)\delta x_1\delta x_2\cdots\delta x_n\\ =\sum_{c_1,c_2,\cdots,c_n\in\{0,1\}}(-1)^{\sum_{k=1}^nc_k}f(b_1+c_1(a_1-b_1),b_2+c_2(a_2-b_2),\cdots,b_n+c_n(a_n-b_n)) $$ $$ H_n=\sum_{i=1}^n\dfrac{1}{i}=\ln n+\gamma+\varepsilon_n $$ - 尽管没有无限微积分那么优秀的性质，有限微积分仍能高效地处理求和问题。 - 从小学到高中的所有数列求和，在有限微积分中得到统一。 Upd 2023.10.6：添加了 Stolz 定理，并用其实现了对调和数的进一步估计。 Upd 2024.12.18：添加了偏差分。