2022年AIME考前知识点分析（三）——递归与递推

各位同学新年好，临近Aime考试，春节给大家送福利，今天继续带来递归与递推的讲解。

递归又分为有限递归与无限递归，都会得到递推式，递推又分为两类，即单递推、双递推（历届考题中还没有出现过更高级别的递推式）。

最简单的单递推是以下类似的题目：

类型I：单向递归

对于递推题目，一是要把递推式写出来（最关键是要定义好第n项到底是谁），第二就是一定要写好首项。

（本题为高联-2012年题）

对于两边取极限的做法，是递归式里常用的一种方法，要根据具体的题目进行。（对于这两道题，AOPS的解析相对比较繁琐，因为没有抓到问题的本质）

单向递归在AMC中曾经考察过一道比较特殊的，是三个并列的单向递归（即非双递推递归），即：

并列的三个递推式中有某种循环关系，所以本质还是单递推的递归。

类型II：双向递归与递推

单向递归是指每一项仅与前一项有关；双向递归是指每一项与前一项以及下一项有关。我们先看二阶以及三阶的递推式解的问题，分为两类：带常数项与不带常数项的，即：

注意，两阶的递推，需要知道2个初始值；三阶的递推则需要3个初始值。

用特征方程求解的数列（里面不带常数项），又叫差分数列，AIME会考察的是二阶差分和三阶差分；在连续函数中，对应的是常微分方程。带常数项的，需要先进行换元，然后转化为差分数列即可。在下文数列的专项中，我们会再提一下。

在AMC中也会考察有限项的双向递归，有限的双向递归，一般会列出N元一次方程，然后求解方程即可。比如如下的这道经典的青蛙题：

AMC考察的有限项的双向递推。AIME也会考察类似的题目，再难一点的题目，则考察无限项的递归。我们先看一道去年AIME-I卷-12题：（AOPS的解析比较繁琐，没有抓住有限元的双向递归的本质。）

答案为：

即：16+3=19.

我们看一道相对复杂一点的题目：

AOPS里给出的解析是：

Iteratively…会让很多同学一口鲜血喷在电脑屏幕上，提供解析的这位同学还是没有弄好带常数项的双递推数列如何去做。这道题还是典型的“构造型的等差数列”（注意，当你求出来公比是1的时候，这个数列就是等差数列了，我们可以认为等差数列是一种特殊的差分数列，即公比为1）。另外就是三阶差分数列，需要知道三个初始条件，这道题的a1和a0之间的一个特殊值，所以可以求出来。另外这道题因为求第23项，而且递推式已经求出来，就没必要求通项公式了。

总之，做好递归题目，还是先学会数列的各种解法。

数列题，分为单递推，以及双递推，对于单递推来说，用的方法有：

① 差分数列（带常数项与不带常数项）：特征值方程法；

② 构造型等差数列或等比数列：待定系数法；

③ 三角换元法：tan(α+β)，sin(α+β)，tan(π/4+α)；

④ 周期数列法：带绝对值的数列、tan(π/4+α)、tan(π/6+α)写前6项

⑤ 裂项法（裂项相加然后相消）；

⑥ 等差与等比的混合数列求和（乘以公比，错位相减）

双递推数列的求法：

① 大部分的双递推需要消掉bn，然后变为单递推；

② 如果消不掉，则根据方程组思想来求解（参考点拨二里面的方程组求法）。

在AIME中，比较难的数列题，一共18道，归纳如下：

时间有限，无法讲解每道题，如果需要讲解的同学，可以扫码，进行PPT和相应的视频索取，也欢迎大家有更多的讨论。