遞迴關係（三）（Recurrence relation-3）

遞迴關係（三）（Recurrence relation-3）
國立高雄大學應用數學系游森棚教授/國立高雄大學應用數學系游森棚教授責任編輯

連結：遞迴關係（二）

摘要：接下來的文章將探討幾個高中教材未提及、但是重要的遞迴關係。本篇先介紹「費波那契（Fibonacci）數」。

從這篇文章開始我們介紹幾個高中課本沒有提，但是重要的遞迴關係。首先介紹費波那契數。希望讀者讀完後可以體會到，遞迴關係有時候比一般項更重要。

$$(1)$$  費波那契（Fibonacci）數

愛好科普的師生可能都知道費波那契數。這個神奇的數列出現在各式各樣的領域中。為什麼會這樣？從遞迴公式也許可以看到本質上的原因：費波那契數所滿足的遞迴，是「二階線性遞迴」的最根本例子。也就是說，這一項由前兩項所決定，而且關係是最簡單的

$$a_{n}=a_{n-1}+a_{n-2}$$

當初始值取最簡單的 $$a_{1}=1,a_{2}=1$$，就是費波那契（Fibonacci）數

$$1,~1,~2,~3,~5,~8,~13,~21,~34,~55,…$$

當初始值取下一個簡單的 $$a_{1}=1,a_{2}=3$$（取 $$a_{1}=1,a_{2}=2$$ 沒意義，一樣得到費波那契數，足碼平移而已），就得到盧卡斯（Lucas）數

$$1,~3,~4,~7,~11,~18,~29,~47,~76,~123,…$$

既然根本，因此這兩個數列因此有非常多的性質。不只是科普的經典題材，更有太多的數學論文與這兩個數列有關。這數列也神奇地出現在自然界，比如向日葵的中心所成的兩個方向的螺旋線，條數會恰好是費波那契數的相鄰兩項。

下次到市場買鳳梨時，也記得數一數兩個方向的線條。我敢打包票會是費波那契數的相鄰兩項！要從數學問題引進費波那契數有很多選擇，比如：上樓梯每次可走一格或兩格的觀點，用科普書上的蜜蜂族譜觀點，或是西方世界第一位研究者採行的大兔子生小兔子觀點（以上都可以在網路上找到）。

高中學生容易接受的觀點應該是拼圖：

用 $$1\times 1$$ 和 $$2\times 1$$ 的拼片去拼 $$n\times 1$$ 的長條，有幾種方法？

想法是標準的遞迴思想：

假設一共有 $$a_n$$ 種方法。
從最左邊拼起，第一步只有兩種選擇：用 $$1\times 1$$ 或 $$2\times 1$$。
如果第一步用 $$1\times 1$$，剩下 $$n-1$$ 格，有 $$a_{n-1}$$ 法。
如果第一步用 $$2\times 1$$，剩下 $$n-2$$，有 $$a_{n-2}$$ 法。因此就有遞迴式

$$a_{n}=a_{n-1}+a_{n-2}$$

初始值為取 $$a_{1}=1,a_{2}=2$$（所以這還是費波那契數，但是足碼平移）。

但寫到這裡完全沒有說費波那契數（$$a_{n}=a_{n-1}+a_{n-2}$$ 且 $$a_{1}=1,a_{2}=1$$）的一般項 $$a_n$$ 到底是多少。因為這太尷尬了 — 這麼一個簡單的遞迴式和初始值，一般項卻相當驚人：

$$a_n=\displaystyle\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^n+\left(\frac{1-\sqrt{5}}{2}\right)^n \right)$$

不可能有人可以從 $$1,~1,~2,~3,~5,~8,~13,~21,~34,~55,…$$。猜出這個一般項。注意這個一般項展開後理論上充滿了根號，但是神奇的是最後會全部消掉，結果是一個整數。看了這個一般項公式，讀者應該能被第一篇文章中的說法說服：找遞迴相對容易，求一般項相當困難。

此外，從此例也可以看出遞迴關係有時是比一般項更本質的。在費波那契數中，如果凡事都要用一般項，未免太不方便也不自然。比如費波那契數有 $$a_{1}+a_{2}+…+a_{n}=a_{n+2}-1$$ 用遞迴關係證明是輕而易舉，用一般項試圖證明會是災難。

那到底一般項怎麼算出來的？這就要用到解線性遞迴的一般理論了。

連結：遞迴關係（四）

參考文獻：

1. Tucker, Applied Combinatorics, 5th edition, Wiley.
2. Brualdi, Introductory Combinatorics, 5th Edition, Pearson.

延伸閱讀：

1. 教育部，高中課程綱要(99)，2010。
2. Posamentier, Lehmann, The Fabulous Fibonacci Numbers, Prometheus Books, 2007.
3. Livio, The Golden Ratio: The Story of PHI, the World’s Most Astonishing Number, 2003.