前言

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

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

可能的前置知识：

组合数及其处理技巧。
两类斯特林数。
拉格朗日插值。
当然不知道也没关系，与这些相关的大多是证明方面的东西。

问题引入

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

1+2+3+⋯+n=∑k=1nk=n(n+1)21+2+3+\cdots+n=\sum_{k=1}^nk=\dfrac{n (n+1) } {2}

1+a+a2+⋯+an−1=∑k=0n−1ak=an−1a−11+a+a^2+\cdots+a^{n-1}=\sum_{k=0}^{n-1}a^k=\dfrac{a^n-1} {a-1}

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

12+22+⋯+n2=∑k=1nk2=n(n+1)(2n+1)61^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}

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

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

裂项相消法

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

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

=(11−12)+(12−13)+(13−14)+⋯+(1n−1n+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)}

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

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

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

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

差分

Δf(x)=f(x+1)−f(x)\Delta f(x)=f(x+1)-f(x)
意思是，Δf(x)\Delta f(x) 是一个新的函数，它等于 f(x)f(x) 的差。

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

加法法则：

Δ(u+v)=Δu+ΔvΔ(u+v)=Δu+Δv\Delta (u+v)=\Delta u+\Delta vΔ(u+v)=Δu+Δv
意思是，两个函数的和的差分等于两个函数的差分的和。直接套用定义即可证明：
Δ(f(x)+g(x))=f(x+1)+g(x+1)−f(x)−g(x)\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)=Δf(x)+Δg(x)=f(x+1)-f(x)+g(x+1)-g(x)=\Delta f(x)+\Delta g(x)

减法法则：

Δ(u−v)=Δu−Δv\Delta (u-v)=\Delta u-\Delta v
同上。

Δ(Cu)=CΔu\Delta(Cu)=C\Delta u
其中 CC 为一个与 xx 无关的常数。
亦可直接套用定义证明，此处不再赘述。

乘法法则：

Δ(uv)=uΔv+EvΔu\Delta(uv)=u\Delta v+\mathrm{E}v\Delta u
其中 Ef(x)=f(x+1)\mathrm{E}f(x)=f(x+1)
证明：Δ(f(x)g(x))=f(x+1)g(x+1)−f(x)g(x)\Delta(f(x)g(x))=f(x+1)g(x+1)-f(x)g(x)
\qquad 考虑添加一个中间项 −f(x)g(x+1)+f(x)g(x+1)-f(x)g(x+1)+f(x)g(x+1)，从而转为差分的形式

=f(x+1)g(x+1)−f(x)g(x+1)+f(x)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)=(f(x+1)-f(x))g(x+1)+(g(x+1)-g(x))f(x)

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

=f(x)Δg(x)+Eg(x)Δf(x)=f(x)\Delta g(x)+\mathrm{E} g(x)\Delta f(x)

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

定和式

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

∑abf(x)δx=∑k=ab−1f(k)=f(a)+f(a+1)+f(a+2)+⋯f(b−1){\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)

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

∑abΔf(x)δx=f(b)−f(a){\sum}_a^b\Delta f(x)\delta x=f(b)-f(a)

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

∑aaf(x)δx=0,∑abf(x)δx=−∑baf(x)δx{\sum}_a^af(x)\delta x=0,{\sum}_a^bf(x)\delta x=-{\sum}_b^af(x)\delta x

∑abf(x)δx+∑bcf(x)δx=∑acf(x)δx{\sum}_a^b f(x)\delta x+{\sum}_b^cf(x)\delta x={\sum}_a^c f(x)\delta x

∑abf(x)δx±∑abg(x)δx=∑ab(f(x)±g(x))δx{\sum}_a^bf(x)\delta x \pm{\sum}_a^b g(x)\delta x={\sum}_a^b(f(x)\pm g(x))\delta x

∑abCf(x)δx=C∑abf(x)δx{\sum}_a^b Cf(x)\delta x=C{\sum}_a^b f(x)\delta x

例题 1：求解等比数列和 ∑k=0n−1ak(a≠1)\sum_{k=0}^{n-1}a^k\quad(a\not= 1)

解：首先考虑指数函数的差分
Δ(ax)=ax+1−ax=(a−1)ax\Delta(a^x)=a^{x+1}-a^x=(a-1)a^x

套用运算法则得到

ax=Δ(axa−1)a^x=\Delta{\left(\dfrac{a^x}{a-1}\right)}

因此

