遞歸關係

設是一個序列。如果和序列中在它前面的若干項聯繫起來的一個關係式對所有大於等於某個整數n的整數n都是有效的，則稱這個關係式為遞歸關係(recursive relation)式。

如：設是一個序列，把該序列中的a和它前面的幾個和錯排數:，都是遞歸關係。

有時也稱遞歸關係式為差分方程。為了能從遞歸關係式計算出序列的每一項，必須知道序列開始的一個或幾個數，稱這樣的數為初始條件(initial condition)或初始值。

在許多情況下，得到遞歸關係式本身就是朝解決一個計數問題邁了一大步。即使不能從這個遞歸關係式很快地解出它的一般表達式，這也是相當不錯的了。這是因為採取逐步計算的方法可以得到序列各項的值。有些例子說明，沒有遞歸關係，計算的可能性根本就不存在。

遞歸關係有兩個比較著名的模型是：斐波那契序列和河內塔。

首先比較詳細地研究一個特殊的計數序列。這個序列是通過遞歸關係定義的。Pisa的Leonardo在1202年出版的名為“Liber Abacci(關於算盤)”一書中，提出了一個問題。該問題是如何確定一對兔子在一年裡生產多少對兔子?Leonardo，因Fibonacci(Filius Bonacci的縮寫)這個名字而更為人們所知道。

由Fibonacci提出的問題是，在一年的開始，將一對兔子放進圍場中。每個月，一對兔子中的雌性兔子生下新的雌雄各異的一對兔子。每對新兔子從第二個月起也是每月生產一對兔子。求一年後，圍場內兔子的總對數。

在第一個月內，所給定的一對兔子將生產一對新兔子，所以，在第一個月末，圍場中，將有兩對兔子。在第2個月內，唯有最初的一對兔子生產一對兔子，所以，在第2個月末，圍場中，將有3對兔子。在第3個月內，最初的一對兔子以及在第一個月所生產一對兔子都將各自生產一對兔子，所以，在第3個月末，圍場中，將有對兔子。對每個，令f(n)表示第n月初（等價地講，第月末）圍場中的兔子對的總數。有，而要計算的是f(13)。以下將f(n)的遞歸關係著手，可以容易地計算出f(13)。在圍場中的第月初的兔子對仍將在第n月初存在；另外，在第月初的就已存在的所有兔子對在第月內各生產一對新的兔子，於是在第n月初有對兔子，所以對有

利用這個關係和已經計算出的f(1)，f(2)，f(3)，f(4)值，可以得到

於是，一年後，圍城內有377對兔子。

如果令，於是.數序列f(0)，f(1)，f(2)，…滿足遞歸關係：對於有連同初始值被稱為斐波那契序列，並且稱序列中的數為斐波那契數。通過計算知道該序列是：

1，1，2，3，5，8，13，21，34，55，89，144，233，377，…

斐波那契序列有許多值得注意的性質。例如，斐波那契序列f(0)，f(1)，f(2)，…項的部分求和具有

對於，該公式簡化為，由於，所以顯然公式是成立的。

假設結論對任意的自然數時成立，則時，

由數學歸納法原理，得到證明。

現在需要做的事情是找出一個顯式表示斐波那契數。考慮斐波那契的對於遞歸關係，並略去f(0)和f(1)值。解決這個遞歸關係的一種方法是尋找形式為的一個解。它的第一項是。發現：滿足斐波那契遞歸關係當且僅當，或對於有。因為假設，所以得到是斐波那契遞歸關係的一個解當且僅當，或等價地講，當且僅當q是二次方程的一個根。該方程的根是

於是

是斐波那契遞歸函數的兩個解。由於這個遞歸關係式線性的（沒有f的不是1的方冪）齊次的（沒有常數項），所以導出

對於任意的常數和，是遞歸函數的解。

因為斐波那契序列有初始值，所以可以通過二元一次方程組來確定常數和。

時，得：

時，得：

解得：

概括起來，有以下定理

1.斐波那契數滿足公式

對

對於不同的處置，c和c將得到不同的值，f(n)的形式也有所不同。

2.沿著楊輝三角或Pascal三角形的對角線，從左向上的二項式係數之和等於斐波那契數。更確切地說，對於，第n斐波那契數f(n)滿足

其中

遞歸關係的另外一個很重要的模型是河內(Hanoi)塔。如下圖所示，1，2和3是三根直立的杆子．不妨設，開始時有n個圓盤依大小，自下而上套在桿1上，並且n個圓盤的半徑兩兩不同。現在按照三條規則，將桿1上的圓盤以原樣全部轉移到桿2或桿3上。這三條規則是：(1)每次只轉移一個圓盤；(2)整個轉移過程始終保持較小的在較大的上面的形式；(3)有而且僅有三根立桿1，2和3供使用。

問：最少要移動多少次，才能將桿1上的n個圓盤以原樣全部轉移到桿2或桿3上?

稍加分析不難看出，按照上述三條轉移規則，n個圓盤的轉移只能按下面的過程進行：第一步將桿1最上面的個圓盤，藉助桿2或桿3轉移到其中的一根上，不妨設轉移到桿2上。第二步將桿1的最下面的大圓盤轉移到桿3上．第三步藉助桿1和桿3，再把桿2上的n-1個圓盤轉移到那個套有最大圓盤的立桿3上，如下圖所示。

假設h表示轉移n個圓盤所需要的最少移動次數，那麼執行第一步需要h次，執行第二步需要一次，執行第三步需要h次，於是最少移動的總次數等於

並且初始條件。顯然，的表達式也是一個遞歸關係式。

在平面上有n條直線，假定沒有兩條直線是平行的，且沒有三條直線是共點的，問這個平面被這n條直線分隔成多少個區域?

解：令a表示n條直線將平面分割成的區域數。顯然，當時，由下圖可得，。

現在假定平面上已有n-1條直線把平面分割成a個區域，再在平面上插入第n條直線。它與原條直線相交，得到個不同的交點，這個點把第n條直線分成n段，從而產生了n個新區域。例如在上圖的(3)中平面省上三條直線將平面分割成7個區域，現加進第4條直線，與原三條直線相交，得3個交點，產生了4個新區域，如下圖陰影部分。因此，我們推知有如下的遞歸關係：

而