單向遞歸是指每一項(xiàng)僅與前一項(xiàng)有關(guān)；雙向遞歸是指每一項(xiàng)與前一項(xiàng)以及下一項(xiàng)有關(guān)。我們先看二階以及三階的遞推式解的問題，分為兩類：帶常數(shù)項(xiàng)與不帶常數(shù)項(xiàng)的，即：
注意，兩階的遞推，需要知道2個(gè)初始值；三階的遞推則需要3個(gè)初始值。
用特征方程求解的數(shù)列（里面不帶常數(shù)項(xiàng)），又叫差分?jǐn)?shù)列，AIME會(huì)考察的是二階差分和三階差分；在連續(xù)函數(shù)中，對(duì)應(yīng)的是常微分方程。帶常數(shù)項(xiàng)的，需要先進(jìn)行換元，然后轉(zhuǎn)化為差分?jǐn)?shù)列即可。在下文數(shù)列的專項(xiàng)中，我們會(huì)再提一下。
在AMC中也會(huì)考察有限項(xiàng)的雙向遞歸，有限的雙向遞歸，一般會(huì)列出N元一次方程，然后求解方程即可。比如如下的這道經(jīng)典的青蛙題：
關(guān)于這道題的完整解析也可以加下方犀牛的微信號(hào)然后向我索取完整版的解析，這里我們不再贅述，AMC考察的有限項(xiàng)的雙向遞推。AIME也會(huì)考察類似的題目，再難一點(diǎn)的題目，則考察無限項(xiàng)的遞歸。我們先看一道去年AIME-I卷-12題：（AOPS的解析比較繁瑣，沒有抓住有限元的雙向遞歸的本質(zhì)。）
答案為：
即：16+3=19.
我們看一道相對(duì)復(fù)雜一點(diǎn)的題目：
AOPS里給出的解析是：
Iteratively…會(huì)讓很多同學(xué)一口鮮血噴在電腦屏幕上，提供解析的這位同學(xué)還是沒有弄好帶常數(shù)項(xiàng)的雙遞推數(shù)列如何去做。這道題還是典型的“構(gòu)造型的等差數(shù)列”（注意，當(dāng)你求出來公比是1的時(shí)候，這個(gè)數(shù)列就是等差數(shù)列了，我們可以認(rèn)為等差數(shù)列是一種特殊的差分?jǐn)?shù)列，即公比為1）。另外就是三階差分?jǐn)?shù)列，需要知道三個(gè)初始條件，這道題的a1和a0之間的一個(gè)特殊值，所以可以求出來。另外這道題因?yàn)榍蟮?3項(xiàng)，而且遞推式已經(jīng)求出來，就沒必要求通項(xiàng)公式了。
總之，做好遞歸題目，還是先學(xué)會(huì)數(shù)列的各種解法。
數(shù)列題，分為單遞推，以及雙遞推，對(duì)于單遞推來說，用的方法有：
① 差分?jǐn)?shù)列（帶常數(shù)項(xiàng)與不帶常數(shù)項(xiàng)）：特征值方程法；
② 構(gòu)造型等差數(shù)列或等比數(shù)列：待定系數(shù)法；
③ 三角換元法：tan(α+β)，sin(α+β)，tan(π/4+α)；
④ 周期數(shù)列法：帶絕對(duì)值的數(shù)列、tan(π/4+α)、tan(π/6+α)寫前6項(xiàng)
⑤ 裂項(xiàng)法（裂項(xiàng)相加然后相消）；
⑥ 等差與等比的混合數(shù)列求和（乘以公比，錯(cuò)位相減）
雙遞推數(shù)列的求法：
① 大部分的雙遞推需要消掉bn，然后變?yōu)閱芜f推；
② 如果消不掉，則根據(jù)方程組思想來求解（參考點(diǎn)撥二里面的方程組求法）。
在AIME中，比較難的數(shù)列題，一共18道，歸納如下：
時(shí)間有限，無法講解每道題，如果需要講解的同學(xué)，請(qǐng)聯(lián)系客服，進(jìn)行PPT和相應(yīng)的視頻索取，也歡迎大家有更多的討論。
