递推式 (recurrence) 又叫递归式或差分方程, 它与常微分方程理论中的许多内容平行, 对照学习收获更多!

入门

等差数列与等比数列

    不妨设数列的首项为 `x_0`.
  1. 满足递推关系 `x_n = x_(n-1) + d`, `n = 1, 2, cdots` 的数列称为等差数列, 其中 `d` 为常数.
  2. 满足递推关系 `x_n = x_(n-1) * q`, `n = 1, 2, cdots` 的数列称为等比数列, 其中 `q` 为常数.
  1. 等差数列的通项公式为 `x_n = x_0 + n d`, 前 `n` 项和为 `sum_(k=0)^(n-1) x_k = sum_(k=0)^(n-1) (x_0 + k d)` `= n x_0 + (n(n-1))/2 d`.
  2. 等比数列的通项公式为 `x_n = q^n x_0`, 前 `n` 项和为 `sum_(k=0)^(n-1) x_k = sum_(k=0)^(n-1) q^k x_0` `= {x_0 (1-q^n)/(1-q), if q != 1; x_0 n, if q = 1:}`.
    求解
  1. 线性递推式 `x_n = a x_(n-1) + d`;
  2. Bernoulli 型递推式 `x_n = a x_(n-1) + d a^n`.
  3. 高次递推式 `x_0 gt 0`, `x_(n+1) = a x_n^m`. 其中 `a gt 0`, `m in RR`.
    当然前 2 小题也可以看作一般的常系数线性递推关系来解答. 详见下文.
  1. `a = 1` 时 `x_n` 即为等差数列. 下设 `a != 1`, 使用待定系数法, 设 `x_n - c = a(x_(n-1) - c)`, 于是 `x_n = a x_(n-1) + (1-a) c`, 与原递推式比较得 `c = d//(1-a)`. 从而 `{x_n - c}` 是以 `a` 为公比的等比数列. 解得 `x_n = a^n x_0 + (1-a^n)/(1-a) d` `= a^n x_0 + (a^(n-1) + cdots + a + 1)d`.
  2. 两边同乘以 `a^-n` 得 `x_n/a^n = x_(n-1)/a^(n-1) + d`, 即 `{x_n/a^n}` 是以 `d` 为公差的等差数列.
  3. 取对数得 `ln x_(n+1) = ln a + m ln x_n`. 这是线性递推式, 解为 `ln x_n = m^n ln x_0 + (1-m^n)/(1-m) ln a`. 于是 `x_n = x_0^(m^n) * a^((1-m^n)/(1-m))`.
    用归纳法容易证明以下多项式的重要求和公式
  1. `sum_(k=1)^n 1 = n`;
  2. `sum_(k=1)^n k = n^2/2 + n/2 = (n(n+1))/2`;
  3. `sum_(k=1)^n k^2 = n^3/3 + n^2/2 + n/6` `= (n(n+1)(2n+1))/6`;
  4. `sum_(k=1)^n k^3 = n^4/4 + n^3/2 + n^2/4` `= ((n(n+1))/2)^2`.

这些公式目前是足够的; 我们以后将得出 `sum_(k=1)^n k^m` (`m` 为非负整数) 的公式.

对于非负整数 `m, n`, Ackermann 函数定义为 `A(m, n) = { n+1, if m = 0; A(m-1, 1), if m gt 0 and n = 0; A(m-1, A(m, n-1)), if "else"; :}` 试计算 `A(0, n)`, `A(1, n)`, `A(2, n)`, `A(3, n)` 的通项公式, 并求 `A(4, 2)`.

  1. `A(0, n) = n+1`.
  2. `A(1, n) = A(0, A(1, n-1))` `= A(1, n-1) + 1`; 故 `A(1, n)` 为等差数列. 利用 `A(1, 0) = A(0, 1) = 2` 有: `A(1, n) = n+2`.
  3. `A(2, n) = A(1, A(2, n-1))` `= A(2, n-1) + 2`; 故 `A(2, n)` 也为等差数列. 利用 `A(2, 0) = A(1, 1) = 3` 有: `A(2, n) = 2n + 3`.
  4. `A(3, n) = A(2, A(3, n-1))` `= 2A(3, n-1) + 3`. 设 `A(3, n) + c = 2(A(3, n-1) + c)`, 解得 `c = 3`. 利用等比数列通项公式和 `A(3, 0) = A(2, 1) = 5` 有: `A(3, n) = 2^(n+3) - 3`.
  5. `A(4, 2) = A(3, A(4, 1))` `= A(3, A(3, A(4, 0)))` `= A(3, A(3, A(3, 1)))` `= A(3, A(3, 16-3))` `= A(3, 65536-3)` `= 2^65536-3`.

