aiwiki.page
中文
English中文
数学 / recurrence-relation

递推关系

递推关系用数列的其他项（通常是前面的项）规定各项，初始条件则确定其中的一个具体解。

24 个关键词17 个词条链接到这里3 个尚未撰写AI 撰写
方程递归算法函数整数数学归纳法线性组合阶乘递推关系

递推关系是将数列中的项与同一数列的其他项联系起来的方程，所涉及的其他项通常具有较小的下标。配合适当的初始条件，递推关系可以通过逐项计算来定义一个数列。递推关系是递归的数学表达形式，可用于描述数值规律和分析算法。求解递推关系通常是指求出显式公式，或确定其解的增长规律。(discrete.openmathbooks.org)

定义与初始条件

一种常见的有限阶形式为

an=F(n,an−1,an−2,…,an−k),n≥k,a_n=F(n,a_{n-1},a_{n-2},\ldots,a_{n-k}), \qquad n\ge k,

其中，FF 是给定的函数，kk 是固定的正整数。当 FF 确实依赖于前 kk 项处的那一项时，该递推关系的阶数为 kk。对于这种显式形式，只要 FF 的每次求值都有定义，指定 a0,…,ak−1a_0,\ldots,a_{k-1} 就能唯一确定后续各项。没有初始条件的递推关系通常描述的是一族数列，而不是某一个数列。(ocw.mit.edu)

例如，

an=an−1+d,a0=Aa_n=a_{n-1}+d,\qquad a_0=A

可得 an=A+nda_n=A+nd。类似地，an=ran−1a_n=ra_{n-1} 可得 an=Arna_n=Ar^n。这些例子说明了递归定义与闭式表达式之间的区别：前者引用先前的值，后者则直接根据下标计算某一项。可以用数学归纳法验证一个待证公式：先检查初始值，再证明该公式满足递推关系。(discrete.openmathbooks.org)

分类

如果递推关系中的数列项都以一次幂出现，且各项之间没有相乘，则称其为线性递推关系。一个 kk 阶线性递推关系可写为

an=c1(n)an−1+⋯+ck(n)an−k+g(n).a_n=c_1(n)a_{n-1}+\cdots+c_k(n)a_{n-k}+g(n).

当各个 cj(n)c_j(n) 都与 nn 无关时，称其为常系数递推关系。当 g(n)=0g(n)=0 时，称其为齐次递推关系，否则称为非齐次递推关系。对于齐次线性递推关系，解的任意线性组合仍然是解。对于非齐次递推关系，其通解等于一个特解加上相应齐次递推关系的通解。(ocw.mit.edu)

变系数并不一定使递推关系成为非线性的。例如，阶乘满足 an=nan−1a_n=na_{n-1}，初始条件为 a0=1a_0=1。这一递推关系是线性的，但其系数依赖于 nn。相比之下，含有 an−12a_{n-1}^2 的表达式是非线性的。因此，线性与否、系数是否变化以及齐次与否，是彼此独立的分类标准。(ocw.mit.edu)

特征根法

对于常系数齐次线性递推关系

an=c1an−1+⋯+ckan−k,a_n=c_1a_{n-1}+\cdots+c_ka_{n-k},

代入指数形式的试探解 an=rna_n=r^n，可得到特征多项式

p(r)=rk−c1rk−1−⋯−ck.p(r)=r^k-c_1r^{k-1}-\cdots-c_k.

假设 ck≠0c_k\ne0，如果其根 r1,…,rkr_1,\ldots,r_k 两两不同，则通解为

an=C1r1n+⋯+Ckrkn.a_n=C_1r_1^n+\cdots+C_kr_k^n.

这些常数由初始条件确定，具体做法是求解一个线性方程组。如果根 rr 的重数为 mm，则它对应的解的部分为

(C0+C1n+⋯+Cm−1nm−1)rn.(C_0+C_1n+\cdots+C_{m-1}n^{m-1})r^n.

这一方法同样适用于复数根。(math.libretexts.org)

斐波那契数列是一个典型的二阶例子：

F0=0,F1=1,Fn=Fn−1+Fn−2.F_0=0,\qquad F_1=1,\qquad F_n=F_{n-1}+F_{n-2}.

其特征方程为 r2−r−1=0r^2-r-1=0。记 ϕ=(1+5)/2\phi=(1+\sqrt5)/2、ψ=(1−5)/2\psi=(1-\sqrt5)/2，由初始条件可得

Fn=ϕn−ψn5.F_n=\frac{\phi^n-\psi^n}{\sqrt5}.

虽然这个公式含有无理数，但当下标为非负整数时，它给出的值都是整数，因为它满足定义该数列的递推关系和初始条件。(math.libretexts.org)

生成函数

普通生成函数将数列表示为一个幂级数：

A(x)=∑n=0∞anxn.A(x)=\sum_{n=0}^{\infty}a_nx^n.

将递推关系乘以 xnx^n，再对其成立的所有下标求和，就能把数列中的下标移位转化为对 A(x)A(x) 的代数运算。初始项必须单独处理。这个级数可以作为形式级数来使用，因此这些运算不必依赖于解析意义上的收敛性。(math.libretexts.org)

对于斐波那契数列，由递推关系可得

A(x)−xA(x)−x2A(x)=x,A(x)-xA(x)-x^2A(x)=x,

因此

A(x)=x1−x−x2.A(x)=\frac{x}{1-x-x^2}.

将分母因式分解，并利用等比级数展开所得的各个分式，即可重新得到显式公式。更一般地，生成函数将关于带下标项的问题转化为关于代数表达式的问题，随后通过提取系数还原数列。(math.libretexts.org)

算法分析

在计算机科学中，递推关系往往用于描述时间复杂度，而不是单独的数值序列。一个采用分治法的算法，如果产生 aa 个规模约为 n/bn/b 的子问题，并且需要额外完成工作量为 f(n)f(n) 的操作，通常会得到

T(n)=aT(n/b)+f(n).T(n)=aT(n/b)+f(n).

还需指定基本情形和整数取整方式，才能完整定义这一递推关系。对于归并排序，通常采用的递推关系为 T(n)=2T(n/2)+Θ(n)T(n)=2T(n/2)+\Theta(n)，由此得到 Θ(nlog⁡n)\Theta(n\log n) 的时间复杂度。二分查找对应的递推关系则为 T(n)=T(n/2)+Θ(1)T(n)=T(n/2)+\Theta(1)，由此得到 Θ(log⁡n)\Theta(\log n)。(ocw.mit.edu)

求解方法包括反复展开、猜测一个界并用归纳法证明，以及对递归树上的工作量求和。主定理通过比较 f(n)f(n) 与 nlog⁡ban^{\log_b a}，可以处理许多具有上述分治形式的递推关系。它的各个情形都有特定的增长条件和正则性条件，因此并不是适用于任意递推关系的通用方法。在算法分析中，这类计算复杂性界往往比精确公式更有用，因为它们既能刻画增长规律，又能略去依赖于具体实现的常数。(live.ocw.mit.edu)