递归式与和式

发表于 2024-10-05 更新于 2025-04-15 分类于具体数学 Waline：

汉诺塔问题
递归式的封闭形式
约瑟夫问题
- Example(《具体数学》1.15)
- Solution
和式
- 和式的基本运算
- 和式的封闭形式

汉诺塔问题

三个柱子,$n$个面积互不相等的有孔圆盘一开始按照面积从上往下以此增大的顺序套在其中一个柱子上.

现在每次可以将某根柱子顶端的圆盘移动到另一根柱子顶端,要求这根柱子原本没有圆盘或者柱子顶端圆盘面积大于该圆盘.

求最小移动次数,使得所有圆盘移动到另一根柱子上.

不妨令$T_n$表示答案,显然$T_0=0,T_1=1$.

而我们一定可以找到一种方案,使得前$n-1$个圆盘先移动到其中一根柱子上,然后将最下面的圆盘移动到目标柱子,最后再把$n-1$个圆盘移动到目标柱子.由于这是一个可行解而不一定是最优解,我们有:$T_n\leq 2T_{n-1}+1$.

而如果我们要移动最大的圆盘,一定要保证前n-1个圆盘已经移走到一根柱子上.因此一定有:$2T_{n-1}+1\leq T_n$.于是有$T_n=2T_{n-1}+1$.

Example1(《具体数学》1.2)

汉诺塔问题,所有圆盘一开始均在最左边的塔A上,要将他们全都移动到最右边的塔C上,不允许在二塔之间直接移动,求最小操作次数.

Solution 1

考虑设$ T_n$为n个圆盘时的最小操作次数.假设已知$T_{n-1}$,我们考虑如何移动.

首先因为不能直接在AC之间移动,因此一定是先要把最大的圆盘移动到中间塔上,这一步要求先把所有圆盘移动到C上,然后需要再把这些圆盘移动回A上,因此,显然有:$T_{n}=3T_{n-1}+2,T_0=0$.

考虑如何求该式子的封闭形式,令$W_n=T_n+1$,显然有$W_n=3W_{n-1},W_0=1$,显然$W_n=3^n$,有$T_n=3^n-1$.

注意到$T_n$刚好是三根柱子上所有合法排列的数量,并且这个过程中不可能出现某两个时刻的情况是相同的,因此1.3也可以证明.

Example2(《具体数学》1.4)

汉诺塔问题,问是否存在一种符合规则的初始摆放方式,使得将其全部移动到其中一根柱子所用次数小于等于$2^n-1$.

Solution 2

不存在.

证明方式类似原初问题的证明,考虑最大的那个圆盘是否到达终点.如果到达则可以去掉它,用数学归纳证明不存在;如果还未到达,同样用数学归纳得到不等式.

Example3(《具体数学》1.10)

汉诺塔问题,但是移动圆盘时只能从A移动到B,从B移动到C,从C移动到A.一开始所有圆盘都在A,求将它们全部移动到B的最小操作次数,以及将他们从B移动回A的最小操作次数.

Solution 3

令$Q_n$为将n个圆盘从A移动到B的最小操作次数,令$R_n$为将n个圆盘从B移动回A的最小操作次数.

先考虑边界情况,$Q_0=0,R_0=0$.

我们考虑,由于柱子间在移动过程中是无区别的,因此$Q_n$的实质是将n个圆盘移动到它的下一个柱子的最小操作次数,$R_n$的实质是将n个圆盘移动到它的上一个柱子的最小操作次数.

在将最大的圆盘移动到下一根柱子前,一定要先把上面的圆盘全部移动到上一根柱子上,最后再移动回来.

显然有$Q_n=2R_{n-1}+1,1\leq n$.

在将最大的圆盘移动到上一根柱子前,一定要先把他移动到下一根柱子上,这个步骤要求我们把其他的圆盘移动到上一根柱子上.在这之后,我们又要把所有圆盘放到上一根柱子上来让最大圆盘到目标柱子,最后再移动回来.

有$R_n=R_{n-1}+1+Q_{n-1}+1+R_{n-1}=Q_n+Q_{n-1}+1,1\leq n$.

Example4(《具体数学》1.11)

汉诺塔问题,但是每种大小的圆盘有两个,且其中一个可以摆放在另一个的上面.

a.如果相同圆盘无区别,求最小操作次数.

b.如果相同圆盘有区别,且最后需要还原原本二者的上下顺序,求最小操作次数.

Solution 4

a.仍然令$T_n$为n对圆盘的最小操作次数,显然$T_n=2T_{n-1}+2,T_0=0$,可解得$T_n=2^{n+1}-2$.

b.令$Q_n$为n对圆盘的最小操作次数,观察a问题,我们可以发现a问题转移之后,只有最下面的两个圆盘会交换顺序.而如果我们在b问题中只关注最下层两个圆盘的顺序,我们发现$Q_n=T_{n-1}+1+T_{n-1}+1+T_{n-1}+1+T_{n-1}=4T_{n-1}+3=2^{n+2}-5$.

我们进行了四次a操作,那么次下面两个圆盘自然就顺序与原本相同了,因此这里的$Q_n$就是答案.

Example5(《具体数学》1.12)

类似Problem11,但第$i$大的圆盘有$k_i$个.

Solution 5

无区别,只是$T_n=2T_{n-1}+k_n,T_0=0$.

如果求封闭形式的话,显然有$T_n=\sum_{i=1}^n2^{n-i}k_i$.

递归式的封闭形式

在上述问题中，我们已经有了以下式子：

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

如果$n$很大，那么一步一步去计算是很复杂的，现在我们想知道一种更为快速的求出$T_n$的方法.

换句话说，我们想要把$T_n$表示为只与n有关的式子，我们称其为该递归式的封闭形式.

寻找循环节

Example(《具体数学》1.8)

解递归式:$Q_n=\begin{cases}\alpha&n=0\\\beta&n=1\\\frac{(1+Q_{n-1})} {Q_{n-2}}&n>1\end{cases}$,保证$\forall n,Q_n>0$.