大整数的表示*

  1. Knuth 箭头 (高德纳箭头). 设 `a, r` 为正整数. 规定 `a uarr r` `:= underbrace(a * cdots * a)_r`,
    `a uarr uarr r` `:= underbrace(a uarr cdots uarr a)_r`,
    `a uarr uarr uarr r` `:= underbrace(a uarr uarr cdots uarr uarr a)_r `,     Knuth 箭头的结合性是从右往左计算, 如 `a uarr b uarr c = a uarr (b uarr c)` `= a^(b^c)`.
    把 `n` 个箭头简记为 `uarr^n`, 则 Knuth 箭头递归定义为: `a uarr^n r :=` `{ a^r, if n = 1 or r = 1; a uarr^(n-1) a uarr^n (r-1), otherwise; :}` Knuth 箭头的性质:
    1. 对任意正整数 `n`, `2 uarr^n 2 = 4`.

    在计算机上, 可以用 ^ 代替箭头, 如 `a uarr b` 写作 a^b, `a uarr uarr b` 写作 a^^b.

  2. Conway 链 [来自Wikimili] 递归定义如下:
    1. `() := 1`;
    2. `(a) := a`;
    3. `a to b := a^b`;
    4. `a to b to c := a uarr^c b`;
    5. `X` 是任意链, `X to 1 := X`, `X to 1 to y := X`. 这就是说末尾和倒数第二位的 `1` 可以去掉;
    6. `X` 是任意链, `X to (a+1) to (b+1) :=` `X to (X to a to (b+1)) to b`. 此规则使得链的长度不变, 但末尾的数字减小. 反复展开中间的括号, 每展开一次, `a` 就减小 `1`. 注意 `X to 1 to (b+1) = X`, 我们得到 `X to (a+1) to (b+1)` `= underbrace(color(red)(X to"(") cdots color(red)(X to"("))_a X underbrace(color(blue)(")"to b)cdots color(blue)(")"to b))_a`. 这一条定义与 Knuth 箭头是相容的. 比如 `x to (a+1) to (b+1)`
      `= x uarr^(b+1) (a+1)` ……Conway 链定义 (4)
      `= x uarr^b x uarr^(b+1) a` ……Knuth 箭头定义
      `= x to (x to a to (b+1)) to b. qquad` ……Conway 链定义 (4)
    Conway 链的性质:
    1. Conway 链不具有结合律, 括号不能随意去掉.
    2. 链的值总是它的第一个数的整数次方, 特别地 `1 to X = 1`.
    3. `X to 1 to Y = X`. 这就是说只要链的中间出现 `1`, 之后的部分就都可以丢弃.
    4. `2 to 2 to Y = 4`. 即 `2 uarr^n 2 = 4`.
    5. `X to 2 to 2 = X to (X)`. 这是定义 (6) 的简单推论. 注意不要与 `X to X` 混淆.

    Conway 的生命游戏 (game of life) 也很有名：）

Graham 数 (葛立恒数) 设 `g(1) = 3 uarr^4 3`, `g(n+1) = 3 uarr^(g(n)) 3`, 则 `g(64)` 称为 Graham 数: `g(n) = 3 underbrace(uarr cdots uarr)_{::} 3`
`qquad quad vdots`
`g(3) = 3 underbrace(uarr cdots uarr)_{::} 3`
`g(2) = 3 underbrace(uarr cdots uarr)_{::} 3`
`g(1) = 3 uarr uarr uarr uarr 3`

    TREE(3) 设 `t_1, t_2, cdots t_m` 是树 (连通无环简单无向图) 的序列, 且满足如下规则:
  1. `t_i` 的节点数不超过 `i`.
  2. 每个节点的颜色是 `n` 种颜色的一种.
  3. 前面的树 `t_i` 不能是后面的树 `t_j (j gt i)` 的子树. 这里的子树需要考虑节点颜色.
    4. 现在固定 `n` 的值, 我们把 `m` 的最大可能值记为 `"TREE"(n)`. 容易得到 `"TREE"(1) = 1` 和 `"TREE"(2) = 3`. 但 `"TREE"(3)` 则是一个巨大的数字, 比 Graham 数还大得多: 
    TREE(1): *

