具体数学内容总结——第2章 和式

书籍介绍：

https://book.douban.com/subject/21323941/

github仓库：

https://github.com/Doraemonzzz/Concrete-Mathematics

这次先回顾第2章——和式。

递归式求解

考虑递归式

$$a_{n} T_{n}=b_{n} T_{n-1}+c_{n}$$

思路是两边同乘$s_n$，得到

$$s_{n} a_{n} T_{n}=s_{n} b_{n} T_{n-1}+s_{n} c_{n}$$

$s_n$满足

$$s_{n} b_{n}=s_{n-1} a_{n-1}$$

记

$$S_{n}=s_{n} a_{n} T_{n}$$

那么

$$\begin{aligned} S_{n}&=S_{n-1}+s_{n} c_{n}\\ S_{n}&=s_{0} a_{0} T_{0}+\sum_{k=1}^{n} s_{k} c_{k}\\ &=s_{1} b_{1} T_{0}+\sum_{k=1}^{n} s_{k} c_{k}\\ T_n&=\frac{1}{s_{n} a_{n}}\left(s_{1} b_{1} T_{0}+\sum_{k=1}^{n} s_{k} c_{k}\right) \end{aligned}$$

最后一步是求解$s_n$，这一点如下关系即可

$$s_{n}=\frac{s_{n-1} a_{n-1}}{ b_{n}}$$

最后得到

$$s_{n}=k\times \frac{a_{n-1} a_{n-2} \cdots a_{1}}{b_{n} b_{n-1} \cdots b_{2}}$$

例子见24页。

扰动法

假设我们要求解和式

$$S_{n}=\sum_{0 \le k \le n} a_{k}$$

一种方法如下：

$$\begin{aligned} S_{n}+a_{n+1} &=\sum_{0 \le k \le n+1} a_{k} \\ &=a_{0}+\sum_{1 \le k \le n+1} a_{k} \\ &=a_{0}+\sum_{1 \le k+1 \le n+1} a_{k+1} \\ &=a_{0}+\sum_{0 \le k \le n} a_{k+1} \end{aligned}$$

然后尝试将$\sum_{0 \le k \le n} a_{k+1}$用$S_n$表达出来，求解方程即可。

例子见27页。

平方和公式的多种推导方法

见35页。

有限微积分

差分算子

差分算子$\Delta$：

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

下降阶乘幂：

$$\begin{aligned} x^{\underline m}&=\overbrace{x(x-1) \cdots(x-m+1)}^{m \text {个因子 }}, \quad \text { 整数 } m \ge 0\\ x^{\underline{-m}}&=\frac{1}{(x+1)(x+2) \cdots(x+m)}, \quad m>0 \end{aligned}$$

上升阶乘幂：

$$\begin{aligned} x^{\overline m}&=\overbrace{x(x+1) \cdots(x+m-1)}^{m \text {个因子 }}, \quad \text { 整数 } m \ge 0 \\ x^{\overline{-m}}&=\frac{1}{(x-1)(x-2) \cdots(x-m)}, \quad m>0 \end{aligned}$$

性质：

$$\begin{aligned} x^{\underline{m+n}}&=x^{\underline{m}}(x-m)^\underline, \quad m \text { 和 } n \text { 是整数. }\\ x^{\overline {m+n}}&=x^{\overline m}(x+m)^{\overline n}, \quad m \text { 和 } n \text { 是整数. } \end{aligned}$$

特殊情形：

$$n !=n^{\underline n}=1^{\overline {n}}$$

性质：

$$\Delta\left(x^{m}\right)=m x^{m-1}$$

逆差分算子

逆差分算子也称为求和算子，记号为$\Sigma$：

$$g(x)=\Delta f(x) \text { 当且仅当 } \sum g(x) \delta x=f(x)+C$$

和式

基本定义

$$\sum_{a}^{b} g(x) \delta x=\begin{cases} \sum_{k=a}^{b-1} g(k)=\sum_{a \leq k<b} g(k) & b\ge a\\ -\sum_{b}^{a} g(x) \delta x & b<a \end{cases}$$

如果$g(x)=\Delta f(x)$，那么

$$\sum_{a}^{b} g(x) \delta x=\left.f(x)\right|_{a} ^{b}=f(b)-f(a)$$

分部求和

定义移位算子：

$$\mathrm E f(x)=f(x+1)$$

那么：

$$\begin{aligned} \Delta(u v)&=u \Delta v+\mathrm{E} v \Delta u\\ \sum u \Delta v&=u v-\sum \mathrm E v \Delta u\\ \sum_{k=1}^n u(k) \Delta v(k)&=u(n+1) v(n+1)-u(1)v(1)-\sum_{k=1}^n \mathrm{E} v(k) \Delta u(k) \end{aligned}$$

应用

$$\sum_{a}^{b} x^{m} \delta x=\left\{\begin{array}{ll} \left.\frac{x^{m+1}}{m+1}\right|_{a} ^{b}, & m \neq-1, \\ \left.H_{x}\right|_{a} ^{b}, & m=-1 . \end{array}\right.$$

其余应用见46页。