∑k=0n−1ak=∑0naxδx=∑0nΔ(axa−1)δx=ana−1−a0a−1=an−1a−1\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}

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

下降幂

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

Δ(xn)=(x+1)n−xn=∑k=0n−1(nk)xk\Delta(x^n)=(x+1)^n-x^n=\sum_{k=0}^{n-1}\dbinom{n}{k}x^k

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

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

xn‾={x(x−1)(x−2)⋯(x−n+1)(n>0)1(n=0)1(x+1)(x+2)⋯(x+(−n))(n<0)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}

有一个同等优美的结论：

Δ(xn‾)=(x+1)n‾−xn‾=((x+1)−(x−n+1))xn−1‾=nxn−1‾\Delta(x^{\underline{n}})=(x+1)^{\underline{n}}-x^{\underline{n}}=((x+1)-(x-n+1))x^{\underline{n-1}}=nx^{\underline{n-1}}

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

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

例题 2：求解等差数列和 ∑k=1nk\sum_{k=1}^n k

解：∑k=1nk=∑1n+1xδx=12(n+1)2‾−1212‾=n(n+1)2\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：求解 ∑k=1n1k(k+1)\sum_{k=1}^n\dfrac{1}{k(k+1)}

解：∑k=1n1k(k+1)=∑k=0n−1k−2‾=∑0nx−2‾δx=n−1‾−0−1‾−1=1−1n+1\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 求和
解：∑i=1n(∏j=ii+m−1j)−1=∑i=0n−1(∏j=i+1i+mj)−1=∑i=0n−11(i+m)m‾\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}}}

=∑0nx−m‾δx=n−m+1‾−0−m+1‾−m+1=(n+m−1)n‾−n!(m−1)(n+m−1)!={\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：求证上指标求和公式 ∑k=0n(km)=(n+1m+1)\sum_{k=0}^n\dbinom{k}{m}=\dbinom{n+1}{m+1}

证明：∑k=0n(km)=∑k=0nkm‾m!=1m!∑0n+1xm‾δx\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}

=(n+1)m+1‾−0m+1‾m!(m+1)=(n+1)m+1‾(m+1)!=(n+1m+1)=\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：求解 ∑k=1nk2\sum_{k=1}^n k^2

解：∑k=1nk2=∑k=0nk2=∑0n+1(x2‾+x)δx=13(n+1)3‾+12(n+1)2‾\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(13(n−1)+12)=(n+1)n(2n+1)6=(n+1)n{\left(\dfrac{1}{3}(n-1)+\dfrac{1}{2}\right)}=\dfrac{(n+1)n(2n+1)}{6}

例题 7：求解 $\sum_{k=1}^n k^3 $

解：∑k=1nk3=∑k=0nk3=∑0n+1(x3‾+3x2‾+x)δx\sum_{k=1}^nk^3=\sum_{k=0}^nk^3={\sum}_0^{n+1}(x^{\underline{3}}+3x^{\underline{2}}+x)\delta x

=14(n+1)4‾+(n+1)3‾+12(n+1)2‾=n2(n+1)24=\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}

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

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

xn=∑k=0n{nk}xk‾x^n=\sum_{k=0}^n{n\brace k}x^{\underline{k}}

xn‾=∑k=0n[nk](−1)n−kxkx^{\underline{n}}=\sum_{k=0}^n{n\brack k}(-1)^{n-k}x^k

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

∑i=0n−1im=∑k=0m{mk}∑i=0n−1ik‾=∑k=0m{mk}∑0nxk‾δx=∑k=0m{mk}nk+1‾k+1\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)=∑Δf(x)δx+Cf(x)=\sum\Delta f(x)\delta x+C
其中 CC 为计算完成后确定的常数。

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

∑uΔv=uv−∑EvΔu\sum u\Delta v=uv-\sum\mathrm{E}v\Delta u

使用时切记是 EvEv\mathrm{E}vEv 而非 EΔv\mathrm{E}\Delta v

例题 8：求解 ∑i=0n−1ik‾ai,a≠1,k\sum_{i=0}^{n-1} i^{\underline{k}}a^i,a\not= 1,k 较小。
解：由分部求和法则得
∑xk‾axδx=xk‾axa−1−∑ax+1a−1kxk−1‾δx\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

=xk‾axa−1−kaa−1∑axxk−1‾δx=\dfrac{x^{\underline{k}}a^x}{a-1}-\dfrac{ka}{a-1}\sum a^xx^{\underline{k-1}}\delta x

