递推关系

递推关系用序列中较早的项来定义每一项，而生成函数则为求封闭形式解提供了一种系统方法。

Definition

递推关系是一个方程，它将序列的每一项表示为一个或多个前项的函数，并结合初始条件唯一确定该序列。

Scope

本主题涵盖常系数线性递推及其特征方程解、斐波那契数列和卡特兰数列的递推关系、分治递推关系，以及将递推关系转化为代数方程的生成函数方法。它连接了初等计数和增长率的分析研究。

Core questions

• 序列如何根据较早的项和初始值递归定义？
• 特征方程如何求解常系数线性递推关系？
• 生成函数如何将递推关系转化为可解的代数方程？
• 分治递推关系如何描述算法的运行时间？

Key concepts

• 常系数线性递推
• 特征方程
• 斐波那契数
• 卡特兰数
• 分治递推
• 生成函数解法

Key theories

特征方程法

常系数线性递推关系通过求解其特征多项式的根来解决；通解是那些根和初始条件决定的指数项的组合。

生成函数解法

将递推关系乘以一个形式变量并求和，可以将其转化为生成函数的代数方程，其展开式可以得到序列的封闭形式，例如卡特兰数和斐波那契数。

Clinical relevance

递推关系描述了递归算法的运行时间，其中分治递推关系和主定理给出了复杂性界限，并且它们模拟了离散动力学和种群过程。

History

斐波那契在13世纪提出的兔子问题给出了典型的递推关系；德·莫弗和欧拉发展了生成函数和特征根方法，这些方法至今仍是标准的求解技术。

Key figures

• Leonardo of Pisa (Fibonacci)
• Abraham de Moivre
• Eugene Catalan

Seminal works

• stanley2011

Frequently asked questions

什么是卡特兰数？

卡特兰数计算许多组合对象——平衡括号、三角剖分、二叉树——并满足一个二次递推关系，该关系可以通过生成函数求解，从而得到一个封闭的二项式形式。

为什么使用生成函数来解决递推关系？

它们将无限的递归方程族转换为一个单一的代数方程，从中可以一次性提取出每个项的封闭形式表达式。