Recurrence relation 用一个数列前面的项来定义后面的项。当问题能自然地拆成一个规模更小的同类问题时，这种表达方式就很有用。

Recursive 与 explicit definitions

设 $(a_n)_{n\in\mathbb N}$ 是一个数列，读作“以自然数为下标的数列 $a_n$”。First-order recurrence 只用到前一项，需要给出两部分：

1. 一个 base case，例如 $a_0=c$；
2. 一条 recurrence rule，例如

$$a_n=F(n,a_{n-1})\qquad(n\ge1).$$

这里 $n$ 是下标，$a_{n-1}$ 是前一项，$F$ 是用来计算下一项的规则。

Explicit formula，也叫 closed form，直接根据 $n$ 给出 $a_n$：

$$a_n=\varphi(n).$$

符号 $\varphi$ 是希腊字母 phi，读作“fee”。Recurrence 让我们逐项往后算；closed form 则让我们直接算出任意下标对应的项。

例：factorials

Factorial 数列的 base case 是

$$0!=1$$

recurrence 是

$$n!=n(n-1)!\qquad(n\ge1).$$

例如，

$$\begin{aligned} 4! &=4\cdot3!\\ &=4\cdot3\cdot2!\\ &=4\cdot3\cdot2\cdot1!\\ &=4\cdot3\cdot2\cdot1\cdot0!\\ &=24. \end{aligned}$$

每代入一次，下标就减小一步，直到回到 base case。

例：geometric recurrence

假设

$$\begin{cases} a_0=c,\\ a_n=r a_{n-1}\qquad(n\ge1), \end{cases}$$

其中 $c$ 是初值，$r$ 是固定的乘数。展开前几项得到

$$a_1=cr, \qquad a_2=cr^2, \qquad a_3=cr^3.$$

由此得到 closed form：

$$\boxed{a_n=cr^n}.$$

检验一个候选 closed form 时，要同时检查它是否满足 base case 和 recurrence。这两项检查能确认它给出的确实是同一个数列。若乘数为零，初值仍按定义取给定值，之后各项都为零；不必通过零的零次幂来确定初值。

用 recurrence 计数：Tower of Hanoi

Tower of Hanoi 有三根柱子和 $n$ 个大小不同的圆盘。起初所有盘子都在第一根柱子上，最大的在最底下。目标是在遵守两条规则的前提下，把整叠盘子移到第三根柱子：

• 每次只能移动一个盘子；
• 不能把大盘放在小盘上面。

设 $h_n$ 表示移动 $n$ 个盘子所需的最少合法步数。没有盘子时不需要移动，因此 base case 是

$$h_0=0.$$

当 $n\ge1$ 时，可以这样完成：

1. 把上面的 $n-1$ 个盘子移到中间的柱子，需要 $h_{n-1}$ 步；
2. 把最大的盘子移到目标柱子，需要一步；
3. 把 $n-1$ 个小盘移到大盘上，再用 $h_{n-1}$ 步。

One legal solution for$n$disks

这个方法给出了一个可行的步数，也确实达到了最少步数。最大盘第一次移动前，所有小盘必须先移到另一根柱子上；最大盘最后一次移动到目标柱子后，所有小盘又必须从另一根柱子移到它上面。这两段各至少需要一次小规模问题的最少步数，而最大盘至少要移动一次。因此，

$$\boxed{h_n=2h_{n-1}+1}.$$

最初几项是

$$h_0=0, \quad h_1=1, \quad h_2=3, \quad h_3=7, \quad h_4=15, \quad h_5=31.$$

这些值都比相应的二的幂少一。要推导这个规律，在 recurrence 两边都加上 $1$：

$$h_n+1=2(h_{n-1}+1).$$

令 $b_n=h_n+1$，则 $b_0=1$，且 $b_n=2b_{n-1}$。这是 geometric recurrence，所以 $b_n=2^n$。因此，

$$\boxed{h_n=2^n-1}.$$

传统的 64 个盘子的版本需要

$$h_{64}=2^{64}-1 =18{,}446{,}744{,}073{,}709{,}551{,}615$$

步。若每秒移动一次，就需要约 $1.84\times10^{19}$ 秒，也就是 $5.85\times10^{11}$ 年。以宇宙年龄约 138 亿年估算，这大约是它的 42 倍。