Solution

注意到$Q_2=\frac{\beta+1}{\alpha},Q_3=\frac{\beta+\alpha+1}{\beta\alpha},Q_4=\frac{1+\alpha}{\beta},Q_5=\alpha,Q_6=\beta$.

显然该递归式存在长度为$5$的循环节.

数学归纳法

观察T序列的前几项，可以发现似乎有$T_n=2^n-1$.

现在我们来证明它：

1.该公式对于$n=0$成立，显然可验证.

2.若该公式对$n=k$时成立，那该公式必然对$n=k+1$成立.

因为有$T_{k+1}=2T_k+1=2\times 2^k+2-1=2^{k+1}-1$.

以上过程被称为数学归纳法.

Example(《具体数学》1.9)

求证:$\prod_{i=1}^nx_i\leq (\frac{\sum_{i=1}^nx_i}{n})^n,\forall i\in N_+,1\leq i\leq n,0\leq x_i$.

Solution

使用反向归纳法.

1.$n=2$时,即基本不等式,显然成立.

2.若该式子对$n=k$时成立,则该式子对n=2k时也成立.

不妨令$A_1=\sqrt[k]{\prod _{i=1}^k x_i},B_1=\sqrt[k]{\prod _{i=k+1}^{2k}x_i},A_2=(\frac{\sum_{i=1}^kx_i}{k}),B_2=(\frac{\sum_{i=k+1}^{2k}x_i}k)$,显然有$A_1\leq A_2,B_1\leq B_2$.

同时有$(\frac{A_2+B_2}{2})\geq \sqrt{A_2B_2}\geq \sqrt{A_1B_1}$.

3.若该式子对$n=k$时成立,则该式子对$n=k-1$的时候也成立.

令$x_k=\frac{\sum_{i=1}^{k-1}x_i}{k-1}$,有$x_k\prod_{i=1}^{k-1}x_i\leq (x_k)^k$.

则显然$n=k-1$时也成立.

由1和2,我们知道了对于n是二的整数次幂的情况,该公式成立,由3,我们又可以知道该公式对于任意一个存在比他大的二的整数次幂的数成立,因此该公式成立.

换元

考虑令$U_n=T_n+1$,显然有:$T_n+1=2T_{n-1}+2$.即$U_n=2U_{n-1}$,显然$U_n=2^n$,则$T_n=2^n-1$.

这个做法可以做掉所有形如$a_{n+1}=pa_n+q$的递归式.我们有: \[ a_{n+1}+\frac{q}{p-1}=p(a_n+\frac{q}{p-1}) \] 换元做掉这个式子.

转化和式

考虑递归式$a_nT_n=b_nT_{n-1}+c_n$.如果我们能找到一个不为0的求和因子$s_n$并满足$s_nb_n=s_{n-1}a_{n-1}$.那么我们两面同时乘以$s_n$,显然有：$s_na_nT_n=s_{n-1}a_{n-1}T_{n-1}+c_ns_n$.

令$S_n=s_na_nT_n$.显然有$S_n=s_0a_0T_0+\sum_{i=1}^ns_ic_i$,则$T_n=\frac{S_n}{s_na_n}$.

而我们也会发现$s_n=\frac{\prod_{i=1}^{n-1}a_i}{\prod_{i=1}^nb_i}$.

Example1(快速排序时间复杂度)

结论:排序$n$个数时,其期望复杂度满足: \[ C_n=\begin{cases}0&n=0,1\\n+1+\frac{2}{n}\sum_{i=0}^{n-1}C_k&n>1\end{cases} \] 不妨考虑两边同时乘以$n$,有 $ nC_n=n^2+n+2_{i=0}^{n-1}C_i,n>1 $ .

显然也有$(n-1)C_{n-1}=(n-1)^2+n-1+2\sum_{i=0}^{n-2}C_i,n>2$.

二式相消,有$nC_n-(n-1)C_{n-1}=2n+2C_{n-1},n>2$.

而同时有$C_2=3$.即:$nC_n=(n+1)C_{n-1}+2n,n>2$,可以使用转化和式的方法,两边乘以$\frac{1}{n(n+1)}$解决.

Example2

已知$a_1=1$,$a_n=\sqrt{S_n}+\sqrt{S_{n-1}}$,求$a_n$.

注意到$a_n=S_n-S_{n-1}$,则有$\sqrt{S_n}-\sqrt{S_{n-1}}=1$,于是$\sqrt{S_n}=n$,$S_n=n^2$,$a_n=2n-1$.

成套方法

如果我们有 $f(n)=\begin{cases} \alpha & n=1\\ 2f(\frac n 2)+\beta & n=2k,k\in \mathbb{N_+}\\ 2f(\frac {n-1}2)+\gamma &n=2k+1,k\in \mathbb{N_+} \end{cases}$

其中$n=2^m+l$且$2^m\leq n<2^{m+1}$.

该如何求出$f(n)$的封闭形式呢?

由于所有的未知数都是以加法运算连接,显然有$f(n)=A(n)\alpha+B(n)\beta+C(n)\gamma$,而有$A、B、C$互不影响且$\alpha\beta\gamma$与$ABC$无关.

那无论$\beta$和$\gamma$的取值如何,$A(n)$都不会受到影响,我们考虑$\beta=\gamma=0$的特殊情况,此时显然有$A(n)=2^m$.

接下来,我们考虑取$\alpha\beta\gamma$的特殊值,去得到ABC之间的关系.

例如，当$f(n)=1$时，由递推式可知$\alpha=1,\beta=\gamma=-1$,那么有$A(n)-B(n)-C(n)=f(n)=1$.

同理，$f(n)=n$时，可知$\alpha=1,\beta=0,\gamma=1$,此时有$A(n)+C(n)=f(n)=n$.

显然可以通过解方程求得$B(n)$和$C(n)$.

这个方法显然是通用方法,式子仅仅是例子,事实上,只要我们能证明$ABC$互不影响且$\alpha\beta\gamma$与$ABC$无关,我们就可以使用这个方法.

