递归式

递归式(Recurrence Relation), 又称递推关系, 是一种用序列中前面的项来定义后面的项的等式. 简单说:

一个问题的解, 依赖于同一问题的更小规模实例的解.

形式上, 一个递归式通常写作: $$T(n)=f(T(n-1),T(n-2),\dots ,T(1),n)$$

即 $T(n)$ 的值由更小的 $T(k)$ 和 $n$ 本身共同决定, 并附带边界条件.

从数学上看, 递归式是离散动力系统的一种——它描述了序列如何从初始状态一步步演化.

数学上的经典例子

数学上解决

线性常系数齐次递归

对于形如: $$a_n=c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}$$ 的递归式, 我们常用的数学武器是——特征方程法.

1. 假设解的形式: $a_n=r^n$

2. 代入得特征方程:

$$r^k-c_1{r}^{k-1}-c_2{r}^{k-2}-\cdots -c_k=0$$

3. 求根 $r_1,r_2,\dots ,r_k$

4. 通解:

   • 若无重根: $a_n={\alpha }_1{r}_1^n+{\alpha }_2{r}_2^n+\cdots +{\alpha }_k{r}_k^n$
   • 若 $r$ 是 $m$ 重根, 对应项为: $({\alpha }_0+{\alpha }_{1}n+\cdots +{\alpha }_{m-1}{n}^{m-1})r^n$

5. 用边界条件确定系数 ${\alpha }_i$

以斐波那契为例:

• 递归式: $F_n=F_{n-1}+F_{n-2}$, 边界 $F_0=0,F_1=1$
• 特征方程: $r^2-r-1=0$
• 根: $\varphi =\frac{1+\sqrt{5}}{2}\approx 1.618$(黄金比例), $\psi =\frac{1-\sqrt{5}}{2}\approx -0.618$
• 通解: $F_n=\alpha {\varphi }^n+\beta {\psi }^n$, 代入边界得比内公式.

非齐次递归

对于形如 $a_n=c_1{a}_{n-1}+f(n)$ 的递归式, 通解 = 齐次通解 + 一个特解. 求解方法包括:

• 待定系数法($f(n)$ 为多项式、指数等时)
• 生成函数法(将递归转化为函数方程, 用幂级数求解)

生成函数视角尤为优雅: 定义 $G(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$, 递归关系转化为 $G(x)$ 的代数方程, 解出后展开即得通项.

Warning

该章节仍在编写, 在 Github仓库 上提交PR以为本书 贡献内容.

练习与回答

1. 已知数列 $\{a_n\}$ 满足: $$a_n=3a_{n-1}-2a_{n-2},a_0=0,a_1=1$$ 试求该数列的通项公式.

容易得到特征方程为 $r^2-3r+2=0$, 根为 $r=1$, $r=2$. 所以通项公式即为 $a_n=n-1$.