遞迴關係（二）（recurrence-relation-2）

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

連結：遞迴關係（一）

摘要：本篇介紹99課綱中提及的五個「一階遞迴公式」。

前面談到遞迴關係是指 $$a_{n}=F(a_{1},a_{2},…,a_{n-1})$$ 。一個簡單的情況是要決定目前這一項，只牽涉到前一項。即

$$a_{n}=F(a_{n-1})$$

這稱為「一階線性遞迴關係」。這一類遞迴式基本上是相對好處理的，正常的情況下一般項的解也能求得出來（當然也有不能算的）。這篇短文稍微介紹一下99課綱中特別提及的五個「一階遞迴公式」（足碼略有調整，但本質上是一樣的）。課綱提及這些遞迴式，不僅僅因為能算，而且也因為有根本的重要性。

首先是等差數列、等比數列。這兩種是最簡單的「有規則的數列」。

一個是一直加常數，一個是一直乘常數。這兩個數列都是一階遞迴數列。

$$(1)$$ $$a_{n}=a_{n-1}+d$$
這是等差數列，有一般項 $$a_{n}=a_{1}+(n-1)d$$ 。

$$(2)$$ $$a_{n}=ra_{n-1}$$
這是等比數列，有一般項 $$a_{n}=ar^{n-1}$$
用「一階遞迴數列」的角度來看等差數列和等比數列，是師生們非常不熟悉的觀點，可能要需要幾年才能習慣。

$$(3)$$ $$a_{n}=a_{n-1}+n$$
以數學的角度看，這是一階非齊次線性遞迴數列的最簡單例子（此處先不擬解釋這些名詞）。但這個遞迴關係是怎麼出現的呢？

考慮排成三角形陣列的單位圓，令 $$a_n$$ 表示要排成三邊長為 $$n$$（記為 $$n\times n\times n$$）的正三角形時所需要的圓數。顯然 $$a_{1}=1, a_{2}=3, a_{3}=6,…$$。對初學者而言，要求出 $$a_n$$ 當然沒這麼容易。但是要看出遞迴式是非常容易的：假設已經排完 $$8\times 8\times 8$$，要怎麼排成 $$9\times 9\times 9$$ ？很簡單，再多放一層九個圓。所以

$$a_{9}=a_{8}+9$$

一般來說，就有 $$a_{n}=a_{n-1}+n$$。

或是考慮這個例子：平面上 $$n$$ 條直線最多把平面分成幾塊區域？令 $$a_n$$ 表示答案。第 $$n$$ 條直線畫下去時，要出現最多塊表示要和前面每一條直線都相交，共有 $$n-1$$ 個交點，故會增加 $$n$$ 塊區域。同樣地也得到遞迴關係 $$a_{n}=a_{n-1}+n$$。

注意到兩個問題的遞迴關係相同但是答案不同。第一個問題初始值是 $$a_{1}=1$$，接著用數學方法可求出一般項是 $$a_{n}=\frac{n^{2}+n}{2}$$。但是直線分割平面問題初始值是 $$a_{1}=2$$，可求出一般項是 $$a_{n}=\frac{n^{2}+n+2}{2}$$。所以也可以看出遞迴關係的初始值是重要的。

第一個問題（排圓）是較為根本且自然的。因為由 $$a_{n}=a_{n-1}+n$$ 與 $$a_{1}=1$$ 可以迭代下去得
$$a_{n}=1+2+…+n$$，這剛好呼應了往後要講的 $$\Sigma$$ 求和公式。

$$(4)$$ $$a_{n}=a_{n-1}+n^2$$

讀到這裡讀者應該可以構造出這個遞迴關係的模型：這是把橘子疊成金字塔狀，疊了$$n$$ 層後一共要用多少橘子。每一層都是正方形，邊長往上遞減，每個橘子疊在下方四個橘子所形成的空隙上方。所以初始值是 $$a_{1}=1, a_{2}=5,a_{3}=14$$ 等等。

除了非齊次項 $$n^2$$ 是一個基本的二次多項式外，這個遞迴式為什麼非出現不可呢? 理由也是要呼應基本的 $$\Sigma$$ 求和公式。$$a_{n}=a_{n-1}+n^2$$，$$a_{1}=1$$ 迭代下去就是大家熟悉的。

$$(5)$$ $$a_{n}=n\cdot a_{n-1}$$

這個遞迴的重要是由於階層。如果初始值 $$a_{1}=1$$，則迭代下去就是 $$a_{n}=1\cdot 2\cdot 3\cdots n=n{!}$$

因此，以上五個一階遞迴的確是高中離散數學的根本。而且等差等比，$$\Sigma$$ 求和，階乘可以用一階遞迴的觀點一次統一起來。這樣的看法是相當有意思的。

連結：遞迴關係（三）

參考文獻

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

延伸閱讀

1. 教育部，高中課程綱要(99)，2010。