这个东西的原理是什么呢?显然是因为其中存在一个线性无关性对吧.

线性递推

一个常系数的$k$阶线性递推关系形如: \[ a_n=P_n+\sum_{i=1}^kc_ia_{n-i},n\geq k\\ a_0=C_0,a_1=C_1,...,a_{k-1}=C_{k-1} \]

当$P=0$时,称作齐次线性递推.

特征方程

我们称方程$r^k=\sum_{i=1}^kc_ir^{k-i}$是该递推关系的特征方程,方程的解叫做该递推关系的特征根.

二阶线性齐次递推

若其特征方程有两个不同的根$r_1$和$r_2$,那么存在两个常数$\alpha_1$和$\alpha_2$,满足$a_n=\alpha_1r_1^n+\alpha_2r_2^n$.

若其特征方程有两个相同的根$r$,那么存在两个常数$\alpha_1$和$\alpha_2$,满足$a_n=\alpha_1r^n+\alpha_2nr^n$.

先考虑前者的证明,首先考虑对于$n=0$或者$n=1$的情况,我们考虑求出一组$\alpha_1$和$\alpha_2$来满足: \[ C_0=\alpha_1+\alpha_2\\ C_1=\alpha_1r_1+\alpha_2r_2 \] 若$r_1\ne r_2$,可以解得: \[ \alpha_1=\cfrac{C_1-C_0r_2}{r_1-r_2}\\ \alpha_2=C_0-\alpha_1 \] 接下来考虑数学归纳: \[ a_n=c_1a_{n-1}+c_2a_{n-2}\\ =c_1(\alpha_1r_1^{n-1}+\alpha_2r_2^{n-1})+c_2(\alpha_1r_1^{n-2}+\alpha_2r_2^{n-2})\\ =\alpha_1(c_1r_1^{n-1}+c_2r_1^{n-2})+\alpha_2(c_1r_2^{n-1}+c_2r_2^{n-2})\\ =\alpha_1r_1^n+\alpha_2r_2^n \] 接下来考虑后者,首先我们有$\Delta=c_1^2+4c_2=0$,考虑初始条件: \[ C_0=\alpha_1\\ C_1=\alpha_1r+\alpha_2r\\ \] 接下来我们考虑数学归纳: \[ a_n=c_1a_{n-1}+c_2a_{n-2}\\ =c_1(\alpha_1r^{n-1}+\alpha_2nr^{n-1}-\alpha_2r^{n-1})+c_2(\alpha_1r^{n-2}+\alpha_2nr^{n-2}-2\alpha_2r^{n-2})\\ =a_n-c_1\alpha_2r^{n-1}-2c_2\alpha_2r^{n-2} \] 我们接下来只需证明$c_1r+2c_2=0$即可.根据方程,不难发现$r=\cfrac{c_1}{2}$,根据$\Delta=0$,自然得证.

更一般的情况

直接在复数域上定义$f_k(x)=\{n^kx^n\}_{n=0}^\infty$,此时我们规定$0^0=1$.特别地,当$x=0$的时候,定义$f_k(x)$的第$k$项是$1$,其余项是$0$.在此基础上定义线性映射$T:(a_n)_{n=0}^\infty\mapsto (a_{n+1})_{n=0}^\infty$,立刻见到:$(T-x)^{k+1}f_k(x)=0,(T-x)^kf_k(x)\ne 0$.原因只需简单数学归纳.而此还可以引出$f_0(x),f_1(x),\cdots$线性无关.

在此基础上观察线性递推$a_{n+d}=c_{d-1}a_{n+d-1}+\cdots+c_0a_n$,不妨取$G(x)=x^d-c_{d-1}x^{d-1}-\cdots-c_0$,立刻应当见到如果$a$是$G$的根并且重数为$e(a)$,那么$f_{0}(x),\cdots,f_{e(a)-1}(a)$都在$\ker f(T)$中.这恰好是该线性递推空间的维数个.我们需要说明它们线性无关,不妨反证,假设出现了形如$\sum_j w_if_i(y)=\sum_j w_jf_j(x)$的情况,此时对右边直接操作若干次$(T-x)$就可以把右边全部消成$0$,在对着左边消几次就可以使得左边只留下最高次项,这个时候发现最高次项是消不掉的,原因是将每一个位置看作关于$n$的多项式右边的$(T-x)$是不会改变左边这边的每一个位置多项式的$\deg$,这当然意味着不可能消干净.

再再进一步

我们都知道矩阵加速:也就是$\vec x_{k+1}=A\vec x$,$\vec x_{n}=A^n\vec x_0$.而我们又知道CH定理:$p(A)=0$,我们用多项式取膜,有$A^n=p(A)F(A)+G(A)=G(A)$,这就是解.

约瑟夫问题

考虑n个人围成一圈,从第一个人开始,每隔一个人就杀掉一个人.如10个人围成一圈时,杀人的顺序是$2,4,6,8,10,3,7,1,9$.问最后幸存下来的人编号.

首先一定有J(1)=1.考虑第一遍杀掉n号或者n-1号之后,对整个圆圈进行重新编号.

那么当人数是偶数时,我们有$J(2n)=2J(n)-1$;当人数是奇数时,我们杀掉一号,然后有$J(2n+1)=2J(n)+1$.

整理得到: \[ J(n)=\begin{cases} 1 & n=1\\ 2J(\frac n 2)-1 & n=2k,k\in \mathbb{N_+}\\ 2J(\frac {n-1}2)+1 &n=2k+1,k\in \mathbb{N_+} \end{cases} \] 仍然可以使用数学归纳，如果令$n=2^m+l且2^m\leq n<2^{m+1}$. 有$J(n)=2l+1$.

