斐波那契數列通項公式是怎樣推導出來的？

12-15

請問斐波那契數列通項公式是怎樣推導出來的？

( 這裡用 $F_n$ 代表斐波那契數列第 $n$ 項，且約定 $F_0=0$ )

設有一個矩陣 $M$ 使得 $egin{pmatrix}F_n\F_{n+1}end{pmatrix}=Megin{pmatrix}F_{n-1}\F_{n}end{pmatrix}$

設 $M=egin{pmatrix}AC\BDend{pmatrix}$ 就有 $egin{pmatrix}F_n\F_{n+1}end{pmatrix}=egin{pmatrix}AF_{n-1}+CF_{n}\BF_{n-1}+DF_{n}end{pmatrix}$

直接令 $A=0$ ，再令 $C=B=D=1$ ，得到 $M=egin{pmatrix}01\11end{pmatrix}$

把 $M$ 特徵分解，就可以求出 $egin{pmatrix}F_n\F_{n+1}end{pmatrix}$ 的通項式

$egin{pmatrix}F_n\F_{n+1}end{pmatrix}=Megin{pmatrix}F_{n-1}\F_{n}end{pmatrix}Rightarrowegin{pmatrix}F_n\F_{n+1}end{pmatrix}=M^negin{pmatrix}F_{0}\F_{1}end{pmatrix}Rightarrowegin{pmatrix}F_n\F_{n+1}end{pmatrix}=PD^nP^{-1}egin{pmatrix}0\1end{pmatrix}$

解特徵方程 $det(M-lambda I)=0$ 得到 $M$ 的特徵值 $lambda=frac{1pmdisplaystylesqrt{5}}{2}$

然後得到兩個的特徵向量 $egin{pmatrix}1\\displaystylefrac{1pmsqrt 5}{2}end{pmatrix}$

$egin{aligned}P^{-1}=egin{vmatrix}11\\displaystylefrac{1+sqrt 5}{2}displaystylefrac{1-sqrt 5}{2}end{vmatrix}^{-1}egin{pmatrix}displaystylefrac{1-sqrt 5}{2}-displaystylefrac{1+sqrt 5}{2}\\-11end{pmatrix}^{ m T}\=egin{pmatrix}displaystylefrac{sqrt 5-1}{2sqrt 5}displaystylefrac{1}{sqrt 5}\\displaystylefrac{sqrt 5 + 1}{2sqrt 5}displaystyle-frac{1}{sqrt 5}end{pmatrix}end{aligned}$

$egin{aligned}F_n=egin{pmatrix}10end{pmatrix}egin{pmatrix}11\\displaystylefrac{1+sqrt 5}{2}displaystylefrac{1-sqrt 5}{2}end{pmatrix}egin{pmatrix}displaystyleleft(frac{1+sqrt 5}{2} ight)^{n}0\0displaystyleleft(frac{1-sqrt 5}{2} ight)^nend{pmatrix}egin{pmatrix}displaystylefrac{sqrt 5-1}{2sqrt 5}displaystylefrac{1}{sqrt 5}\\displaystylefrac{sqrt 5 + 1}{2sqrt 5}displaystyle-frac{1}{sqrt 5}end{pmatrix}egin{pmatrix}0\1end{pmatrix}\=egin{pmatrix}10end{pmatrix}egin{pmatrix}11\\displaystylefrac{1+sqrt 5}{2}displaystylefrac{1-sqrt 5}{2}end{pmatrix}egin{pmatrix}displaystyleleft(frac{1+sqrt 5}{2} ight)^{n}0\0displaystyleleft(frac{1-sqrt 5}{2} ight)^nend{pmatrix}egin{pmatrix}displaystylefrac{1}{sqrt{5}}\\displaystyle-frac{1}{sqrt{5}}end{pmatrix}\=frac{2^{-n}}{sqrt 5}egin{pmatrix}10end{pmatrix}egin{pmatrix}11\\displaystylefrac{1+sqrt 5}{2}displaystylefrac{1-sqrt 5}{2}end{pmatrix}egin{pmatrix}displaystyleleft(1+sqrt 5 ight)^n\-displaystyleleft(1-sqrt 5 ight)^nend{pmatrix}\=frac{displaystyleleft(frac{1+displaystylesqrt{5}}{2} ight)^n-displaystyleleft(frac{1-displaystylesqrt{5}}{2} ight)^n}{displaystylesqrt{5}}end{aligned}$

所以

$F_n=frac{displaystyleleft(frac{1+displaystylesqrt{5}}{2} ight)^n-displaystyleleft(frac{1-displaystylesqrt{5}}{2} ight)^n}{displaystylesqrt{5}}$

