离散数学

常系数线性递推

本质

求常系数线性递推的封闭形式 $\Leftrightarrow$ 求常系数线性差分方程の通解 所以很多地方可以与 微分方程 类比

Warning

  1. 递推公式必须是最简形式，比如 $a_{n}=(a_{n+1}+a_{n-1})/2$ 不是递推，尽管可以化为递推

齐次

齐次常系数线性递推 :=

$$ a_{n+k}=\sum_{i=0}^{k-1}c_{i}a_{n+i} $$

则

  1. 特征方程 $$x^{n+k}=\sum_{i=0}^{k-1}c_{i}x^{n+i} $$

  2. 解为 $r_{1},\dots,r_{R}$，重数分别是 $m_{1},\dots,m_{R}$

  3. 封闭形式为 $a_{n}=\sum_{i=1}^{R}(\beta_{i,0}+\beta_{i,1}n+\dots+\beta_{i,m_{i}-1}n^{m_{i}-1})r_{i}^{n}$

  4. 系数 $\beta_{i,j}$ 由相应数量 $\sum m_{i}$ 个初项待定系数解出

退化

当重数 $r_{i}=1$ 时 封闭形式 $a_{n}=\sum_{i=1}^{n}\beta_{i}r_{i}^{n}$

虚特征根

遇到虚特征根 $r_{i}=l_{i}e^{i\theta_{i}}$，则通解部分项为 $(\beta_{i,0}+\dots\beta_{i,m_{i}-1}n^{m_{i}-1})(l_{i}e^{i\theta_i})^{n}=l_{i}^{n}\sum_{j=0}^{m_{i}-1}(C_{i,j,0}\cos n\theta+C_{i,j,1}\sin n\theta)n^{j}$

与之对偶的 微分方程 虚特征根の通解项为 $(a+bi)^{n}=a^{n}(C_{1}\cos bn+C_{2}\sin bn)$

差分方程是极坐标形式分解，而微分方程是直角坐标形式分解

非齐次

非齐次常系数线性递推 :=

$$ a_{n+k}=\sum_{i=0}^{k-1} c_{i}a_{n+i} +F(n) $$

  1. 伴随齐次线性递推式 $$a_{n+k}=\sum_{i=0}^{k-1} c_{i}a_{n+i}$$

  2. 伴随式解为 ${a_{n}^{(h)}}$

  3. 不考虑初始情况，原递推式有特解 ${a_{n}^{(p)}}$

    1. 若 $F(n)$ 具有形式 $$F(n)=(b_{t}n^{t}+\dots+b_{0})s^{n}$$

      1. $s$ 是伴随解的 $m$ 重根 ($0$ 重根表示不是伴随解)
      2. 则特解 $a_{n}^{(p)}=n^{m}(p_{t}n^{t}+\dots+p_{0})s^{n}$ $t$ = $F(n)$ 中的 $t$！！！

    2. 通过通解形式代入原线性递推式求出 $a_{n}^{(p)}$ 系数

  4. 通解具有形式 ${a_{n}^{(p)}+a_{n}^{(h)}}$

    1. 通过代入初始项确定 $a_{n}^{(h)}$ 系数
求系数顺序

  1. 先求特解 $a_{n}^{(p)}$ 系数，by 特解形式代入递推项
  2. 再求伴随齐次解 $a_{n}^{(h)}$ 系数，by 代入初始项