2022年AIME考前知識點分析（三）——遞歸與遞推

各位同學新年好，臨(lin) 近Aime考試，春節給大家送福利，今天繼續帶來遞歸與(yu) 遞推的講解。

遞歸又分為(wei) 有限遞歸與(yu) 無限遞歸，都會(hui) 得到遞推式，遞推又分為(wei) 兩(liang) 類，即單遞推、雙遞推（曆屆考題中還沒有出現過更高級別的遞推式）。

最簡單的單遞推是以下類似的題目：

類型I：單向遞歸

對於(yu) 遞推題目，一是要把遞推式寫(xie) 出來（最關(guan) 鍵是要定義(yi) 好第n項到底是誰），第二就是一定要寫(xie) 好首項。

（本題為(wei) 高聯-2012年題）

對於(yu) 兩(liang) 邊取極限的做法，是遞歸式裏常用的一種方法，要根據具體(ti) 的題目進行。（對於(yu) 這兩(liang) 道題，AOPS的解析相對比較繁瑣，因為(wei) 沒有抓到問題的本質）

單向遞歸在AMC中曾經考察過一道比較特殊的，是三個(ge) 並列的單向遞歸（即非雙遞推遞歸），即：

並列的三個(ge) 遞推式中有某種循環關(guan) 係，所以本質還是單遞推的遞歸。

類型II：雙向遞歸與(yu) 遞推

單向遞歸是指每一項僅(jin) 與(yu) 前一項有關(guan) ；雙向遞歸是指每一項與(yu) 前一項以及下一項有關(guan) 。我們(men) 先看二階以及三階的遞推式解的問題，分為(wei) 兩(liang) 類：帶常數項與(yu) 不帶常數項的，即：

注意，兩(liang) 階的遞推，需要知道2個(ge) 初始值；三階的遞推則需要3個(ge) 初始值。

用特征方程求解的數列（裏麵不帶常數項），又叫差分數列，AIME會(hui) 考察的是二階差分和三階差分；在連續函數中，對應的是常微分方程。帶常數項的，需要先進行換元，然後轉化為(wei) 差分數列即可。在下文數列的專(zhuan) 項中，我們(men) 會(hui) 再提一下。

在AMC中也會(hui) 考察有限項的雙向遞歸，有限的雙向遞歸，一般會(hui) 列出N元一次方程，然後求解方程即可。比如如下的這道經典的青蛙題：

AMC考察的有限項的雙向遞推。AIME也會(hui) 考察類似的題目，再難一點的題目，則考察無限項的遞歸。我們(men) 先看一道去年AIME-I卷-12題：（AOPS的解析比較繁瑣，沒有抓住有限元的雙向遞歸的本質。）

答案為(wei) ：

即：16+3=19.

我們(men) 看一道相對複雜一點的題目：

AOPS裏給出的解析是：

Iteratively…會(hui) 讓很多同學一口鮮血噴在電腦屏幕上，提供解析的這位同學還是沒有弄好帶常數項的雙遞推數列如何去做。這道題還是典型的“構造型的等差數列”（注意，當你求出來公比是1的時候，這個(ge) 數列就是等差數列了，我們(men) 可以認為(wei) 等差數列是一種特殊的差分數列，即公比為(wei) 1）。另外就是三階差分數列，需要知道三個(ge) 初始條件，這道題的a1和a0之間的一個(ge) 特殊值，所以可以求出來。另外這道題因為(wei) 求第23項，而且遞推式已經求出來，就沒必要求通項公式了。

總之，做好遞歸題目，還是先學會(hui) 數列的各種解法。

數列題，分為(wei) 單遞推，以及雙遞推，對於(yu) 單遞推來說，用的方法有：

① 差分數列（帶常數項與(yu) 不帶常數項）：特征值方程法；

② 構造型等差數列或等比數列：待定係數法；

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

④ 周期數列法：帶絕對值的數列、tan(π/4+α)、tan(π/6+α)寫(xie) 前6項

⑤ 裂項法（裂項相加然後相消）；

⑥ 等差與(yu) 等比的混合數列求和（乘以公比，錯位相減）

雙遞推數列的求法：

① 大部分的雙遞推需要消掉bn，然後變為(wei) 單遞推；

② 如果消不掉，則根據方程組思想來求解（參考點撥二裏麵的方程組求法）。

在AIME中，比較難的數列題，一共18道，歸納如下：

時間有限，無法講解每道題，如果需要講解的同學，可以掃碼，進行PPT和相應的視頻索取，也歡迎大家有更多的討論。