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

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

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

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

类型I：单向递归

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

（本题为高联-2012年题）

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

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

并列的三个递推式中有某种循环关系，所以本质还是单递推的递归。忘记这道题解法的同学可以看之前上课的笔记，或者向犀牛索取相应的这道题的解析。（AOPS的解析相对比较繁琐，因为没有抓到问题的本质）

类型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和相应的视频索取，也欢迎大家有更多的讨论。