递推公式
dì tuī gōng shì
递推公式利用一个或多个前面的项,加上一个起始值,来定义数列中的每一项。
Definition
递推公式告诉你如何用前面的一项（或几项）求出数列的下一项，总是从给定的首项出发向前构建。等差数列使用 $a_n = a_{n-1} + d$，等比数列使用 $a_n = r \cdot a_{n-1}$，斐波那契数列使用前两项，$a_n = a_{n-1} + a_{n-2}$，且 $a_1 = 1$，$a_2 = 1$。严格地说，递推公式通过递推关系 $a_n = F(a_{n-1}, \ldots, a_{n-k})$ 及 $k$ 个初始条件来定义数列；具有常系数的线性递推可以用特征多项式求出封闭形式的解，若 $r_1, \ldots, r_k$ 是其互不相同的根，一般解为 $a_n = \sum C_i r_i^n$。
Example
设 $a_1 = 3$，$a_{n+1} = a_n + 5$：$3$，然后 $3+5=8$，然后 $8+5=13$，然后 $13+5=18$，生成 $3, 8, 13, 18, \ldots$。一个等比递推公式 $a_1 = 5$，$a_n = 3 \cdot a_{n-1}$ 给出 $5, 15, 45, 135, 405, \ldots$，不过用这种方法求 $a_{10}$ 需要先算出前面每一项。对于斐波那契数列，$a_n = a_{n-1} + a_{n-2}$，特征方程 $x^2 = x + 1$ 的根是 $\phi = (1 + \sqrt{5})/2$ 和 $\psi = (1 - \sqrt{5})/2$，从而给出比内公式 $a_n = (\phi^n - \psi^n) / \sqrt{5}$。
Key Insight
"递推"意味着"用自身来定义自身"：你需要一个起点和一条向前推进的规则，没有首项就无法开始；递推公式往往更容易写出，但要得到某一特定项，必须先算出前面的每一项，不像通项公式那样对较大的 $n$ 更高效。线性递推与特征多项式之间的联系，映照着线性常微分方程与其特征方程之间的联系，揭示了离散数学与连续数学之间深刻的结构性相似。