遞迴關係（一）（Recurrence relation-1）

遞迴關係（一）（Recurrence relation-1）
國立高雄大學應用數學系游森棚教授/國立高雄大學應用數學系游森棚教授

摘要：這是一系列關於「遞迴關係」文章的第一篇，本篇先介紹遞迴的基本概念，並簡述它在科學發展上的重要性。

九九的數學課綱（100 學年度高一開始使用）和以往相比有相當大幅度的更動，一個結構性的調整的是排列組合放到高一來教了。因此現在（100 年）是奇妙的一年，高一和高二同時在教排列組合，這一點可能要經過許多年師生才能調適好。

新的課綱中的總架構中的數學II（高一下學期）處理和離散數學相關的部分，第一部份為數列與級數，當作整個數學 II 的預備知識。在此部分中，課綱中特別強調了遞迴的概念，茲節錄如下：

本章節作為有限數學的先備知識，主要是讓學生發現數列的規律性，歸納成公式，並用數學歸納法加以證明。核心的公式為一階線性遞迴關係。（中略）。級數部分包括基本的求和公式與 $$\Sigma$$ 符號的操作。

可看出遞迴的確是新課綱中強調的思想之一。

由本文開始的一系列的短文章中，將用各種角度來介紹一下「遞迴」。文章內容不拘泥於高中的程度，而且高中課本有處理的都刻意跳過去以免重複，以期能帶領讀者看到更廣闊精彩的面向。在這第一篇文章中我們先談遞迴這件事的最根本概念，以及為什麼它在科學發展上是重要的。

遞迴講穿了就是：「每一項可以由前面幾項所決定」。所以兩個關鍵：第一個關鍵，決定出這一項的規則（這稱為遞迴關係 recurrence relation）。第二個關鍵，一開始必須有幾項是已經知道的（這稱為初始值 initial values）。

最簡單的例子是等差數列和等比數列。首項為 $$a$$ ，公差為 $$d$$ 的等差數列寫成遞迴就是

$$a_n=a_{n-1}+d$$，其中 $$a_1=a$$

首項為 $$a$$ ，公比為 $$r$$ 的等比數列寫成遞迴就是

$$a_n=ra_{n-1}$$，其中 $$a_1=a$$

更一般地說，用數學符號來說，一個完整的遞迴關係就是

1. $$a_{n}=F(a_{1},a_{2},…,a_{n-1})$$（即每一項由前面幾項所決定）
2. 其中一開始有某幾項是給定的。

應該可以體會這樣形容是非常空泛的 — 自由度太大了。沒錯，這也是遞迴之所以是有用的原因。因為在許多的科學研究上，我們一開始觀察到的不是真正想要求的整體結果，而是某個控制變因改變時所造成的後果。

讀者可以這樣想：若 $$a_n$$ 表示在時間為 $$n$$ 時的數量。則要觀察到 $$a_{n}=\frac{2}{3}a_{n-1}$$，比起一開始要得出 $$a_n$$ 的一般項，是相對容易的。反映在數列上，就是先知道兩相鄰項之間的關係，而非一般項的通式。

但請注意，我們熟悉的等差數列一般項是$$a_{n}=a+(n-1)d$$，等比數列一般項是$$a_{n}=ar^{n-1}$$。這兩個一般項公式完全從遞迴關係裡看不出來。換句話說，知道遞迴關係跟知道一般項是兩碼子事。

所以從遞迴關係到解出一般項中間有個很大的鴻溝。事實上，隨便寫個遞迴式要求出一般項，通常是困難的（跟隨便寫個式子要積分一樣地困難）。

因此遞迴之所以重要，是在於實際研究層面與科學素養的層面。在研究層面上，有相當多的研究依循這樣的模式：遞迴是好觀察的，所以遞迴關係容易得到，接著再想辦法用種種數學的工具與方法得到一般項或其他結果。在科學素養上，觀察本來就是一個最基本的功夫，因此在數學素養上，觀察兩項之間的變化是一個基本技能。落實到教材上，就是遞迴關係了。

連結：遞迴關係（二）

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

延伸閱讀：

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