TREE(2): *   *    *
              \
               *

TREE(3): ...

    求和因子

    设递推关系为 `a_n x_n = b_n x_(n-1) + c_n`, 等号两边乘以适当的 `s_n` 得 `s_n a_n x_n = s_n b_n x_(n-1) + s_n c_n`. 如果 `s_n b_n = s_(n-1) a_(n-1)`, 记 `y_n = s_n a_n x_n`, 就有 `y_n = y_(n-1) + s_n c_n`, 这一递推式的解为 `y_n = y_0 + sum_(k=1)^n (y_k - y_(k-1))` `= y_0 + sum_(k=1)^n s_k c_k`. 再将 `s_n b_n = s_(n-1) a_(n-1)` 的解 `s_n = lambda (a_(n-1) cdots a_1 a_0)/(b_n cdots b_2 b_1)` 代入即可, 其中 `lambda` 为任意常数.

    `x_1 = 2`, `x_n = 1/((n-1)!) + 1/n x_(n-1)`, `n gt 1`. 求 `x_n` 通项公式.

    两边同乘以求和因子 `n!`, `n! x_n = (n-1)! x_(n-1) + n` `= 1! x_1 + sum_(k=2)^n k` `= 2 + (n(n+1))/2 - 1`. 所以 `x_n = 1/(n!) (1 + (n(n+1))/2)`.

    `x_1 = 1`, `x_n = 1 + 2/n^2 sum_(k=1)^(n-1) k x_k`, `n gt 1`. 求 `x_n` 通项公式.

    记 `S_n = 2 sum_(k=1)^n k x_k`. 从递推式中解出 `S_(n-1) = n^2 (x_n - 1)`, 相减得 `2 (n-1) x_(n-1) = S_(n-1) - S_(n-2)` `= n^2 x_n - (n-1)^2 x_(n-1) - (n^2 - (n-1)^2)`. 即 `n^2 x_n = (n+1)(n-1) x_(n-1) + 2n - 1`. 两边同加 `n^2`, 再同除以 `n(n+1)`, `n/(n+1) (x_n + 1) = (n-1)/n (x_(n-1) + 1) + 2/(n+1)` `= 1/2 (x_1 + 1) + sum_(k=2)^n 2/(k+1)` `= 2 sum_(k=1)^n 1/(k+1)`. 即 `x_n = 2(1+1/n) sum_(k=1)^n 1/(k+1) - 1`.

    成套方法

    成套方法 (repertoire method) 适用于线性递推式的方程组.

    用成套方法求解 `{ x_1 = alpha,; x_(2n) = 2 x_n + beta, n ge 1; x_(2n+1) = 2x_n + gamma, n ge 1 :}`

    设通解为 `x_n = alpha a_n + beta b_n + gamma c_n`, 将 `x_n = 1` 代入原方程组得 `{1 = alpha; 1 = 2 + beta; 1 = 2 + gamma:}`, 从而 `(alpha, beta, gamma) = (1, -1, -1)`. 代入通解有 `1 = a_n - b_n - c_n`. 类似地, 再将 `x_n = n` 代入原方程组, 得到 `(alpha, beta, gamma) = (1, 0, 1)`, 然后代入通解有 `n = a_n + c_n`. 最后, 取 `(alpha, beta, gamma) = (1, 0, 0)`, 代入通解有 `x_n = a_n`, 代入原方程组有 `{a_1 = 1; a_(2n) = 2a_n; a_(2n+1) = 2a_n:}`, 用归纳法可以证明其解为 `a_n = 2^m`, 其中 `2^m le n lt 2^(m+1)`. 现在联立 `{a_n-b_n-c_n = 1; a_n+c_n = n; a_n = 2^m:}` 最终解为 `x_n = alpha 2^m + beta(2^(m+1)-1-n) + gamma(n-2^m)`.

    线性递推式

    一个例子: Fibonacci 数列

    求 Fibonacci 数列 `f_n = { 0, if n = 0; 1, if n = 1; f_(n-1) + f_(n-2){::}, if n ge 2; :}` 的通项公式.

    待定系数法化为等差/等比数列 设 `f_n = (varphi + psi) f_(n-1) - varphi psi f_(n-2)`, 则 `varphi, psi` 应是方程 `x^2 - x - 1` 的两根, 不妨令 `varphi, psi = (1 +- sqrt 5)//2`. 上式变形得到 `{ f_n - varphi f_(n-1) = psi(f_(n-1) - varphi f_(n-2)); f_n - psi f_(n-1) = varphi(f_(n-1) - psi f_(n-2)); :}` 于是 `{f_n - varphi f_(n-1)}`, `{f_n - psi f_(n-1)}` 皆为等比数列. 由等比数列的通项公式有: `f_n - varphi f_(n-1) = psi^(n-1) (f_1 - varphi f_0) = psi^(n-1)`,
    `f_n - psi f_(n-1) = varphi^(n-1) (f_1 - psi f_0) = varphi^(n-1)`.     注意 `varphi psi = -1`, 由上式得到 `{ psi f_n + f_(n-1) = psi^n; varphi f_n + f_(n-1) = varphi^n; :}` 解得 `f_n = 1/sqrt 5 (varphi^n - psi^n)`.

    生成函数法 记 `F(x) = sum_(n=0)^oo f_n x^n`, 于是 `F(x) = 0 + x + sum_(n=2)^oo (f_(n-1) + f_(n-2)) x^n` `= x + sum_(n=1)^oo f_n x^(n+1) + sum_(n=0)^oo f_n x^(n+2)` `= x + x F(x) + x^2 F(x)`. 解得 `F(x) = x/(1-x-x^2)`. 记上式分母的两个零点的相反数为 `varphi, psi = (1 +- sqrt 5)//2`, 则 `varphi psi = -1`. 通过分解分式, `F(x) = 1/sqrt 5(psi/(x + psi) - varphi/(x + varphi))` `= 1/sqrt 5(1/(1-varphi x) - 1/(1-psi x))` `= 1/sqrt 5 sum_(n=0)^oo [(varphi x)^n - (psi x)^n]`. 于是 `f_n = 1/sqrt 5(varphi^n - psi^n)`.

    特征根法 将 `f_n = lambda^n` (`lambda != 0`) 代入递推公式, 得 `lambda^n = lambda^(n-1) + lambda^(n-2)`, 由 `lambda != 0`, 有 `lambda^2 = lambda + 1`. 这个二次方程的两根记为 `varphi, psi = (1 +- sqrt 5)//2`, 由线性叠加原理, 该差分方程的通解为 `f_n = c_1 varphi^n + c_2 psi^n`. 再代入初值条件 `f_0 = 0`, `f_1 = 1`, 有 `{ c_1 + c_2 = 0; varphi c_1 + psi c_2 = 1; :}` 解得 `c_1, c_2 = +- 1/sqrt 5`. 于是 Fibonacci 数列的通项公式是 `f_n = 1/sqrt 5 (varphi^n - psi^n)`.

    注意 `|psi| = |1-sqrt 5|//2 lt 1`, 从而对 `n = 0, 1, 2...` 都成立 `|psi^n/sqrt 5| lt 1/sqrt 5 lt 1/2`. 我们推出: `f_n` 等于最接近 `varphi^n/sqrt 5` 的整数.

    `varphi = (1+sqrt 5)//2` 即是著名的黄金比例, 它定义为方程 `x^2 = 1 + x` 的正根. 利用通项公式容易计算, Fibonacci 数列前后项的比值 `f_(n+1)//f_n` 的极限是 `varphi`, 因此它在某种意义上是对等比数列 `varphi^n/sqrt 5` 的逼近.

    现在我们不用通项公式, 只借助递推式来推导极限 `lim_(n to oo) f_(n+1)//f_n`. 记 `x_n = f_(n+1)//f_n`, 则 `x_1 = 1`, `quad x_n = (f_n + f_(n-1))/(f_n) = 1 + 1/x_(n-1)`. 假设 `x_n to a`, 则 `a` 满足 `a = 1 + 1/a`. 显然 `a` 是正数, 由上式解得 `a = varphi = (1+sqrt 5)//2`. 下证极限存在. 注意到 `x_n ge 1`, `n = 1, 2, cdots`, 有 `|x_n - a| = |(1 + 1/x_(n-1)) - (1 + 1/a)|` `= |1/x_(n-1) - 1/a|` `= |x_(n-1) - a|/(a x_(n-1))` `le 1/a |x_(n-1) - a|` 由 `1/a lt 1` 知 `|x_n - a| to 0`, 即 `x_n to a`.

    在 Fibonacci 数列的生成函数 `F(x) = x/(1-x-x^2)` 中令 `x = 0.1` 得 `F(0.1) = 10/89`. 于是 
      0.01
