Recurrence - 递归

更新中 · 笔记范围：持续补充

一个函数的 递归式（Recurrence Equation / Recurrence） 告诉我们如何从前 n-1 个函数值计算出 n 处的函数值：
f(n)=F(f(1),f(2), \dots,f(n-1))
例如解汉诺塔的递归算法。

  • 正确性。用 implicit 的归纳法，说明能解 1 层的，并且能解 n-1 层的汉诺塔就能解 n 层的即可。([n,0,0]\to[1,n-1,0]\to[0,n-1,1]\to[0,0,n])。
  • 复杂度。M(n)=2M(n-1)+1,M(1)=1。 可以用 explicit 的归纳法证明 M(n)=2^{n}-1。

一阶线性递归式（First-Order Linear Recurrence）： T(n) 只和 T(n-1) 有关，且 T(n-1) 只有一次。可以写成：
T(n)=f(n) T(n-1) +g(n)

定理： 对递归式
T(n)=rT(n-1)+g(n)
有
T(n)=r^{n}T(0)+ \sum _{i=1}^{n} r^{n-i}g(i)
显然可以通过数学归纳法证明。

主定理（The Master Theorem）。 对递归式
T(n)= aT(n / b) + c n^{d}
其中 a 为正整数，b>1,c>0,d\geq0，T(1)\geq0。那么：

  • 若 a<b^{d}，则 T(n)=\Theta(n^{d})。
  • 若 a=b^{d}，则 T(n) =\Theta(n^{d}\log n)
  • 若 a>b^{d}，则 T(n)=\Theta(n^{\log _{b}a})

解线性齐次递归式

常系数 k 阶线性齐次递归式（Linear homogeneous relation of degree k with constant coefficients）：
a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\dots+c_{k}a_{n-k}
这里 c_{1},c_{2}, \dots, c_{k} 是常数，且 c_{k}\neq0。
如果不限定初始条件，可能有很多解；如果有初始条件，解就唯一了。
注意到，如果 a_{n}, a_{n}' 是解，那么 a_{n}+a_{n}' 和 \alpha a_{n} 仍然是解，也就是说，它们的线性组合也是解。因此，不妨先关注一个特定形式的解： a_{n}=r^{n}。代入得到
r^{n}=c_{1}r^{n-1}+c_{2}r^{n-2}+\dots+c_{k}r^{n-k}
r=0 显然成立。如果 r\neq0，两边同除 r^{n-k}，这就相当于解方程
r^{k}-c_{1}r^{k-1}-\dots-c_{k-1}r-c_{k}=0
这个方程就叫这个序列的 特征方程（Characteristic Equation, CE）。

考虑 2 阶的形式 a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}，它的特征方程是 r^{2}-c_{1}r-c_{2}=0。若它有两个不等的根 r_{1}\neq r_{2}，那么 \{ a_{n} \} 是解，当且仅当
a_{n}=\alpha _{1}r_{1}^{n}+\alpha _{2}r_{2}^{n}
证明：

  • “当“：只需要代入递归式验证即可。
    \begin{aligned} &c_{1}a_{n-1}+c_{2}a_{n-2} \\ = & c_{1}(\alpha_{1}r_{1}^{n-1}+\alpha _{2}r_{2}^{n-1})+c_{2}(\alpha_{1}r_{1}^{n-2}+\alpha _{2}r_{2}^{n-2}) \\ = & \alpha _{1} r_{1}^{n-2}(c_{1}r_{1}+c_{2})+ \alpha _{2}r_{2}^{n-2}(c_{1}r_{2}+c_{2}) \\ =& \alpha_{1}r_{1}^{n-2} \cdot r_{1}^{2} + \alpha_{2}r_{2}^{n-2}\cdot r_{2}^{2} \\ =& \alpha_{1} r_{1}^{n} + \alpha _{2} r_{2}^{n}=a_{n} \end{aligned}
  • “仅当”：如果初始条件确定了，那么 a_{n} 就会完全确定下来。而因为 r_{1}\neq r_{2}，方程组 \alpha_{1}+\alpha_{2}=a_{0},\ \alpha_{1}r_{1}+\alpha_{2}r_{2}=a_{1} 总有解，也就是说对任意初始条件，都能找到这种形式的一个解。那么它就应该是唯一的解。

若这个二次的特征方程有重根 r_{0}，那么
a_{n}=\alpha_{1}r_{0}^{n}+\alpha_{2}nr_{0}^{n}
证明：

  • 重根：令 f(r)=r^{n}-c_{1} r^{n-1} - c_{2}r^{n-2}-\dots-c_{k}r^{n-k}，那么有 f(r_{0})=f'(r_{0})=0，从而可以推出 nr_{0}^{n} 也是解。

考虑 k 阶的情况，若特征方程 r^{k}-\sum _{i=1}^{k} c_{i}r^{k-i} = 0 有 k 个不同的根，那么解的形式就是
a_{n}=\sum _{i=1}^{k}\alpha_{i}r_{i}^{n}
证明与 2 阶类似。
有重根的情况：
a_{n}= \sum _{i=1}^{t} \left(\sum _{j=0}^{m_{i}-1}\alpha _{i,j}n^{j}\right) r_{i}^{n}
其中 r_{i} 的重数（Multiplicities）为 m_{i}。

解线性非齐次递归式

对于线性非齐次的递归式
a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\dots+c_{k}a_{n-k} + F(n)
其中 F(n) 让这个递归式不再齐次。那么，如果这个递归式有一个特解 p(n)，而齐次的部分
a_{n}=c_{1}a_{n-1}+c_{2}a_{n-2}+\dots+c_{k}a_{n-k}
的解为 h(n)，那么通解的结构为
a_{n}=h(n)+p(n)
例如解汉诺塔递归式 H(n)=2H(n-1)+1，使用现在的通用方法：

  • 齐次部分 H(n)=2H(n-1)，特征方程为 r-2=0，解为 h(n)=\alpha2^{n}。
  • 我们猜特解 p(n)=c 是一个常数。那么 c=2c+1\implies c=-1，于是 H(n)=\alpha2^{n}-1。结合 H(1)=1 得到 H(n)=2^{n}-1。