Linear first-order recurrences

Linear first-order recurrence 的形式为

$$\begin{cases} a_0=c,\\ a_n=f(n)a_{n-1}+g(n)\qquad(n\ge1), \end{cases}$$

其中 $f(n)$ 和 $g(n)$ 是已知函数。$g(n)$ 称为 nonhomogeneous term，也叫 forcing term。

考虑

$$\begin{cases} a_0=3,\\ a_n=2a_{n-1}+n. \end{cases}$$

逐项计算得到

$$3,7,16,35,74,\ldots$$

为了求出 closed form，可以先求去掉 forcing term 后的 homogeneous solution，再找一个能满足完整 recurrence 的 particular solution。

Homogeneous recurrence

去掉 forcing term $g(n)$，得到对应的 homogeneous recurrence：

$$h_n=f(n)h_{n-1}.$$

在这个例子中，它是

$$h_n=2h_{n-1},$$

通解为

$$h_n=C\cdot2^n,$$

其中 $C$ 是任意常数。

Particular solution 是满足完整 recurrence 的某一个数列，这里暂不要求它满足指定的初值。设 $(p_n)$ 和 $(q_n)$ 是两个 particular solutions。把它们的等式相减，forcing term 就会抵消：

$$\begin{aligned} p_n-q_n &=f(n)p_{n-1}+g(n)-\bigl(f(n)q_{n-1}+g(n)\bigr)\\ &=f(n)(p_{n-1}-q_{n-1}). \end{aligned}$$

所以，任意两个 particular solutions 的差都满足 homogeneous recurrence。只要找到一个 particular solution $p_n$，每个解都能写成

$$\boxed{a_n=p_n+h_n}.$$

求 particular solution

对于

$$a_n=2a_{n-1}+n,$$

forcing term $g(n)=n$ 是一次多项式。因此先尝试同样形式的 particular solution：

$$p_n=An+B,$$

其中 $A$、$B$ 是待定常数。把这个形式代入 recurrence：

$$\begin{aligned} An+B &=2\bigl(A(n-1)+B\bigr)+n\\ &=(2A+1)n+(-2A+2B). \end{aligned}$$

比较 $n$ 的系数和常数项，得到

$$A=2A+1, \qquad B=-2A+2B.$$

因此，

$$A=-1, \qquad B=-2,$$

所以一个 particular solution 是

$$p_n=-n-2.$$

再加上 homogeneous solution：

$$a_n=-n-2+C\cdot2^n.$$

最后使用 base case $a_0=3$：

$$3=-2+C, \qquad C=5.$$

得到 closed form：

$$\boxed{a_n=5\cdot2^n-n-2}.$$

代入 $n=0$ 得到 $a_0=3$；再把公式代入 recurrence，也能验证 $a_n=2a_{n-1}+n$。

如何选择 trial form

下面选择 trial form 的方法适用于 constant-coefficient recurrence

$$a_n=r a_{n-1}+g(n),$$

其中 $r$ 是常数。在这种情况下，可以根据 $g(n)$ 的形式来选择 $p_n$：

例如，如果

$$g(n)=2^n+n^2 3^n,$$

先尝试

$$p_n=A2^n+(B+Cn+Dn^2)3^n.$$

还需要检查 trial form 是否与 homogeneous solution 重叠。如果重叠，代入时相关项会抵消，就无法匹配 forcing term。此时把 trial form 乘以 $n$；必要时乘以 $n$ 的更高次幂，直到消除重叠。若 $g(n)$ 是几项之和，只调整其中重叠的那一部分。

对这种 constant-coefficient 情况，完整步骤是：

1. 解对应的 homogeneous recurrence，得到 $h_n$；
2. 根据 $g(n)$ 的形式选择 trial $p_n$；
3. 把 $p_n$ 代入原 recurrence，解出待定系数；
4. 写出 $a_n=p_n+h_n$；
5. 用 base case 确定剩下的常数。

Higher-order recurrences

Order 为 $2$ 的 recurrence 可以用到前两项，因此需要两个 base cases。一个常见的例子是下标平移后的 Fibonacci sequence：

$$\begin{cases} f_0=1,\\ f_1=2,\\ f_n=f_{n-1}+f_{n-2}\qquad(n\ge2). \end{cases}$$