要是注意力没有那么集中怎么办呢?考虑到这个东西显然和取膜有着不可分割的关系,我们不妨从$0$开始编号: \[ J(n)=\begin{cases} 0 & n=1\\ 2J(\frac n 2) & n=2k,k\in \mathbb{N_+}\\ 2J(\frac {n-1}2)+2 &n=2k+1,k\in \mathbb{N_+} \end{cases} \] 这下相信$J(n)$是多少就很显然了,将$n$写成二进制的形式,这个就相当于把首位$1$抹去然后在末尾加个$0$.

Example(《具体数学》1.15)

求约瑟夫问题中最后一名被杀死的人的编号.

Solution

显然有: \[ J(n)=\begin{cases} 2 & n=2\\ 1&n=3\\ 2J(\frac n 2)-1 & n=2k+2,k\in \mathbb{N_+}\\ 2J(\frac {n-1}2)+1 &n=2k+3,k\in \mathbb{N_+} \end{cases} \] 从$0$开始编号,自然有: \[ J(n)=\begin{cases} 1 & n=2\\ 0&n=3\\ 2J(\frac n 2) & n=2k+2,k\in \mathbb{N_+}\\ 2J(\frac {n-1}2)+2 &n=2k+3,k\in \mathbb{N_+} \end{cases} \] 显然$J(n)$也可以用二进制表达其形式.

和式

和式的基本运算

分配律: \[ \sum_{i\in S}ca_i=c\sum_{i\in S}a_i \] 一般分配律: \[ \sum_{i}\sum_{j}a_{i}b_j=(\sum_{i}a_i)(\sum_jb_j) \] 结合律: \[ \sum_{i\in S}(a_i+b_i)=\sum_{i\in S}a_i+\sum_{i\in S}b_i \] 交换律: \[ \sum_{i\in S}a_i=\sum_{p(i)\in S}a_{p(i)} \] 交换求和顺序:

\[ \sum_{i}\sum_{j}a_{i,j}[P(i,j)]=\sum_{j}\sum_{i}a_{i,j}[P(i,j)]\\ \sum_{i=1}^n\sum_{j=i}^na_{i,j}=\sum_{j=1}^n\sum_{i=1}^ja_{i,j} \]

和式的封闭形式

交换顺序法

Example1(等差数列求和)

我们有: \[ S_n=\sum_{i=0}^n(ai+b)=\sum_{i=0}^n(a(n-i)+b)\\ 2S_n=\sum_{i=0}^n(an+2b)=an(n+1)+2b(n+1)\\ S_n=(n+1)(\frac{an}{2}+b) \]

Example2(切比雪夫单调不等式)

令$S=\sum_{1\leq i<j\leq n}(a_j-a_i)(b_j-b_i)=\sum_{1\leq j<i\leq n}(a_j-a_i)(b_j-b_i)$.

考虑恒等式$[1\leq j<i\leq n]+[1\leq i<j\leq n]=[1\leq j,i\leq n]-[1\leq i=j\leq n]$.

那么我们有:

\[ 2S=\sum_{1\leq i,j\leq n}(a_j-a_i)(b_j-b_i)-\sum_{1\leq i=j\leq n}(a_j-a_i)(b_j-b_i)\\=\sum_{1\leq i,j\leq n}(a_j-a_i)(b_j-b_i)\\ =2n\sum_{i=1}^na_ib_i-2(\sum_{i=1}^na_i)(\sum_{j=1}^nb_j)\\ (\sum_{i=1}^na_i)(\sum_{j=1}^nb_j)=n\sum_{i=1}^na_ib_i-\sum_{1\leq i<j\leq n}(a_j-a_i)(b_j-b_i) \] 显然有以下式子:

$(\sum_{i=1}^na_i)(\sum_{j=1}^nb_j)\leq n\sum_{i=1}^na_ib_i，\forall i<j，a_i\leq a_j且b_i\leq b_j\\ (\sum_{i=1}^na_i)(\sum_{j=1}^nb_j)\geq n\sum_{i=1}^na_ib_i，\forall i<j，a_i\leq a_j且b_i\geq b_j\\$

上式被称为切比雪夫单调不等式.

值得一提的是,切比雪夫单调不等式其实是排序不等式的一个特化版本.

Example3(拉格朗日恒等式)

证明: \[ \sum_{1\leq j<k\leq n}(a_jb_k-a_kb_j)^2=(\sum_{i=1}^na_i^2)(\sum_{i=1}^nb_i^2)-(\sum_{i=1}^na_ib_i)^2\\ \] 有: \[ S_n=\sum_{1\leq j<k\leq n}(a_jb_k-a_kb_j)^2\\ 2S_n=\sum_{j=1}^n\sum_{k=1}^n(a_jb_k-a_kb_j)^2\\ =\sum_{j=1}^n\sum_{k=1}^n(a_j^2b_k^2-2a_ja_kb_jb_k+a_k^2b_j^2)\\ =2(\sum_{i=1}^na_i^2)(\sum_{i=1}^nb_i^2)-2(\sum_{i=1}^na_ib_i)^2 \]

扰动法

Example1(等比数列求和)

\[ S_n=\sum_{i=0}^nax^i\\=a+\sum_{i=1}^nax^i\\=a+x\sum_{i=0}^{n-1}ax^i\\=a+xS_{n-1} \]

而$S_{n-1}+ax^n=S_n=a+xS_{n-1}$,有$S_n+ax^{n+1}=a+xS_n,S_n=a\frac{x^{n+1}-1}{x-1}$，其中$x\ne1$.

Example2(平方和公式)

如果直接对该公式使用扰动法:

\[ S_n=\sum_{i=0}^ni^2=\sum_{i=0}^{n-1}i^2+n^2\\=\sum_{i=1}^n(i-1)^2+n^2\\=S_n-2\sum_{i=1}^ni+n+n^2 \] 我们无法得到$S_n$的封闭形式,但我们发现我们得到了$\sum_{i=1}^ni$的封闭形式.

那以此类推,我们设$W_n=\sum_{i=0}i^3$.