相同的方法可以求形如 $A_{n}=c_1A_{n-1}+c_2A_{n-2}$ 遞推式的通項公式，

只要讓 $M=egin{pmatrix}01\c_2c_1end{pmatrix}$ ，剩下的步驟一模一樣

甚至還可以擴展到更高維度的矩陣求形如 $A_{n}=c_1A_{n-1}+c_2A_{n-2}+cdots+c_mA_{n-m}$ 的通項公式

當然，前提是 $M$ 非奇異，且擁有 $m$ 個線性無關的特徵向量

Mathematica代碼：

Simplify[{{1, 0}}.Transpose[Eigenvectors[{{0, 1}, {1, 1}}]].MatrixPower[DiagonalMatrix[Eigenvalues[{{0, 1}, {1, 1}}]], n].Inverse[Transpose[Eigenvectors[{{0, 1}, {1, 1}}]]].{0, 1}]

一些其他的關於斐波那契數列的東西：關於斐波那契數列 - 知乎專欄

感謝大家的點贊和評論！在這裡統一向各位說聲抱歉，我把這個解答稱為初等方法確實不夠嚴謹，看似初等的方法裡面實際上隱藏了並不初等的概念。確切地說，如果要正確理解下面這個等式

需要一些形式冪級數環的簡單知識（包括環的概念，環中可逆元的概念）。

因為考慮的是形式冪級數，在向形式變元 $x$ 代入具體的數之前並不牽涉收斂性問題，也無需使用泰勒展開等工具。因此，我仍然認為這是一個中學生可以接受的解答，再加上生成函數非常有價值，應該介紹給大家。

至於「初等」與「高等」之爭，我認為是一件好事，因為大家所熟知的初等數學裡，也有很多事情需要藉助高等數學的知識才能說清楚，而我們國家的中學數學教材與大學數學教材其實脫節很嚴重。但狀況並不應該如此，中學數學裡的內容有一些非常有趣而深刻的背景可以挖掘出來，而不是只教大家做題。最近在對這方面的內容做一個梳理和總結，系列文章

奇葩數學史 - 知乎專欄新鮮上線，希望大家多提意見！

以下是原答。

－－－－－－－－－－－－－－－－－－分割線－－－－－－－－－－－－－－－－－－－

純手工初等方法。記斐波那契數列第 $n$ 項為 $F_n$ ，則 $F_n=F_{n-2}+F_{n-1}$ 。

構造一個與 ${F_n}$ 有關的冪級數

這個函數被稱為斐波那契數列的生成函數，因為它的冪級數展開完全決定了 ${F_n}$ ，展開式中 $q^n$ 的係數就是斐波那契數列的第 $n$ 項。

對於一般數列的生成函數，我們暫且按下不表，先來看看有沒有辦法求這個特殊的 $F$ 。我們沒有別的選擇，唯一的條件是 $F_n=F_{n-1}+F_{n-2}$ ，這個等式應該能夠誘導出一個 $F$ 滿足的方程。

確實如此， $F_n$ 是 $q^n$ 的係數， $F_{n-1}$ 和 $F_{n-2}$ 則分別是 $q^{n-1}$ 和 $q^{n-2}$ 的係數，要想讓它們匹配在一起，就要想辦法讓它們對應同一個 $q^n$ 。這其實很容易辦到， $qcdot F$ 中 $q^n$ 的係數就是 $F_{n-1}$ ，同理， $q^2cdot F$ 中 $q^n$ 的係數就是 $F_{n-2}$ 。

於是， $F-qcdot F-q^2cdot F$ 中 $q$ 的所有高於 $1$ 的冪次前的係數都變成了 $0$ ，只剩下了 $q$ 。從而

如果你能把 $frac{q}{1-q-q^2}$ 展開成冪級數的形式，就自然求出了斐波那契數列的通項。

現在，讓我們回憶一個中學裡十分常用的技巧

這件事情的本質是將分母中的多項式作因式分解，將分母含有二次項的分式轉換成分母只含一次項，而分母只含一次項的分式很容易寫成冪級數

回到 $F=frac{q}{1-q-q^2}$ ，我們可以用待定係數法完成上面的過程，設

於是

我們得到一個四元方程組

這個方程組的難度只能稱為小嘍嘍級別，憑藉後兩個方程解出

代入到前兩個方程中即得 $a=frac{1}{sqrt{5}}$ ， $b=-frac{1}{sqrt{5}}$ 。

所以

蘊含了斐波那契數列的通項為

看起來不太像整數，但確實如此。