逐项计算得到

$$1,2,3,5,8,13,21,34,\ldots,$$

特别地，

$$f_{12}=377.$$

这个下标约定对应一种兔群模型：从一对已经能繁殖的兔子开始，并把第零个月已有的这一对也计入。Recurrence 适合按顺序计算各项，而 characteristic equation 能帮助我们直接写出 $f_n$ 的公式。

Characteristic equations

对 constant coefficients 的 homogeneous second-order recurrence，

$$a_n=C_1a_{n-1}+C_2a_{n-2},$$

可以借鉴一阶 geometric recurrence，尝试 exponential solution $a_n=x^n$。代入得到

$$x^n=C_1x^{n-1}+C_2x^{n-2}.$$

当 $x$ 非零时，两边除以 $x^{n-2}$，得到 characteristic equation。以下按真正二阶的情形讨论，即最早一项的系数 $C_2$ 非零；这样 characteristic roots 也不会为零。

$$x^2-C_1x-C_2=0.$$

对 Fibonacci recurrence，方程是

$$x^2-x-1=0.$$

它的两个根为

$$\varphi=\frac{1+\sqrt5}{2}, \qquad \bar\varphi=\frac{1-\sqrt5}{2}.$$

$\varphi$ 是 golden ratio。另一个根 $\bar\varphi$ 为负数，而且其 absolute value 小于一。

单独一个 exponential solution 通常不能同时满足两个独立的 base cases。若有两个不同的 characteristic roots，则每个解都是它们对应解的 linear combination：

$$f_n=A\varphi^n+B\bar\varphi^n.$$

两个 base cases 给出方程组

$$1=A+B, \qquad 2=A\varphi+B\bar\varphi.$$

解得

$$A=\frac{\sqrt5+3}{2\sqrt5}, \qquad B=\frac{\sqrt5-3}{2\sqrt5}.$$

因此，

$$\boxed{ f_n= \frac{\sqrt5+3}{2\sqrt5}\varphi^n + \frac{\sqrt5-3}{2\sqrt5}\bar\varphi^n }.$$

也可以写成

$$f_n=\frac{\varphi^{n+2}-\bar\varphi^{n+2}}{\sqrt5}.$$

由于 $\varphi>1$，而 $|\bar\varphi|<1$，长期增长由第一项决定；第二项的 absolute value 会逐渐减小，符号则不断交替。

Fibonacci growth from characteristic roots

• $f_n$recurrence values
• $A{\phi }^n$dominant-root term
• $B{\bar{\phi }}^n$conjugate-root correction

另一个 characteristic-root 例题

考虑

$$\begin{cases} a_n=a_{n-1}+2a_{n-2},\\ a_0=2,\\ a_1=7. \end{cases}$$

Characteristic equation 是

$$x^2-x-2=0,$$

两个根为 $r_1=-1$ 和 $r_2=2$。因此，

$$a_n=A(-1)^n+B2^n.$$

由 base cases 得到

$$2=A+B, \qquad 7=-A+2B,$$

所以 $A=-1$、$B=3$。Closed form 为

$$\boxed{a_n=-(-1)^n+3\cdot2^n}.$$

其他情况有什么变化

• Repeated root： 若 characteristic polynomial 只有一个非零 double root $r$，两个独立的 basis solutions 是 $r^n$ 和 $nr^n$，因此通解为 $(A+Bn)r^n$。
• Complex roots： 同样的方法也适用于 complex numbers；一对 conjugate roots 对应的解可以组合成实数的 sine-cosine 形式。
• Nonhomogeneous recurrence： 先解 homogeneous recurrence，再找一个 particular solution，然后相加：$a_n=h_n+p_n$。
• Order 大于二： 方法仍然适用，但 characteristic polynomial 的次数与 recurrence 的 order 相同。例如，

$$a_n=a_{n-1}+a_{n-2}-a_{n-3}$$

给出

$$x^3-x^2-x+1=0.$$

Characteristic polynomial 方法要求 recurrence 是 linear 且具有 constant coefficients。Variable coefficients 或 nonlinear terms 需要其他方法。若最早一项的系数为零，应先检查是否已经降阶，并单独处理初值，不要直接套用上面的非零根公式。