從斐波那契數列看線性遞推數列通項公式的求法

在本月的每月一講欄目中，我們(men) 將以一個(ge) 新的視角，從(cong) 所謂的 Fibonacci（斐波那契）數列開始，明確線性遞推數列的通項公式的求法，以及高觀點下的特征方程、特征值的意義(yi) 。以下所有值均在複數範圍內(nei) 討論。

(p.s.矩陣部分內(nei) 容閱讀與(yu) 理解有困難的同學可以跳過Part2進入後麵的內(nei) 容~）

01·Fibonacci數列

首先，Fibonacci數列是一列不斷增加的正整數列，滿足

Fibonacci列具有豐(feng) 富的性質，它有一些重要的identities如，d'Ocagne's Identity:

在數論和組合學中的樹結構、生成函數等方麵它也有一些應用。

Fibonacci列的通項公式求法在數學上被稱為(wei) 特征方程法，而此方程在多數教科書(shu) 中總是不加解釋地使用：

由此方法得到的通項公式雖然正確（可以由Induction證明），但很難給高中生合理的解釋：為(wei) 什麽(me) 要用此特征方程、特征根？又是怎樣想到這樣的名詞和方法呢？

下麵，我們(men) 先給出k-階線性遞推的定義(yi) 和通項求法，再進一步解釋此方法。

02·k-階線性遞推

首先我們(men) 給出k-階線性遞推的定義(yi) 和通項求法：

證明：我們(men) 從(cong) 矩陣的角度來看特征方程

上述的做法對不熟悉矩陣的讀者極不友好，故我們(men) 再從(cong) 更高更抽象但代數上更簡單的角度回看 Fibonacci 數列，由此來更深入地理解 k-階線性遞推。

首先對於(yu) Fibonacci 數列，我們(men) 要回一個(ge) 很杠精的問題：

想回答這個(ge) 問題，需要你對數列改變一些約定俗成的看法。數列雖然長得像一列數，但它本 質上妥妥地是個(ge) 函數。

03·譜分解

說到這兒(er) ，一個(ge) 合格的數學學習(xi) 邏輯就是去研究解析延拓了，但我們(men) 決(jue) 定就此打住，來看更有技術含量的內(nei) 容：譜分解。為(wei) 此，我們(men) 要先建立線性空間、特征向量的概念。如果你是一個(ge) 新手，你大可以把他當做一個(ge) 沒有維數限製的歐氏空間。

下麵，我們(men) 將親(qin) 手構造一個(ge) 線性空間：

終於(yu) 我們(men) 可以給一個(ge) 平平無奇的定理

當然，我們(men) 還有一個(ge) 平平無奇的定理

上麵這兩(liang) 個(ge) 定理的證明請參見任一泛函分析講義(yi) 。

接下來，我們(men) 需要知道左移算子L，它已經超越了“很好”，甚至可以用“無敵”來形容，它在V上的特征值和特征子空間長得十分規整，換句話說，你要問：什麽(me) 數列是左移不變（等於(yu) 沒移）的？

答案隻有一個(ge) ：等比數列。

現在，你對Fibonacci數列是不是有更深刻的理解了呢~