函数方程：递归法

一句话

定义域是正整数集 ${\mathbb{N}}_{+}$ 的函数，就是一个数列：$f(1),f(2),f(3),\dots$。如果函数方程能把 $f(n+1)$（或 $f(n+2)$）用前面的值表示出来，它就是一个递推关系，加上初始值，$f$ 就被唯一确定了——剩下的事是求出通项。

第 1 站 · 一阶递推：累加

例 $f:{\mathbb{N}}_{+}\to {\mathbb{N}}_{+}$，$f(m+n)=f(m)+f(n)+mn$，$f(1)=1$。

令 $m=1$：$f(n+1)=f(n)+n+1$。这是一阶递推，相邻两项的差已知，逐项相加：

代回原方程：$\frac{(m+n)(m+n+1)}{2}=\frac{m(m+1)}{2}+\frac{n(n+1)}{2}+mn$ ✓。这和上一站的赋值法是同一套动作——赋值 $m=1$ 造出递推，递归法再把递推解完。

第 2 站 · 二阶递推：特征根

本站开头的例子。要点：

1. 特征方程 $x^2=px+q$ 有两个不同的根 $x_1,x_2$ 时，$f(n)=c_1{x}_1^n+c_2{x}_2^n$；
2. 有二重根 $x_1$ 时，$f(n)=(c_1+c_{2}n)x_1^n$；
3. 常数由 $f(1)$、$f(2)$ 解出，最后检验。

第 3 站 · 二重根

练一练