具体数学 第二章 和式

记号 Notation

$a_k$: term.

$\sum_{k=1}^n \underbrace{a_k}_{\mathrm{summand}}$

$\sum_{P(k)} a_k=\sum_k a_k [P(k)]$

和式和递归式 Sums and Recurrences

$S_n=\sum_{k=0}^n a_k \Leftrightarrow \begin{aligned}&S_0=a_0;\\&S_n=S_{n-1}+a_n,n>0\end{aligned}$

推导

$R_0=\alpha\\ R_n=R_{n-1}+\beta+\gamma n$

使用成套方法。

河内塔递归式

$T_0=0\\ T_n=2T_{n-1}+1,n>0$

多重和式 Multiple Sums

交换求和次序的基本法则

$\sum_j \sum_k a_{j,k} [P(j,k)]=\sum_{P(j,k)} a_{j,k}=\sum_k \sum_j a_{j,k} [P(j,k)]$

交换求和次序的变形

简易型 vanilla

$\sum_{j\in J}\sum_{k\in K} a_{j,k}=\sum_{j}\sum_{k} a_{j,k} [j\in J][k\in K]=\sum_{j\in J\, k\in K}a_{j,k}=\sum_{k\in K}\sum_{j\in J} a_{j,k}$

复杂形 rocky road

$\sum_{j\in J}\sum_{k\in K(j)} a_{j,k}=\sum_{k\in K'}\sum_{j\in J'(k)} a_{j,k}$

其中必须满足以下关系：

$[j\in J][k\in K(j)]=[k\in K'][j \in J'(k)]$

类似于高数中的 $X$ 型区域和 $Y$ 型区域。

证明：

$\sum_{j=1}^n \sum_{k=j}^n a_{j,k}=\sum_{k=1}^n \sum_{j=1}^k a_{j,k}$

因为

$[1\le j \le n][j \le k \le n]=[1\le j \le k \le n]=[1\le k\le n][1\le j \le k]$

证明：

$[1\le j < k \le n]+[1\le k < j \le n]=[1\le j,k \le n]-[1\le j=k \le n]$

得到

$S=\sum_{1\le j<k \le n} (a_k-a_j)(b_k-b_j)$

交换符号：

$2S=\sum_{1\le j<k \le n}+\sum_{1\le k<j \le n}=\sum_{1\le j \le n}\sum_{1\le k \le n} -\sum_{1\le j=k\le n}=\sum_{1\le j \le n}\sum_{1\le k \le n}$

因此，需要进行展开：

$2S=\sum_{1\le j,k \le n} a_k b_k-\sum_{1\le j,k \le n} a_j b_k-\sum_{1\le j,k \le n} a_k b_j+\sum_{1\le j,k \le n} a_j b_j\\ =2n \sum_{k=1}^n a_k b_k -2 \left(\sum_{k=1}^n a_k\right)\left(\sum_{k=1}^n b_k\right)$

得到了一个有趣的公式：

$\left(\sum_{k=1}^n a_k\right)\left(\sum_{k=1}^n b_k\right)=n\sum_{k=1}^n a_k b_k-\sum_{1\le j<k \le n} (a_k-a_j)(b_k-b_j)$

连续形式就是：

$\int_a^b f(x)\mathrm d x\int_a^b g(x)\mathrm d x=(b-a)\int_a^b f(x)g(x)\mathrm d x-\iint_D (f(x)-f(y))(g(x)-g(y))\mathrm d \sigma$

其中 $D=\{(x,y)\mid a\le y \le b,a\le x \le y\}$。

证明：

$\iint_{[a,b]\times[a,b]} f(x)g(y) \mathrm d \sigma=\iint_{[a,b]\times[a,b]} f(x)g(x)\mathrm d \sigma-\iint_D (f(x)-f(y))(g(x)-g(y))\mathrm d \sigma$

$\iint_{[a,b]\times[a,b]} f(x)(g(y)-g(x)) \mathrm d \sigma=-\iint_D (f(x)-f(y))(g(x)-g(y))\mathrm d \sigma$

交换 $x,y$ 符号，并且相加：

$\iint_{[a,b]\times[a,b]} (f(x)-f(y))(g(y)-g(x))\mathrm d \sigma=-\iint_{[a,b]\times[a,b]}(f(x)-f(y))(g(x)-g(y))\mathrm d \sigma$

得证！思想方法和和式差不多。

证明 Lagrange 恒等式：

$\sum_{1 \le j < k \le n}(a_jb_k - a_kb_j)^2=\left(\sum_{k=1}^n a_k^2\right)\left(\sum_{k=1}^n b_k^2\right)-\left(\sum_{k=1}^n a_kb_k\right)^2$

其积分形式：

