递推关系是将数列中的项与同一数列的其他项联系起来的方程,所涉及的其他项通常具有较小的下标。配合适当的初始条件,递推关系可以通过逐项计算来定义一个数列。递推关系是递归的数学表达形式,可用于描述数值规律和分析算法。求解递推关系通常是指求出显式公式,或确定其解的增长规律。(discrete.openmathbooks.org)
定义与初始条件
一种常见的有限阶形式为
其中, 是给定的函数, 是固定的正整数。当 确实依赖于前 项处的那一项时,该递推关系的阶数为 。对于这种显式形式,只要 的每次求值都有定义,指定 就能唯一确定后续各项。没有初始条件的递推关系通常描述的是一族数列,而不是某一个数列。(ocw.mit.edu)
例如,
可得 。类似地, 可得 。这些例子说明了递归定义与闭式表达式之间的区别:前者引用先前的值,后者则直接根据下标计算某一项。可以用数学归纳法验证一个待证公式:先检查初始值,再证明该公式满足递推关系。(discrete.openmathbooks.org)
分类
如果递推关系中的数列项都以一次幂出现,且各项之间没有相乘,则称其为线性递推关系。一个 阶线性递推关系可写为
当各个 都与 无关时,称其为常系数递推关系。当 时,称其为齐次递推关系,否则称为非齐次递推关系。对于齐次线性递推关系,解的任意线性组合仍然是解。对于非齐次递推关系,其通解等于一个特解加上相应齐次递推关系的通解。(ocw.mit.edu)
变系数并不一定使递推关系成为非线性的。例如,阶乘满足 ,初始条件为 。这一递推关系是线性的,但其系数依赖于 。相比之下,含有 的表达式是非线性的。因此,线性与否、系数是否变化以及齐次与否,是彼此独立的分类标准。(ocw.mit.edu)
特征根法
对于常系数齐次线性递推关系
代入指数形式的试探解 ,可得到特征多项式
假设 ,如果其根 两两不同,则通解为
这些常数由初始条件确定,具体做法是求解一个线性方程组。如果根 的重数为 ,则它对应的解的部分为
这一方法同样适用于复数根。(math.libretexts.org)
斐波那契数列是一个典型的二阶例子:
其特征方程为 。记 、,由初始条件可得
虽然这个公式含有无理数,但当下标为非负整数时,它给出的值都是整数,因为它满足定义该数列的递推关系和初始条件。(math.libretexts.org)
生成函数
将递推关系乘以 ,再对其成立的所有下标求和,就能把数列中的下标移位转化为对 的代数运算。初始项必须单独处理。这个级数可以作为形式级数来使用,因此这些运算不必依赖于解析意义上的收敛性。(math.libretexts.org)
对于斐波那契数列,由递推关系可得
因此
将分母因式分解,并利用等比级数展开所得的各个分式,即可重新得到显式公式。更一般地,生成函数将关于带下标项的问题转化为关于代数表达式的问题,随后通过提取系数还原数列。(math.libretexts.org)
算法分析
在计算机科学中,递推关系往往用于描述时间复杂度,而不是单独的数值序列。一个采用分治法的算法,如果产生 个规模约为 的子问题,并且需要额外完成工作量为 的操作,通常会得到
还需指定基本情形和整数取整方式,才能完整定义这一递推关系。对于归并排序,通常采用的递推关系为 ,由此得到 的时间复杂度。二分查找对应的递推关系则为 ,由此得到 。(ocw.mit.edu)
求解方法包括反复展开、猜测一个界并用归纳法证明,以及对递归树上的工作量求和。主定理通过比较 与 ,可以处理许多具有上述分治形式的递推关系。它的各个情形都有特定的增长条件和正则性条件,因此并不是适用于任意递推关系的通用方法。在算法分析中,这类计算复杂性界往往比精确公式更有用,因为它们既能刻画增长规律,又能略去依赖于具体实现的常数。(live.ocw.mit.edu)
参考来源
- discrete.openmathbooks.org/dmoi3/sec_recurrence.htmldiscrete.openmathbooks.org
- ocw.mit.edu/courses/6-042j-mathematics-for-computer-science-spring-2015/mit6_04…ocw.mit.edu
- math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_…math.libretexts.org
- math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Combinat…math.libretexts.org
- math.libretexts.org/Bookshelves/Combinatorics_and_Discrete_Mathematics/Applied_…math.libretexts.org
- ocw.mit.edu/courses/6-1200j-mathematics-for-computer-science-spring-2024/mit6_1…ocw.mit.edu
- live.ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/1869dbf64…live.ocw.mit.edu