=axa−1∑i=0k(−aa−1)iki‾xk−i‾=\dfrac{a^x}{a-1}\sum_{i=0}^k{\left(\dfrac{-a}{a-1}\right)}^ik^{\underline{i}}x^{\underline{k-i}}

因此 ∑i=0n−1ik‾ai=∑0nxk‾axδx=1a−1∑i=0k(−aa−1)iki‾(annk−i‾−a00k−i‾)\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 幂

高阶差分

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

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

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

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

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

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

f(x)=∑k=0∞Δkf(x0)k!(x−x0)k‾=∑k=0∞(x−x0k)Δkf(x0)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\deg f=n，综合以上两个公式得

f(x)=∑k=0∞(xk)∑i=0k(ki)(−1)k−iEif(x0)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)=∑k=0n∑i=0k(xk)(ki)(−1)k−if(i)f(x)=\sum_{k=0}^n\sum_{i=0}^k\dbinom{x}{k}\dbinom{k}{i}(-1)^{k-i}f(i)

f(x)=∑k=0n∑i=0k(xi)(x−ik−i)(−1)k−if(i)f(x)=\sum_{k=0}^n\sum_{i=0}^k\dbinom{x}{i}\dbinom{x-i}{k-i}(-1)^{k-i}f(i)

此处使用了三项式版恒等式
调换下求和顺序

f(x)=∑i=0n(xi)f(i)∑k=in(x−ik−i)(−1)k−if(x)=\sum_{i=0}^n\dbinom{x}{i}f(i)\sum_{k=i}^n\dbinom{x-i}{k-i}(-1)^{k-i}

f(x)=∑i=0n(xi)f(i)∑k=0n−i(x−ik)(−1)kf(x)=\sum_{i=0}^n\dbinom{x}{i}f(i)\sum_{k=0}^{n-i}\dbinom{x-i}{k}(-1)^k

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

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

使用平行求和法 ∑k=0n(r+kk)=(r+n+1n)\sum_{k=0}^n\dbinom{r+k}{k}=\dbinom{r+n+1}{n}

f(x)=∑i=0n(xi)f(i)(n−i−(x−i)−1+1n−i)f(x)=\sum_{i=0}^n\dbinom{x}{i}f(i)\dbinom{n-i-(x-i)-1+1}{n-i}

f(x)=∑i=0nf(i)(xi)(n−xn−i)f(x)=\sum_{i=0}^nf(i)\dbinom{x}{i}\dbinom{n-x}{n-i}

f(x)=∑i=0nf(i)(∏j=0i−1x−ji−j)(∏j=i+1nx−ji−j)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)=∑i=0nf(i)∏j≠ix−ji−jf(x)=\sum_{i=0}^nf(i)\prod_{j\not=i}\dfrac{x-j}{i-j}

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

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

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

总结
Δf(x)=f(x+1)−f(x),∑abf(x)δx=∑k=ab−1f(k)\Delta f(x)=f(x+1)-f(x),{\sum}_a^bf(x)\delta x=\sum_{k=a}^{b-1}f(k)

∑abΔf(x)δx=f(b)−f(a){\sum}_a^b\Delta f(x)\delta x=f(b)-f(a)

Δ(ax)=(a−1)ax,Δ(xn‾)=nxn−1‾\Delta(a^x)=(a-1)a^x,\Delta(x^{\underline{n}})=nx^{\underline{n-1}}

f(x)=∑Δf(x)δx+C,∑uΔv=uv−∑EvΔuf(x)=∑Δf(x)δx+C,∑uΔv=uv−∑EvΔuΔnf=(E−1)nf=∑k=0n(nk)(−1)n−kEkff(x)=\sum\Delta f(x)\delta x+C,\sum u\Delta v=uv-\sum\mathrm{E}v\Delta u f(x)=∑Δf(x)δx+C,∑uΔv=uv−∑EvΔu \Delta^n f=(\mathrm{E}-1)^nf=\sum_{k=0}^n\binom{n}{k}(-1)^{n-k}\mathrm{E}^kf

f(x)=∑k=0∞(x−x0k)Δkf(x0)=∑i=0nf(i)(xi)(n−xn−i)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}

Hn=∑i=1n1i=ln⁡n+γ+εnH_n=\sum_{i=1}^n\dfrac{1}{i}=\ln n+\gamma+\varepsilon_n

尽管没有无限微积分那么优秀的性质，有限微积分仍能高效地处理求和问题。

从小学到高中的所有数列求和，在有限微积分中得到统一。