遞推數列通項的一些解法

01-24

前言

嘛，為什麼會心血來潮寫這篇文章呢，因為之前想去找的時候沒有找到看著比較愉快的版本，所以就想著自己來寫一寫吧。

不過其實我本來是打算中秋和國慶那個長假慢慢碼的，但是，但是，但是，這個假期一下子就過去了的說QAQ，我也很無奈啊，所以就只好一拖再拖了咯，感覺自己真的是拖延症晚期的晚期了的說。

我在做題的時候經常發現壓軸或者說比較難的數列的題有很大一部分都是遞推數列求通項的問題，欺負我們沒有學線性代數不會特徵根是不是，(￢︿??￢☆)，大大的壞的出題人，哼。

有時候甚至數學老師都不能一眼看出來該怎麼做，其實我覺得有的時候壓軸題就是出題人拿來賣萌的，就是為了體現自己很厲害但是苦於不能去現場怒拿RANK1於是乎就出一道很難很難的題目來讓大家都做不出來，這種出題人最討厭了的說。那麼遇到這種情況我們該怎麼辦呢？

這裡就介紹一種基於特徵根來解遞推數列通項問題，我覺得這種方法大概是萬能的說。

不過特徵方程本質性的東西就留到以後再說吧，知乎的公式體驗是真的差

遞推數列的定義

我們學習數學第一件事是幹什麼？
講定義！

那麼我們就先來規範一下遞推數列的定義：如果一個數列 $left{ a_n ight}$ 的第n項 $a_n$ 由它的前面的若干項所確定，那麼該數列就是一個遞推數列。

那麼根據上述定義我們能夠發現一個很顯然的東西：等差數列和等比數列都是遞推數列，至於遞推式嘛，就留給聰明的讀者作為思考問題啦（什麼思考題嘛(╯‵□′)╯︵┻━┻，這麼水，大佬們如是說到）

一般地，如果：

$a_{n+k}=F(a_n,a_{n+1},...,a_{n+k+1})$ ①

即 $a_{n+k}$ 是 $a_n,a_{n+1},...,a_{n+k-1}$ 的函數，並且初值 $a_1,...,a_k$ 是確定的，那麼稱 $left{ a_n ight}$ 為k階遞推數列，①稱為 $left{ a_n ight}$ 的遞推公式。

特徵根定義

好的，到這裡我們就得到了遞推數列的定義了，那麼我們下面就來討論一些工具性的結論了哦，為什麼是工具性的而非本質呢？

因為本質的話會涉及到線性代數，所以考慮到受眾的問題（好吧我承認只是因為我懶得編輯公式而已，唔編輯公式真的好麻煩的說）所以我決定把這個本質放到附錄，其實附錄是什麼，附錄就是心情好的時候就寫一點的東西（看來是要有生之年了）。

我們稱滿足下述遞推公式的數列 $left{ a_n ight}$ 為常係數齊次線性遞推數列

$a_{n+k}=c_1a_{n+k-1}+c_2a{n+k-2}+...+c_ka_{n}$ ②

其中 $c_1,c_2,...,c_n$ 為常數

這個時候我們就會像變魔術一樣變出一個方程：

如果 $lambda$ 是方程 $lambda ^k=c_1lambda ^{k-1}+c_2lambda ^{k-2}+...+c_k$ ③的根，那麼數列 $left{ lambda^n ight}(n=1,2,...)$ 滿足遞推式②。

對於沒有重根這種美妙的情況，我們設k個根 $lambda_1,lambda_2,...,lambda_k$ ，那麼數列 $left{ A_1lambda_1^n,A_2lambda_2^n,...,A_klambda_k^n ight}(n=1,2,...)$ 是滿足②的數列，並且可以通過初始條件確定其中的係數，那麼這樣子我們就可以很輕鬆的得出數列通項啦，是不是很簡單。

與之相對的，我們還可以用母函數的方法來處理，那麼數列的母函數是長什麼樣子的呢？