+ 0.001
+ 0.0002
+ 0.00003
+ 0.000005
+ 0.0000008
+ 0.00000013
+ 0.000000021
+ 0.0000000034
+ 0.00000000055
+ 0.000000000089
+ 0.0000000000144
+ ...
= 1/89

    设有两种译码规则 0 = A 和 00 = B, 现收到一串 `n` 个 0 的序列, 问有几种不同的解释. 事实上, 设这个数为 `x_n`, 则 `x_1 = 1`, `x_2 = 2` (因为两个 0 可以解释为一个 B, 也可以解释为两个 A). 设 `n ge 3`, 考虑 `n` 个 0 的序列, 若将第一个 0 解释为一个 A, 则余下 `n-1` 个 0 有 `x_(n-1)` 种解释; 若将前两个 0 解释为一个 B, 则余下 `n-2` 个 0 有 `x_(n-2)` 种解释. `x_n = x_(n-1) + x_(n-2)`, `quad n ge 3`. 注意 `x_1 = f_2`, `x_2 = f_3`, 所以 `x_n = f_(n+1)`.

    用数学归纳法可证 `f_(n+1) f_(n-1) - f_n^2 = (-1)^n`, 反之, 若数列 `{x_n}` 满足 `x_1 = x_2 = 1` 和 `x_(n+1) x_(n-1) - x_n^2 = (-1)^n`, 则 `x_n = f_n`.

    常系数齐次线性递推式

    我们看到, 求解 Fibonacci 数列通项公式的所有方法中, 特征根法计算量最小, 且抓住了问题的本质. 这一方法很容易推广到一般的常系数线性递推式, 形如: `sum_(i=0)^k a_i x_(n+i) = 0`, `quad a_k != 0`. 将 `x_n = lambda^n` (`lambda != 0`) 代入方程即得到关于 `lambda` 的一元 `k` 次方程 `sum_(i=0)^k a_i lambda^i = 0`, 称为递推式的特征方程, 方程左边的 `k` 次多项式称为特征多项式, 它的根称为特征根. 事实上, 方程有 `k` 个线性无关的特解 `x_n = n^j lambda^n`, `quad j = 0, 1, cdots, m-1`, 其中 `lambda` 取遍所有不同的特征根, `m` 是 `lambda` 的重数. 我们来说明它们确实是方程的解, 即证 `sum_(i=0)^k a_i (n+i)^j lambda^(n+i) = 0`. 这只需证明下面的引理:

    设 `lambda != 0` 是多项式 `f(x) = sum_(i=0)^k a_i x^i` 的 `m` 重根 (`m ge 1`), 那么 `sum_(i=0)^k a_i (n+i)^j lambda^i = 0`, `quad j = 0, 1, cdots, m-1`.

      当 `j = 0` 时, 显然 `sum_(i=0)^k a_i lambda^i = 0`. 下面证明分两步:
    1. 先证 `lambda` 是 `f_j(x) = sum_(i=0)^k a_i i^j x^i` 的 `m-j` 重根, `j = 0, 1, cdots, m-1` (约定 `0^0 = 1`). `j = 0` 的情形, 条件已经给出. 现在设 `j gt 0`, 且 `lambda` 是 `f_(j-1)(x) = sum_(i=0)^k a_i i^(j-1) x^i` 的 `m-j+1` 重根, 则它是其导式 `f_(j-1)'(x) = sum_(i=1)^k a_i i^j x^(i-1)` 的 `m-j` 重根, 从而是 `f_j(x) = sum_(i=0)^k a_i i^j x^i` `= sum_(i=1)^k a_i i^j x^i` `= x f_(j-1)'(x)` 的 `m-j` 重根 (这是因为 `lambda != 0`).
    2. 再设引理的结论对 `j-1` 成立, 则 `sum_(i=0)^k a_i (n+i)^j lambda^i` `= n sum_(i=0)^k a_i (n+i)^(j-1) lambda^i` ` + sum_(i=0)^k a_i i (n+i)^(j-1) lambda^i` `= n * 0 + sum_(i=0)^k a_i lambda^i sum_(t=0)^(j-1) (j-1;t) i^(t+1) n^(j-1-t)` `= sum_(t=0)^(j-1) (j-1;t) n^(j-1-t) sum_(i=0)^k a_i i^(t+1) lambda^i = 0`.

    如果特征方程有 `m` 重零根 `lambda = 0`, 则对应的系数满足 `a_0 = a_1 = cdots = a_(m-1) = 0`, 且 `a_m != 0`. 此时令 `y_n = x_(n+m)`, 原方程就化为 `sum_(i=m)^k a_i x_(n+i)` `= sum_(i=0)^(k-m) a_(i+m) y_(n+i) = 0`. 由于 `a_m != 0`, 它的特征方程无零根.

    如果系数 `a_0, a_1, cdots, a_k` 为实数, 而特征方程有复根 `lambda = r"e"^("i" theta) = r(cos theta + "i"sin theta)`, 则在特征方程两端同时取其共轭, 容易证明 `bar lambda = r(cos theta - "i"sin theta)` 也是特征根, 且和 `lambda` 具有相同重数. 可以取两个实的特解 `1/2 n^j (lambda^n + {:bar lambda:}^n) = n^j r^n cos {:n theta:}`,
    `1/(2"i") n^j (lambda^n - {:bar lambda:}^n) = n^j r^n sin {:n theta:}`.     来替换对应的复数特解 `n^j lambda^n` 和 `n^j {:bar lambda:}^n`.

    设 `x^2-2x+6 = 0` 的两根为 `alpha, beta`, 求 `alpha^10 + beta^10`.

    构造线性递推式 `x_n = 2 x_(n-1) - 6 x_(n-2)`, 它的特征方程恰为 `x^2-2x+6 = 0`. 于是通解为 `x_n = c_1 alpha^n + c_2 beta^n`. 取 `c_1 = c_2 = 1`, 则 `x_10` 即为所求. 这时满足的初值条件为 `x_0 = alpha^0 + beta^0 = 2`, `x_1 = alpha + beta = 2`. 利用递推式迭代计算可得答案 `7552`.

    构造多项式 `f(x) = x^2-2x+6` 的友阵 `bm A = [0, -6; 1, 2]`, 它的特征多项式恰为 `f(x)`. 由线性代数的知识知道, `alpha^10+beta^10` 恰好为 `bm A^10` 的迹. 依次计算 `bm A^2, bm A^4, bm A^8`, 最后得到 `bm A^10 = [6816, **; **, 736]`. 所以答案是 `6816+736=7552`.

    [题源 brilliant.org] 求 `(sqrt(71)+1)^71 - (sqrt(71)-1)^71` 的个位数.

    将题目改写为 `(1+sqrt(71))^71 + (1-sqrt(71))^71`, 构造线性递推式 `x_n = 2 x_(n-1) + 70 x_(n-2)`, 它的两个特征根恰为 `1+-sqrt(71)`. 题目转化为求解 `x_71 (mod 10)`. 代入初值条件 `x_1 = 2`, 容易知道 `x_2 -= 4`, `x_3 -= 8`, `x_4 -= 6`, `x_5 = 2` `quad (mod 10)`. 由于 `71 -= 3 (mod 4)`, 所以 `x_71 -= 8 (mod 10)`.

    [题源 brilliant.org] 求 `|__ (sqrt 2+1)^6 __|`.

    记 `x_n = (1+sqrt 2)^n + (1-sqrt 2)^n`. 容易求得 `x_6 = 198`. 注意到 `(1-sqrt 2)^6 lt 1`, 所以答案是 `197`.

    常系数线性非齐次递推式: 比较系数法

      这类方程的一般形式如 `sum_(i=0)^k a_i x_(n+i) = f(n)`. 我们的结论是 (证明?):
    1. 当 `f(n) = P(n) lambda^n`, 其中 `P(n)` 是多项式: 方程有特解 `n^m Q(n) lambda^n`, 其中 `Q(n)` 是次数不超过 `del P(n)` 的多项式, `m` 是 `lambda` 在特征多项式中的重数, 如果 `lambda` 不是特征根, 则 `m = 0`.
    2. 当 `f(n) = r^n (A(n) cos n theta + B(n) sin n theta)`, 其中 `A(n)`, `B(n)` 是多项式: 方程有特解 `n^m r^n (P(n) cos n theta + Q(n) sin n theta)`, 其中 `P(n)`, `Q(n)` 是次数不超过 `max{del A(n), del B(n)}` 的多项式, `m` 是 `r"e"^("i" theta)` 在特征多项式中的重数, 如果 `r"e"^("i" theta)` 不是特征根, 则 `m = 0`.
    `f(n)` 方程的特解
    `P(n) lambda^n` `n^m Q(n) lambda^n`
    `r^n (A(n) cos n theta + B(n) sin n theta)` `n^m r^n (P(n) cos n theta + Q(n) sin n theta)`

    非线性递推式

    不动点法

    事实上, 前面所述的特征方程的方法, 也可以推广到非线性的递推式中. 一般地, 设 `x_(n+1) = f(x_n)`, 我们称方程 `x = f(x)` 的根为函数 `f(x)` 的不动点. 我们利用不动点来求解一些递推式.

      分式线性变换 设 `f(x) = (a x + b)/(c x + d)`, `a d - b c != 0`, `c != 0`. 又设 `{x_n}` 满足 `x_1 != f(x_1)`, `x_(n+1) = f(x_n)`, 且 `c x_n + d != 0`, `n = 1, 2, cdots`. 则
    1. `f(x)` 有两个不同的不动点, 即方程 `x = f(x)` 有两根 `p, q` 时, `{(x_n-p)/(x_n-q)}` 是以 `(a-c p)/(a-c q) = (c q+d)/(c p+d)` 为公比的等比数列; 特别当公比的模为 `1`, 辐角为 `2pi` 的有理数倍时, 该数列呈周期性重复.
    2. `f(x)` 只有一个不动点 `p` 时, `{1/(x_n-p)}` 是以 `c/(c p+d) = (2c)/(a+d)` 为公差的等差数列.
      容易计算, `f(x) - f(y) = ((a d-b c)(x-y))/((c x+d)(c y+d))`.
    1. 若方程 `x = f(x)` 有两个不同的根 `p, q`, 则 `(x_(n+1) - p)/(x_(n+1) - q)` `= (f(x_n) - f(p))/(f(x_n) - f(q))` `= (x_n-p)/(x_n-q) (c q+d)/(c p+d)`. 现在证明 `(a-c p)/(a-c q) = (c q+d)/(c p+d)`. 事实上, 交叉相乘并消去相同的项, 得到 `(a-d)c q - c^2q^2 = (a-d)c p - c^2p^2`. 但 `p, q` 是方程 `x = f(x)`, 即 `c x^2 - (a-d) x - b = 0` 的根, 所以上式左右两边都等于 `-b c`.
    2. 若方程 `x = f(x)` 只有一根 `p`, 由于 `c != 0`, 有 `p = (a-d)//(2c)`, 则 `c p+d = (a+d)//2`, 又此时判别式 `Delta = (a-d)^2 + 4b c = 0`, 有 `(c p+d)^2 = (a+d)^2/4 = ((a-d)^2+4a d)/4` `= a d-b c`. 于是 `1/(x_(n+1)-p)` `= 1/(f(x_n) - f(p))` `= ((c x_n+d)(c p+d))/((a d-b c)(x_n-p))` `= (c x_n+d)/((c p+d)(x_n-p))` `= 1/(x_n-p) + c/(c p+d)` `= 1/(x_n-p) + (2c)/(a+d)`.
    1. 现在解释定理对参数的要求. 显然如果 `a d-b c = 0`, `f(x) = (a x+b)/(c x+d)` 退化为常数. 如果 `c = 0`, 递推式退化为 `x_(n+1) = a/d x_n + b/d`, 为一线性递推式. 可以按照前例解之, 但也可以用不动点法. 取方程 `x = a/d x + b/d` 的根 `b/(d-a)`, 有 `x_(n+1) - b/(d-a) = a/d(x_n - b/(d-a))`, 从而得到一等比数列.
    2. 若 `f(x)` 的两个不动点是一对共轭复数 `p, q`, 通项公式中将含有复数, 但容易说明它其实是实数. 事实上, 记 `(x_(n+1)-p)/(x_(n+1)-q)` `= (x_1-p)/(x_1-q) ((a-c p)/(a-c q))^n := k`, 由于 `k` 的分子分母互为共轭, 所以 `bar k = k^-1`. 于是 `x_(n+1) = (p-k q)/(1-k)` `= ((p-k q)(1-k^-1))/((1-k)(1-k^-1))` `= ((p+q) - (k q+k^-1 p))/((1-k)(1-k^-1))`. 分子分母都是实数, 因此 `x_(n+1)` 是实数.

    `x_(n+1) = n/(n+2) x_n + 2/(n+2)`.

    这是非常系数的线性递推式. 注意到系数之和为 `1`, 显然特征方程 `x = n/(n+2) x + 2/(n+2)` 有不动点 `1`. 计算知 `x_(n+1) - 1 = n/(n+2) (x_n - 1)`. 递推, `x_n - 1 = (n-1)/(n+1) (n-2)/n (n-3)/(n-1)` `cdots 2/4 1/3 (x_1-1)` `= 2/(n(n+1)) (x_1-1)`.

    `x_(n+1) = 1/2(x_n + a/x_n)`, `a gt 0`.

    这是熟知的开平方根的牛顿迭代公式, 对所有正的初值都收敛到 `sqrt a`. 为求通项公式, 先求得不动点为 `+- sqrt a`, 再计算 `(x_(n+1) - sqrt a)/(x_(n+1) + sqrt a)` `= ((x_n^2+a)/(2x_n) - sqrt a)/((x_n^2+a)/(2x_n) + sqrt a)` `= ((x_n-sqrt a)/(x_n+sqrt a))^2`. 记 `y_n = (x_n-sqrt a)/(x_n+sqrt a)`, 则 `y_(n+1) = y_n^2`. 利用高次递推式的结果, `y_n = y_0^(2^n)`. 由此可得 `x_n` 的通项公式.

    三角换元法

    1. `x_(n+1) = (1+x_n)/(1-x_n)`;
    2. `x_(n+1) = (2 x_n)/(1-x_n^2)`;
    3. `x_(n+1) = 1/2 (x_n +- 1/x_n)`;
    4. `x_(n+1) = 4 x_n^3 - 3 x_n`, 其中 `x_0 in [-1, 1]`;
    5. `x_(n+1) = 2 x_n^2 - 1`.
    1. 令 `x_n = tan theta_n`, 则递推关系可以写为 `tan theta_(n+1) = (1+tan theta_n)/(1-tan theta_n)` `= tan(theta_n+pi/4)`. 从而 `theta_(n+1) = theta_n + pi/4 + k pi`, `k in ZZ`,
      `theta_n = theta_0 + (n pi)/4 + k pi`, `k in ZZ`,
      `x_n = tan(theta_0 + (n pi)/4)`.
    2. 令 `x_n = tan theta_n`, 并利用恒等式 `tan 2 theta = (2 tan theta)/(1-tan^2 theta)`.
    3. 令 `x_n = cot theta_n` (和 `"coth" theta_n`), 并利用恒等式 `cot 2theta = 1/2(cot theta - 1/(cot theta))`,
      `"coth" 2theta = 1/2("coth"theta + 1/("coth"theta))`.
    4. 令 `x_n = cos theta_n`, 并利用恒等式 `cos 3 theta = 4 cos^3 theta - 3 cos theta`.
    5. `x_0 in [-1, 1]` 时, 令 `x_n = cos theta_n`, 并利用恒等式 `cos 2 theta = 2 cos^2 theta - 1`. `x_0 gt 1` 时, 令 `x_n = cosh theta_n` 并利用恒等式 `cosh 2 theta = 2 cosh^2 theta -1`. `x_0 lt -1` 时, 有 `x_1 gt 1`, 即化为上一种情形.

    杂例

    [来自群友 我是的的我是] 反复投一枚硬币, 记投掷总次数为 `X`, 求出现连续 `n` 次正面时 `X` 的期望.

    用 `x_n` 表示达成连续 `n` 次正面平均所需的次数. 假设当前已经连续掷出 `n-1` 次正面, 再掷一次, 如果为正面, 则达成连续 `n` 次正面; 如果为背面, 则重新来过, 还需掷 `x_n` 次: `x_n = x_(n-1) + 1/2 + (1+x_n)/2`. 利用 `x_0 = 0` 解得 `x_n = 2^(n+1) - 2`.

    记投出正面为胜, 背面为负. 用 `x_k` 表示当前已经 `k` 连胜, 距离达成 `n` 连胜平均还需要玩的对局数. 讨论每种情况的胜负, 列出方程组 `{ x_0 = (1+x_1)/2 + (1+x_0)/2; x_1 = (1+x_2)/2 + (1+x_0)/2; cdots; x_(n-1) = (1+x_n)/2 + (1+x_0)/2; x_n = 0; :}` 方程组化为 `x_k = 2 x_(k-1) - x_0 - 2`, `quad k = 1, cdots, n`,
    `x_n = 0`.     将通解 `x_k = a 2^k + b` 代入得 `a 2^k + b = 2(a 2^(k-1)+b) - x_0 - 2`,
    `a 2^n + b = 0`.     即 `b = x_0 + 2`, `a = -(x_0+2) 2^-n`. 将它们代入 `x_0 = a + b` 最终解得 `E X = x_0 = 2^(n+1)-2`.