$\iint_D (f(x)g(y)-f(y)g(x))^2=\int_a^b f^2(x)\mathrm d x\int_a^b g^2(x)\mathrm d x-\left(\int_a^b f(x)g(x)\mathrm d x\right)^2$

其中 $D=\{(x,y)\mid a\le y \le b,a\le x \le y\}$。

$\iint_{[a,b]\times[a,b]} f^2(x)g^2(y)\mathrm d \sigma-\iint_{[a,b]\times[a,b]} f(x)g(x)f(y)g(y)\mathrm d \sigma\\ =\iint_{[a,b]\times[a,b]}f(x)g(y)[f(x)g(y)-g(x)f(y)]\mathrm d \sigma$

然后交换 $x,y$ 可证。

和式证明：

原式展开得到

$\sum_{1\le j<k \le n}a_j^2 b_k^2+a_k^2 b_j^2-2a_ja_kb_jb_k$

前两项就是

$\sum_{1\le j\not=k <n} a_j^2 b_k^2$

后面使用 $[1\le j < k \le n]+[1\le k < j \le n]=[1\le j,k \le n]-[1\le j=k \le n]$ 展开，得到

$-\sum_{1\le j,k \le n} a_ja_kb_jb_k+\sum_{1\le j=k \le n}a_j a_kb_jb_k=-\left(\sum_{k=1}^n a_kb_k\right)^2+\sum_{1\le j=k <n} a_j^2 b_k^2$

合并后拆分，得到原式。

排列和求和

计算 $S_n=\sum_{1\le j <k \le n} \frac{1}{k-j}$。

等于

$\sum_{d=1}^{n-1} d\cdot \frac{1}{n-d}=\sum_{d=1}^{n-1}\frac{n}{n-d}-1=-(n-1)+n\sum_{d=0}^{n-1}\frac{1}{n-d}-1=nH_n-n$

一般性的方法 General Methods

有限微积分 Finite Calculus

类比积分，我们需要引入有限微积分和无限微积分的概念。

无限微积分（微分算子 D）

$\mathrm{D} f(x)=\lim_{h\to 0} \frac{f(x+h)-f(x)}{h}$

有限微积分（差分算子 $\Delta$）

$\Delta f(x)=\frac{f(x+1)-f(x)}{1}=f(x+1)-f(x)$

两者对比

众所周知：

$\mathrm{D} x^m=mx^{m-1}$

而对于有限微积分，有没有类似的结论？

事实上，引入 $x^{\underline{m}}$，称为下降阶乘幂，其定义是：

$x^{\underline{m}}=x(x-1)\cdots(x-m+1)$

则，$\Delta(x^{\underline{m}})=x(x-1)\cdots(x-m+1)-(x-1)\cdots(x-m)=mx^{\underline{m-1}}$，结论与上面类似。

运用到积分

设 $\sum_a^b g(x)\delta x=f(b)-f(a)$，其中 $\Delta f(x)=g(x)$，则由定义我们推出 $\sum_{a}^b g(x)\delta x= \sum_{a\le x <b} g(x)$。

注：这里的 $\delta$ 是 $\Delta$ 的小写，类比 $\mathrm{d}$ 是 $\mathrm{D}$ 的小写。

可以试着代入 $g(x)=x^{\underline{m}}$，则 $f(x)=\frac{x^{\underline{m+1}}}{m+1}$，则：

$\sum_{0 \le k <n}k^{\underline{m}}=f(n)-f(0)=\frac{n^{\underline{m+1}}}{m+1}$

于是我们可以试着用待定系数法（或者多项式除法）来求解 $\sum_{0\le k <n} k^a$，其中 $a$ 是正整数。

函数乘积的差分

已知 $\Delta u(x),\Delta v(x),u(x),v(x)$，求 $\Delta(u(x)v(x))$。

由定义，我们有：

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

或者写成不对称的形式：

$u(x)\Delta v(x)+v(x+1)\Delta u(x)$

分部积分

回顾无限微积分下分部积分的法则：

$\int u\mathrm{d}v=uv-\int v\mathrm{d}u$

我们令 $\mathrm{E}$ 为移位算子，具体地，$\mathrm{E} v(x)=v(x+1)$，则有类似的法则：

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

如果我们想要求 $\sum k2^k$，则：

$\begin{aligned} &\sum x2^x\delta x \quad (u=x,\Delta v=2^{x} \Rightarrow \Delta u=1,v=2^x)\\ =&x2^x-\sum \mathrm{E} 2^{x} \delta x=x2^x-2^{x+1}+C \end{aligned}$

则 $\sum_{k=0}^n k2^k=\sum_{0}^{n+1} x2^x \delta x=x2^x-2^{x+1}|_0^{n+1}=(n-1)2^{n+1}+2$。