\[ W_n=\sum_{i=0}^{n-1}i^3+n^3\\=\sum_{i=1}^n(i-1)^3+n^3\\=\sum_{i=1}^ni^3-3\sum_{i=1}^ni^2+3\sum_{i=1}^ni-n+n^3\\=W_n-3S_n+3\frac{n+n^2}2-n+n^3\\ S_n=\frac{n+n^2}2-\frac{n-n^3}3\\=\frac{n+3n^2+2n^3}6\\=\frac{n(1+3n+2n^2)}{6}\\=\frac{n(2n+1)(n+1)}{6} \]

Example3(《具体数学》2.20)

令$H_n=\sum_{k=1}^n\frac{1}{k}$,求$\sum_{i=0}^nH_i$.

Solution3

不妨考虑$\sum_{i=0}^niH_{i}$的值.

\[ \sum_{i=0}^niH_{i}=\sum_{i=1}^n[(i-1+1)H_{i-1}+1]\\=n+\sum_{i=0}^{n-1}H_i+\sum_{i=0}^{n}iH_i-nH_n\\ \sum_{i=0}^{n-1}H_i=n(H_n-1)\\ \sum_{i=0}^nH_i=(n+1)(H_{n+1}-1)\\ \]

Example4(《具体数学》2.21)

求$S_n=\sum_{i=0}^n(-1)^{n-i},T_n=\sum_{i=0}^n(-1)^{n-i}i,U_n=\sum_{i=0}^n(-1)^{n-i}i^2$.

Solution 4

\[ S_n=\sum_{i=1}^{n}(-1)^{n-i}+(-1)^n\\-S_{n-1}+1=(-1)^n+\sum_{i=0}^{n-1}(-1)^{n-1-i}\\-S_{n-1}+1=(-1)^n+S_{n-1}\\S_{n-1}=\frac{1-(-1)^n}{2}\\S_n=\frac{1+(-1)^n}{2} \]

\[ T_{n}=\sum_{i=1}^n(-1)^{n-i}i\\-T_{n-1}+n=\sum_{i=1}^n(-1)^{n-i}(i-1)+\sum_{i=1}^n(-1)^{n-i}\\-T_{n-1}+n=\sum_{i=0}^{n-1}(-1)^{n-i-1}i+\sum_{i=0}^n(-1)^{n-i}-(-1)^n\\-T_{n-1}+n=T_{n-1}+S_n-(-1)^n\\n-\frac{1-(-1)^n}2=2T_{n-1}\\T_n=\frac{1}{2}(n+1+\frac{-1-(-1)^n}2)=\frac{1}{2}(n+\frac{1-(-1)^n}2) \]

\[ U_n=\sum_{i=1}^n(-1)^{n-i}i^2\\-U_{n-1}+n^2=\sum_{i=1}^n(-1)^{n-i}(i-1+1)^2\\-U_{n-1}+n^2=\sum_{i=1}^n(-1)^{n-i}(i-1)^2+2\sum_{i=1}^n(-1)^{n-i}(i-1)+\sum_{i=1}^n(-1)^{n-i}\\-U_{n-1}+n^2=\sum_{i=0}^{n-1}(-1)^{n-i-1}i^2+2\sum_{i=0}^{n-1}(-1)^{n-i-1}i+\sum_{i=0}^{n-1}(-1)^{n-i-1}\\-U_{n-1}+n^2=U_{n-1}+2T_{n-1}+S_{n-1}\\2U_{n-1}=n^2-2T_{n-1}-S_{n-1}\\2U_{n-1}=n^2-(n-\frac{1-(-1)^n}2)-\frac{1-(-1)^n}{2}\\2U_{n-1}=n^2-n\\U_n=\frac{n(n+1)}{2} \]

转化为递归式

考虑和式$S_n=\sum_{i=0}^nf(i)=S_{n-1}+f(n)\\$，显然是递归式形式.

因此递归式所可以使用的方法同样可以在和式中使用.

Example1(《具体数学》2.13)

求$\sum_{i=0}^n(-1)^ii^2\\$.

Solution1

令$S(n)=\sum_{i=0}^n(-1)^ii^2=S(n-1)+(-1)^nn^2$,考虑使用成套方法.

不妨令$S(n)=S(n-1)+(-1)^n(\alpha+\beta n+\gamma n^2)=\alpha A(n)+\beta B(n)+\gamma C(n)$.

令$S(n)=(-1)^nn,可以解得\alpha=-1,\beta=2,\gamma=0$,有$(-1)^nn=-A(n)+2B(n)$.

令$S(n)=(-1)^nn^2,可以解得\alpha=1,\beta=-2,\gamma=2$,有$(-1)^nn^2=A(n)-2B(n)+2C(n)$.

显然可解得$2C(n)=(-1)^nn^2+(-1)^nn,C(n)=(-1)^n\frac{n(n+1)}{2}$.

而原式中,$S(n)=C(n)=(-1)^n\frac{n(n+1)}{2}$.

#####Example2(《具体数学》2.19)

有$2T_n=nT_{n-1}+3n!,T_0=5$,求$T_n$.

#####Solution 2

令$s_n=\frac{2^{n-1}}{n!}$,两边同时乘以$s_n$,有$\frac{2^n}{n!}T_n=\frac{2^{n-1}}{(n-1)!}T_{n-1}+3\times 2^{n-1}\\$.

令$S_n=\frac{2^n}{n!}T_n$,有:

\[ S_n=S_{n-1}+3\times 2^{n-1}\\=5+3\sum_{i=0}^{n-1}2^i\\=5+3\times 2^{n+1}-3\\=3\times 2^{n}+2\\T_n=3n!+\frac{n!}{2^{n-1}} \]

转化为积分形式

Example1(平方和公式)

考虑先求出一个近似解,然后再求误差.

考虑函数$f(x)=x^2$,显然$\int_0^nx^2dx=\frac{n^3}{3}\sim S_n\\$.

接下来,我们考虑求得二者之间的误差,设$E_n=S_n-\frac{n^3}{3}\\$,对其使用扰动法:

\[ E_n=S_n-\frac{n^3}3\\=S_{n-1}+n^2-\frac{(n-1+1)^3}{3} \\=S_{n-1}+n^2-\frac{(n-1)^3}3-(n-1)^2-(n-1)-\frac 1 3 \\=E_{n-1}+n^2-n^2+2n-1-n+1-\frac 1 3\\=E_{n-1}+n-\frac{1}3 \] 这样就得到了递归式,可以求得封闭形式.

还有一种方法是: \[ E_n=S_n-\int_0^nx^2dx\\=\sum_{k=1}^n(k^2-\int_{k-1}^kx^2dx) \\=\sum_{k=1}^n(k^2-\frac{k^3-(k-1)^3}{3})\\=\sum_{k=1}^n(k-\frac1 3) \] 这是一个简单的和式.而$S_n=E_n+\frac{n^3}3\\$,显然也可以求得.

Example2(某浙江高考题)

已知$a_1=1,a_{n+1}-a_n=-\frac{1}{3}a_n^2$,估计$a_n$的值.

考虑构造一个函数$f(n)$使得$f(n)\approx a_n$,那我们就可以将$a_{n+1}-a_n\approx f_n$.

这个第一眼看上去就很有道理,而事实上也确实很有道理,原因是根据拉格朗日中值定理,$\exists x_0\in[n,n+1],f'(x_0)=f(n+1)-f(n)$,而对于增长率变化不大的函数,直接认为$f'(x_0)=f'(n)$是有理可循的!

然后,原式子就变成了一个微分方程了,带入$f(1)=1$解得$f(n)=\frac{3}{n+2}$.这个精度已经足够选出来原本的放缩题的答案了.

令$a_n=\frac{3}{n+2}-b_n$,带入化简,得到$\{b_n\}$的递推式:

\[ \frac{3}{n+3}-b_{n+1}=(\frac{3}{n+2}-b_n)(1-\frac{1}{n+2}+\frac{b_n}{3})\\ b_{n+1}-\frac{3}{n+3}=(b_n-\frac{3}{n+2})(\frac{n+1}{n+2}+\frac{b_n}{3})\\b_1=0,b_{n+1}=\frac{b_n^2}{3}+\frac{n}{n+2}b_n+\frac{3}{(n+2)^2(n+3)} \]

算到这里,我们可以很轻易使用数学归纳法算出$b_n\leq \frac{1}{4n}$,这个精度已经挺不错的了,但是也让人觉得很不满意,因为这个误差项怎么和估计项是同阶的啊.

然后我开始估计了一下这个$b_n$的阶,因为我其实没学过什么高超的高数技巧,所以我使用了OI的一些技巧来估计,不妨假设$b_n^2<<b_n$:

那么这个$b_n$是$O(\frac{\ln n}{n^2})$级别的.

如何理解这个级别?考虑别乱动$b_n$的系数,我们有:

\[ b_{n+1}=\frac{n}{n+2}b_n+\frac{1}{n(n+1)(n+2)}\\ (n+1)(n+2)b_{n+1}=n(n+1)b_n+\frac{1}{n}\\ g(n)=n(n+1)b_n,g'(n)=\frac{1}{n},g(n)=\ln n\\ b_n=\frac{\ln n}{n^2} \]

这警戒我们以后乱估计的时候千万别把$O(n^{\epsilon})$和$O(1)$搞混了,警钟长鸣.

这个时候大概估计一下会发现$b_n\leq \frac{3\ln n}{n(n+1)}$.

展开和收缩

Example1(平方和公式)

我们有: \[ S_n=\sum_{k=1}^nk^2\\=\sum_{k=1}^n\sum_{i=1}^kk \\=\sum_{i=1}^n\sum_{k=i}^nk\\=\sum_{i=1}^n\frac 1 2(i+n)(n-i+1)\\=\sum_{i=1}^n\frac{1}2(in-i^2+i+n^2-ni+n)\\ =\frac{1}2(\sum_{i=1}^ni-\sum_{i=1}^ni^2+n^3+n^2)\\=\frac{1}4n(n+1)-\frac1 2S_n+\frac{n^3+n^2}2 \]

整理得到$S_n$.

Example2(《具体数学》2.14)

求$\sum_{i=1}^ni2^i\\$.

Solution 2

\[ \sum_{i=1}^ni2^i=\sum_{i=1}^n\sum_{j=1}^i2^i\\=\sum_{j=1}^n\sum_{i=j}^n2^i\\=\sum_{j=1}^n(2^{n+1}-2^j)\\=n2^{n+1}-(2^{n+1}-2)\\=(n-1)2^{n+1}+2 \]

Example3(《具体数学》2.15)

求$\sum_{i=1}^n i^3\\$.

Solution 3

\[ S(n)=\sum_{i=1}^n i^3\\=\sum_{i=1}^n\sum_{j=1}^ii^2\\=\sum_{j=1}^n\sum_{i=j}^ni^2\\=\sum_{j=1}^n(\frac{n(n+1)(2n+1)}{6}-\frac{(j-1)j(2j-1)}{6})\\=\frac{n^2(n+1)(2n+1)}{6}-\frac 1 3 S(n)+\frac{n(n+1)(2n+1)}{12}-\frac{n(n+1)}{12}\\S(n)=\frac{n^2(n+1)^2}{4} \]

ExampleEX

求$\sum_{i=1}^niq^i(q\ne 1)$.

SolutionEX

\[ \sum_{i=1}^niq^i=\sum_{j=1}^n\sum_{i=j}^nq^i\\ =\sum_{j=1}^n\frac{q^j-q^{n+1}}{1-q}\\ =\frac{1}{q-1}\sum_{j=1}^n(q^{n+1}-q^j)\\ =\frac{1}{q-1}(nq^{n+1}-\frac{q^{n+1}-q}{q-1})\\ \]

ExampleEX2

求$\sum_{i=1}^n(ai+b)q^{i-1}(q\ne 1)$.

SolutionEX2

令$A=\frac{a}{q-1},B=\frac{b-A}{q-1}$,答案为$(An+B)q^n-B$.

有限微积分

移位算子

定义移位算子$E$，使得$Ef(x)=f(x+1)$.

差分算子

定义差分算子$\Delta f(x)=f(x+1)-f(x)$，类似于无限微积分中的D算子.

另外,不难发现有$\Delta=E-1$.

逆差分算子

定义逆差分算子$\Sigma$,可以得到有限微积分的基本定理:

\[ g(x)=\Delta f(x)\Leftrightarrow \sum g(x)\delta x=f(x)+C\\ \] 这里的$\Sigma$又被称为不定和式,是差分等于$g$的一个函数类.

值得一提的是,这里的$C$与无限微积分中的$C$有一定区别,这里的$C$可以是满足$p(x)=p(x+1)$的任意一个函数而不非得是常数函数.

定和式

如果$g(x)=\Delta f(x)$,那么有$\sum\nolimits_{a}^b g(x)\delta x=f(x)|^{b}_a=f(b)-f(a)\\$.

值得一提的是,如果$a\leq b$,显然有$\sum\nolimits_{a}^bg(x)\delta x=\sum_{x=a}^{b-1}g(x)\\$.

但如果$a>b$,那么$\sum\nolimits_{a}^bg(x)\delta x=-\sum\nolimits_b^a g(x)\delta x\\$.

事实上,我们一定有:$\sum\nolimits_a^bg(x)\delta x+\sum\nolimits_b^cg(x)\delta x=\sum\nolimits_a^cg(x)\delta x\\$.

一些基本的公式

类比无限微积分中的$D(x^m)=mx^{m-1}$，有:

\[ \Delta(x^{\underline{m}})=mx^{\underline{m-1}}\\\sum mx^{\underline{m-1}}\delta x=x^{\underline{m}}+C,m\ne 0\\ \\ \] 类比无限微积分中的$D(\ln x)=\frac 1 x$,有: \[ \Delta(H(x))=x^{\underline{-1}}=\frac{1}{x+1}\\ \sum x^{\underline{-1}}\delta x =H(x)+C\\ \\ \] 类比无限微积分中的$D(e^x)=e^x$,有: \[ \Delta(2^x)=2^x,\sum 2^x\delta x=2^x+C\\ \Delta (c^x)=(c-1)c^x,\sum c^x\delta x=\frac{c^x}{c-1}+C,c\ne 1\\ \Delta (c^{\underline{x}})=\frac{c^{\underline{x+2}}}{c-x},\sum \frac{c^{\underline{x+2}}}{c-x}\delta x=c^{\underline{x}}+C,c-x\ne 0\\ \] 根据组合数公式,有:

\[ \Delta(\binom{x}{k})=\binom{x}{k-1}\\\sum\binom{x}{k-1}\delta x=\binom{x}{k}+C \]

######Example(平方和公式)

我们有:$k^2=k^{\underline{2}}+k^{\underline{1}}\\$.

那么:

\[ S_{n-1}=\sum_{i=0}^{n-1}i^2\\=\sum_{i=0}^{n-1}(i^{\underline{2}}+i^{\underline{1}})\\=\sum\nolimits_{0}^nx^{\underline2}\delta x+\sum\nolimits_{0}^nx^{\underline 1}\delta x\\=\frac{n^\underline{3}}{3}+\frac{n^{\underline{2}}}{2} \] 整理即可得到封闭形式.

值得一提的是:

与前面的方法不同，这里没有使用三次的二项式公式，而是使用了二次的斯特林公式负责将一般幂转化为下降幂.

高阶差分

考虑一阶差分是$\Delta f(x)=f(x+1)-f(x)$,那么二阶差分就是$\Delta^2f(x)=f(x+2)-2f(x+1)+f(x)$.

类似地,我们可以通过归纳法证明$\Delta^nf(x)=\sum_{k}\binom{n}{k}(-1)^{n-k}f(x+k)\\$.

事实上有一种更简单的证明方法,由于$\Delta=E-1$,于是$\Delta^n=(E-1)^n=\sum_{k}\binom{n}{k}(-1)^{n-k}E^k\\$,由于$E^kf(x)=f(x+k)$,即可证明原式.

另外,不难发现如果$f(x)$是一个关于$x$的$d$次多项式,那么$\Delta f(x)$是一个$d-1$次多项式.同理,$\Delta^d f(x)$会是一个常数而$\Delta^{d+1}f(x)$会是$0$,这个发现引出了牛顿级数.

Example([yLOI2020]灼)

首先不难发现对于一个位置,有意义的只有相邻的两个虫洞,设这两个位置分别为$x_1,x_2$.

不难写出期望转移式子:$f_i=\cfrac{1}{2}(f_{i-1}+f_{i+1})+1$,并且$f_{x_1}=f_{x_2}=0$.

接下来如何做呢?

我们先对第一个式子进行变形: \[ f_i=\cfrac{1}{2}(f_{i-1}+f_{i+1})+1\\ 2f_i=f_{i-1}+f_{i+1}+2\\ f_i-f_{i-1}=f_{i+1}-f_i+2\\ \Delta f_{i-1}=\Delta f_{i}+2\\ \Delta f_i-\Delta f_{i-1}=-2\\ \Delta^2 f_{i-1}=-2 \] $f$的二阶差分是常数,也就是说$f$是二次多项式,不难求得其二次项系数为$-1$又知道两个零点,显然可以得到$f$的表达式.

牛顿级数

令$f(x)=\sum_{0\leq i\leq d}a_ix^i\\$.而由于有斯特林数可以进行幂和下降幂的转换,则我们可以将其改写为$f(x)=\sum_{0\leq i\leq d}b_ix^{\underline{i}}\\$.

我们设$c_i=i!b_i$,于是有:$f(x)=\sum_{0\leq i\leq d}c_i\binom{x}{i}\\$.

也就是说,任何多项式都可以表示为二项式系数的倍数之和,我们称这样的展开式为$f(x)$的牛顿级数.

于是不难发现有:$\Delta^nf(x)=\sum_{0\leq i\leq d}c_i\binom{x}{i-n}\\$.如果我们令$x=0$,则有:$\Delta^nf(0)=\begin{cases}c_n&n\leq d\\0&n>d\end{cases}$.那么牛顿级数的另一种表示即:$f(x)=\sum_{0\leq i\leq d}\Delta^if(0)\binom{x}{d}\\$.

另外,如果我们展开一下$c_n=\Delta^nf(0)$,我们可以得到公式:

$\sum_{k}\binom{n}{k}(-1)^k(\sum_{0\leq i\leq n}c_i\binom{k}{i})=(-1)^nc_n,n\in\mathbb{N}\\$.

如果我们将多项式还原,由于$a_n=b_n$,有:

$\sum_{k}\binom{n}{k}(-1)^k(\sum_{0\leq i\leq n}a_ik^i)=(-1)^nn!a_n,n\in\mathbb{N}\\$.

另外,如果$x\in\mathbb{N}$,那么我们有:$f(x)=\sum_{0\leq k}\Delta^kf(0)\binom{x}{0}$,根据多项式推理法,这个公式对$\forall x\in\mathbb{Z}$都成立.

于是我们可以类似泰勒级数写出无限牛顿级数: \[ g(a+x)=\sum_{0\leq k}\cfrac{\Delta^kg(a)}{k!}x^{\underline{k}} \]

Example

求$\sum_{k}\binom{n}{k}\binom{r-sk}{n}(-1)^k,n\in\mathbb{N}\\$.

如果我们令$f(k)=\binom{r-sk}{n}=\sum_{0\leq i\leq n}a_ik^i\\$,不难发现$a_n=\cfrac{(-1)^ns^n}{n!}$,于是显然原式$=s^n$.

分部求和法则(Abel求和法)

\[ \Delta(uv)=u(x+1)v(x+1)-u(x)v(x)\\ =u(x+1)v(x+1)-u(x)v(x+1)+u(x)v(x+1)-u(x)v(x)\\ =v(x+1)\Delta u+u(x)\Delta v=Ev\Delta u+u\Delta v\\ \]

两边取不定和，即可得到分部求和法则:

$\sum u\Delta v=uv-\sum Ev\Delta u\\$.

分部求和用一般和式表达如下,下式又被称为Abel求和法:

\[ \sum_{i=l}^{r-1}(a_{i+1}-a_i)b_i=a_rb_r-a_lb_l-\sum_{i=l}^{r-1}a_{i+1}(b_{i+1}-b_i)\\ \sum_{i=l}^{r-1}(\Delta a_i)b_i=a_rb_r-a_lb_l-\sum_{i=l}^{r-1}a_{i+1}(\Delta b_i) \]

对于$l=0,r=n,a_0=b_0=0$的特殊情况,应当有: \[ \sum_{i=0}^{n-1}(\Delta a_i)b_i=a_nb_n-\sum_{i=0}^{n-1}a_{i+1}(\Delta b_i)\\ \sum_{i=1}^na_i(b_{i+1}-b_i)=a_nb_n-\sum_{i=0}^{n-1}(\Delta a_i)b_i \] 取两组数列$\alpha,\beta$,并令$\sum_{i=1}^n \beta_i=B_i$,立刻有: \[ \sum_{i=1}^n \alpha_i\beta_i=\alpha_nB_n-\sum_{i=1}^{n-1}(\alpha_{i+1}-\alpha_i)B_i \]

Example1

求$\sum_{k=0}^nk2^k\\$.

根据分部求和法则，我们有:

$\sum x2^x\delta x=x2^x-\sum2^{x+1}\delta x=x2^x-2^{x+1}+C\\$.

改为定和式形式，显然有:

$\sum_{k=0}^nk2^k=\sum\nolimits_0^{n+1}x2^x\delta x=(n+1)2^{n+1}-2^{n+2}+2=(n-1)2^{n+1}+2\\$.

Example2

求$\sum_{k=0}^{n-1}kH_k\\$.

令$u(x)=H_x,v(x)=\frac 1 2x^{\underline{2}}\\$.

带入分部求和法则，显然有:

$\sum xH_x\delta x=\frac{x^\underline{2}}2H_x-\frac{x^\underline{2}}4+C\\$.

带入即可求出原式$=\frac{n^\underline{2}}2(H_n-\frac{1}2)\\$.

######Example3(《具体数学》2.23)

求$\sum_{i=1}^n\frac{2i+1}{i(i+1)}\\$.

######Solution 3

令$u=(2n+1),v=-\frac{1}{i}$,则$\Delta u=2,\Delta v=\frac{1}{i(i+1)}$.

根据分部求和法则,有:

\[ \sum_{i=1}^n\frac{2i+1}{i(i+1)}=(2n+3)\times (-\frac{1}{n+1})+3-\sum_{i=1}^n(-\frac{2}{i+1})\\=-\frac{2n+3}{n+1}+2H_n+\frac{n+3}{n+1}=2H_n-\frac{n}{n+1} \]

######Problem 4(《具体数学》2.24)

求$\sum_{i=0}^{n-1}\frac{H_k}{(k+1)(k+2)}\\$.

######Solution 4

令$u=H_n,v=-\frac{1}{n+1},\Delta u=\frac{1}{n+1},\Delta v=\frac{1}{(n+1)(n+2)}\\$.

根据分部求和法则,有:

\[ \sum_{i=0}^{n-1}\frac{H_k}{(k+1)(k+2)}=-\frac{H_n}{n+1}-\sum_{i=0}^{n-1}(-\frac{1}{(i+2)(i+1)})\\=-\frac{H_n}{n+1}+\sum_{i=0}^{n-1}(\frac{1}{i+1}-\frac{1}{i+2})\\=-\frac{H_n}{n+1}+H_n-(H_n-1+\frac{1}{n+1})\\=1-\frac{H_n+1}{n+1} \]