生成函數是處理數列的常用工具，是離散走向連續的橋樑，很多人們關心的離散信息都復刻在這樣一條DNA上。你們一定很奇怪我在定義 $F$ 時用的自變數是 $q$ 而不是 $x$ ，事實上我想通過這種方式提醒大家無窮展開的廣泛性，當 $q$ 被某種具有周期性的基本函數替代時，我們就得到了傅立葉展開。作為著名的費馬大定理證明核心的谷山－志村－韋伊猜想說的就是某種刻畫了橢圓曲線模 $p$ 點個數信息的生成函數可以與模形式的傅立葉展開對應起來，有機會再跟大家詳聊。

以上。

PS. 知乎公式編輯器的體驗真是差到令人髮指……

首先：
$a_{n+2}=a_{n+1}+a_{n}$
等價於

$a_{n+2}- frac{1-sqrt{5} }{2} a_{n+1}= frac{1+sqrt{5} }{2}left(a_{n+1}- frac{1-sqrt{5} }{2}a_{n} ight)$ ..................（1）
等價於
$a_{n+2}- frac{1+sqrt{5} }{2} a_{n+1}= frac{1-sqrt{5} }{2}left(a_{n+1}- frac{1+sqrt{5} }{2}a_{n} ight)$ ..................（2）

然後：

由（1）（2）遞推得
$a_{n+2}- frac{1-sqrt{5} }{2} a_{n+1}= left( frac{1+sqrt{5} }{2} ight) ^{n}*A$ ........................(3)

$a_{n+2}- frac{1+sqrt{5} }{2} a_{n+1}= left( frac{1-sqrt{5} }{2} ight) ^{n}*B$ ........................(4)
其中A,B為常數，由 $a_{1},a_{2}$ 確定

最後：
由(3)(4)解二元一次方程組得:

$a_{n+2}= left( frac{1-sqrt{5} }{2} ight) ^{n}*C+ left( frac{1+sqrt{5} }{2} ight) ^{n}*D$
其中C,D為常數，由 $a_{1},a_{2}$ 確定

解遞推方程

在此僅給出 @楊電量中公式（1）和（2）的由來：

由上可得具體的公式。
詳細請參考：斐波那契數列的通項公式推導

2x2遞推矩陣的特徵向量

高二剛學數列時證的
比較初等的一個方法吧

解差分方程
$x(n+2)=x(n+1)+x(n)$
$Z^{2} X(Z)=Z X(Z)+X(Z)$
$X(Z)=frac{1}{Z^{2}-Z-1} =frac{1}{(Z-frac{1+sqrt{5} }{2} )(Z-frac{1-sqrt{5} }{2} )} =frac{1}{sqrt{5}} (frac{Z}{Z-frac{1+sqrt{5} }{2}} -frac{Z}{Z-frac{1-sqrt{5} }{2}} )$
求逆Z變換
$xleft( n ight) =frac{1}{sqrt{5}}[(frac{1+sqrt{5} }{2} )^{n}-frac{1-sqrt{5} }{2} )^{n}]$

使用矩陣，然後解矩陣的特徵根，把矩陣對角化，然後這個問題就解決了。

考慮指數型生成函數，問題變成求解微分方程y""=y"+y，這個微分方程非常容易解～然後將解y(x)展成冪級數，x^n/n!前面的係數就是數列通項。

我有一個很初等的證法，但是渣機不知道怎麼弄數學符號。如果你沒有滿意當然答案不妨聯繫我。

1.高中的時候，我記得用最初等的待定係數法硬來。另外當時因為看過一些競賽書，所以知道有「不動點」來求解。
2.後來看過有一本書叫「數學女孩」，上面用的是「生成函數」的方法
3.大學裡學的是用特徵方程搞的

不過其他答主都答完了

生成函數大法好

特徵方程。
看劉佳汝的演算法入門的時候，有一道題是：有n層台階，一次只能上一層或者兩層，有多少種走到第n層台階的方法。
一上來我就遞歸了，也沒多想。反正就是f(n-1)+f(n-2)嘛～

然後……
有一次翻翻組合數學，有一道例題類似於上面的台階題。。題解打的我臉很疼，大意是an=an-1+an-2，轉化成a^n=a^(n-1)+a^(n-2),繼續a^2-a-1=0……看到這兒題主應該明白了吧。。不說了，都是淚，我高數真是學完了就扔了，當初我怎麼就沒想到呢，摔

建議題主先網上學習一下，另外組合數學很棒，可以讀讀。

運用連分數解答

可以使用矩陣相似對角化求解N階斐波那契數列.

特徵根方程啊，去百度搜都能搜到

1.特徵根法
2.猜想驗證(數學歸納法)

高等代數裡面有介紹。用特徵方程或正規方程

特徵根。