##### 递推关系 - 递推关系 - **递推关系**是指一个[[序列]]中的每一项通过前面的若干项来[[递归]]定义的等式, 也是一种显式形式的[[差分方程]], 对于一个序列 $\{a_n\}$, 如果存在一个公式, 使得序列的某项 $a_n$​ 可以用[[映射]] $f$ 以及前面的若干项 $a_{n-1}, a_{n-2}, \dots, a_{n−k}​$ 来表示, 则称该序列满足递推关系, 其中 $k\leq n$ 是递推关系的阶数. 求解递推关系就是找到一个封闭公式来表达序列的通项. 主要包括[[线性递推关系]]和非线性递推关系 - $a_n​=f(a_{n−1}​)$ - $a_n​=f(a_{n−1}​,a_{n−2}​)$ - $a_n​=f(a_{n−1}​,a_{n−2}​,\dots,a_{n−k}​)$ >[!example]- 递推关系 > - 汉诺塔问题 > - 在汉诺塔问题中, 有三个杆子, 分别为 A, B 和 C. 初始时, 所有盘子按大小顺序叠放在杆 A 上, 目标是将这些盘子按相同的顺序移动到杆 C 上, 且在此过程中, 所有盘子必须遵循以下规则 > - 每次只能移动一个盘子 > - 每个盘子只能放在空杆上或比它大的盘子上 > - 假设有 $n$ 个盘子需要从杆 A 移到杆 C, 且使用杆 B 作为辅助杆. 可以通过递归的方式来解决这个问题, 递推关系可以通过分解问题得到 > - 进行 $T_{n−1}$ 次移动, 将较小的圆盘从最大的圆盘上取下来 > - 移动 $1$ 步来移动最大的盘子 > - 进行 $T_{n-1}$ 次移动, 将较小的圆盘放回到最大的圆盘上 > - $T_n​=2T_{n−1}​+1$ > - $T_n=2^n+1$