一般地，對數列 $left{ a_n ight}(n=0,1,2,...)$ 我們稱下面的形式級數

$f(x)=a_0+a_1x+a_2x^2+...$ 為數列 $left{ a_n ight}$ 的母函數。

我們紙上談兵的聊了那麼久我們來實戰一下吧，來做幾道例題吧

例題

例題1：

已知數列 $left{ f_n ight}$ 滿足 $f_n=f_{n-1}+f_{n-2}(n=3,4,5,...)且 f_1=1,f_2=1$ ，求數列通項。

沒錯，這就是大名鼎鼎的斐波那契數列，也叫做兔子數列，為什麼叫做兔子數列呢，因為傳說啊，從前有座山，山裡有一窩兔子，這一窩兔子可不得了啊，它們...好吧，好像偏題了，我們繼續來看這題怎麼做。

在這裡只介紹兩種解法，分別對應特徵根和生成函數的解法。

首先，我們來介紹一下特徵根的解法，我們根據上面特徵根的定義易得特徵根 $lambda=frac{1pmsqrt{5}}{2}$ ，由此可得通解為 $f_n=eta_1lambda_1^n+eta_2lambda_2^n$ ，把兩個初始值帶進去就可以得到通項啦。

然後我們來考慮一下用母函數應該怎麼算呢？

首先，首先我們應該構造一下斐波那契數列的生成函數，也就是母函數，其實為什麼叫母函數呢？我也不知道，反正這兩個是同一個東西的說。

根據上述定義，它的母函數為： $f(x)=f_1x+f_2x^2+...+f_nx^n+...$ ，這個時候相信聰明的你們都會發現，似乎條件有點不夠哇，怎麼辦怎嘛辦，我們來仔細觀察一下條件都有什麼，好吧，似乎只有 $f_n=f_{n-1}+f_{n-2}$ 這一個條件欸，那我們就來試一下這個該怎麼做吧。

我們在觀察之後不難發現 $f_n對應的是x^n的係數$ ，那麼我們如果想要用到那僅有的條件我們就需要讓 $f_n,f_{n-1},f_{n-2}$ 對應同一個 $x^n$ ，所以我們獲得了一個方程 $f-xf-x^2f=xRightarrow f=frac{x}{1-x-x^2}$ ④ 到了這裡我們很容易就會想到如果可以把④式拆成冪級數的形式的話就可以得出通項了，於是我們設 $f=frac{a}{1-rx}+frac{b}{1-sx}Rightarrow f=frac{a+b-(as-br)x}{1-(r+s)x+rsx^2}$

然後就可以得到一個方程組：

解出這個方程我們進一步就可以得到： $f_x=frac{a}{1-rx}+frac{b}{1-sx}Rightarrow f_x=a(1+rx+r^2x^2+...)+b(1+sx+s^2x^2+...)$

然後我們斐波那契的通項公式就得出來啦，是不是也很快捷呢？

例題2：

已知數列 $left{ a_n ight}$ 滿足 $a_1=0,a_{n+1}=5a_n+sqrt{24a_m^2+1},n=1,2,...$ ，求此數列的通項。

嗯，我相信聰明的讀者讀到這裡一下子就把這道題切掉了對吧，那麼我們就直接公布答案吧： $a_n=frac{1}{4sqrt{6}}*((5+2sqrt{6})^{n-1}-(5-2sqrt{6})^{n-1})$

那麼這道題究竟該怎麼做呢？我們一眼望過去發現這道題不是線性齊次遞推，那我們就要想辦法把他變成線性遞推。

將等式兩邊移項平方後化簡可得 $a_{n+1}^2-10a_na_{n+1}+a_n^2=1$ ，我們用n+1替換n可得 $a_{n+2}^2-10a_{n+1}a_{n+2}+a_{n+1}^2=1$ ，由上面兩個式子可知 $a_n,a_{n+2}$ 均為 $x^2-10a_{n+1}x+a_{n+1}^2-1=0$ 的根，由題目我們不難得到這兩個根互不相同，由韋達定理可知