發刊日期 |
2009年12月
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
標題 | 線性遞迴關係之求解(上) |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
作者 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
關鍵字 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
檔案下載 | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
全文 |
1. 前言在數學上, 遞迴關係 (recurrence relation), 是一種遞迴地定義一個序列的方程式: 序列的每一項目定義為前面項的函數。 即某件事情發生的過程中, 又包含了與事情本身很類似的另一件事情, 而且這種包含關係可以無止盡地發展下去; 類似的概念即發展出一個非常重要的技巧, 稱為遞迴 (recursion)。 解這一類的問題通常可分成下列三個步驟:
數列是應用數學中經常出現的觀念, 而遞迴關係是研究數列的一個重要工具, 對於每一個數學分支如: 代數 、機率 、統計 、演算法 、計算科學 、電路分析 、動態系統 、 經濟 、生物及其他領域問題上都有許多應用, 特別是在組合學的計數問題上有許多重要的應用。 遞迴關係的研究可以追溯到 13世紀初著名的義大利數學家費布那西 (Fibonacci), $$ F_{n+2} = F_{n+1} + F_{n}, \quad n \geq 0, ~~F_{0} = 1, ~~F_{1} = 1 $$ 在他的經典著作『算盤書』 (研究算術代數的書籍) 中, 提出一個有趣的兔子問題: 『假設兔子出生以後兩個月, 每個月都能生小兔, 若每次不多不少恰好生一對 (一雌一雄)。 如果今天養了初生的小兔一對, 試問 $n$ 年後共可有多少對兔子 $F_n$ (如果生下的小兔都不死的話)? 』 後來發現其結果與一數列: 表1. 費布那西數列
有相當的關係, 而此數列更與一些大自然的變化息息相關, 這就是著名的『費布那西數列』。 有關費布那西數列更多詳細的介紹可參考網站 Fibonacci Numbers (Loy, 2007), 網站裡介紹許多費布那西數的特性及應用例子。 Kelley and Peterson (2000) 第一章先對遞迴關係的基本定義作簡單的介紹, 第二章介紹解遞迴關係會運用到的運算子, 第三章則將遞迴關係作詳細的分類介紹及應用和解題方法。 Grimaldi (1999) 將遞迴關係做一個 12頁的重點整理: 包括基本定義 、概念, 還有一些常見重要與計數相關的遞迴關係的例子, 及解遞迴關係常用的方法。 D'Angelo and West (1999) 第十二章將遞迴關係作基本的分類介紹。 Spiegel (1971) 第五章介紹遞迴關係的定義, 第六章則介紹應用的例子。 關於著名整數數列的遞迴關係及其相關性質, 請參閱世界上收錄最齊全的網路整數數列百科全書 "The On-Line Encyclopedia of Integer Sequences" (Sloane, 2007)。 本文的目的首先是要讓讀者熟悉遞迴關係的基本定義 、性質, 主要是介紹單一遞迴數列的求解方法, 舉出一些著名的例子, 針對可求解各種不同的形式: 齊次 、非齊次 、常係數等, 分別介紹其常用的解題方法。 遞迴關係是一個解決組合問題的急切工具, 一旦學會基本定義 、性質, 加上一些例子的輔助, 再將其應用, 即可解決許多數列相關的問題。 在第二節先介紹遞迴關係的基本定義及一些著名的例子。 第三節介紹一階線性遞迴關係的一些定理及基本解題方法和例題。 第四節介紹簡單的常係數線性遞迴關係, 分別對齊次和非齊次作探討, 然後再針對其特徵方程式的解為重根 、相異根 、共軛複根分別一一作介紹。 在許多應用軟體中也可以求解遞迴關係, 在附錄裡, 提出一個功能強大的軟體 Mathematica (Wolfram 2003), 介紹如何應用此程式求解遞迴關係式。 本文中的例子及習題的解答都已經過 Mathematica 的求解核對無誤。 2. 遞迴關係 (recurrence relation)在數學上, 遞迴關係式 (recurrence relation), 是一種遞迴地定義一個序列的方程式。 本節介紹遞迴關係的基本定義及一些著名的例子。 2.1. 定義首先介紹遞迴關係的基本定義。 定義 2.1: (遞迴關係) 假設 $\{a_n\}$ 為一個數列, 而對於 $n\ge n_0$, 每一個 $a_n$ 與它前面的項 $a_i$, $i\lt n$, 滿足方程式 $f(a_n, a_{n-1} ,\ldots)=0$ 稱為遞迴關係。 例 2.1: $a_n=2a_{n-1}+5$ 為一遞迴關係式。 例 2.2: $a_na_0+a_{n-1}a_1+\cdots+a_0a_n=1$ 為一遞迴關係式。 定義 2.2: ($k$ 階遞迴關係) 型如 $f(a_n,a_{n-1}, \ldots, a_{n-k})=0$ 的遞迴關係, 稱為 $k$ 階遞迴關係。 例 2.3: $a_n-10n^2a_{n-1}+21na_{n-2}-8a_{n-3}=0$ 是一個三階遞迴關係式。 定義 2.3: ($k$ 階線性遞迴關係) 型如 $c_0(n)a_n+c_1(n) a_{n-1}+\cdots+c_k(n)a_{n-k}=f(n)$, $c_0(n), c_k(n)\neq 0$ 的遞迴關係, 稱為 $k$ 階線性遞迴關係, 其他形式稱為非線性遞迴關係。 例 2.4: $a_{n+2}-2a_{n+1}+5a_n=0$ 是一個二階線性遞迴關係式。 例 2.5: $a_{n+2}-\displaystyle\frac{2a_{n+1}}{5a_n}=0$ 是一個二階非線性遞迴關係式。 定義 2.4: (齊次遞迴關係) 如果 $a_n=a_{n-1}=\cdots=0$ 是遞迴關係 $f(a_n, a_{n-1}, \ldots)=0$ 的一個解, 則稱 $f(a_n, a_{n-1}, \ldots)=0$ 為齊次遞迴關係, 其他形式稱為非齊次遞迴關係。 例 2.6: $a_{n+3}+2a_{n+2}-a_{n+1}-2a_n=0$ 是一個齊次三階遞迴關係式。 例 2.7: $a_{n+3}+2a_{n+2}-a_{n+1}-2a_n=9$ 是一個非齊次三階遞迴關係式。 定義 2.5: ($k$階常係數線性遞迴關係) 假設 $k\in{\mathbb N}=\{1, 2, \ldots\}, C_0, C_1, \ldots, C_k\in{\mathbb R}=\{x|-\infty\lt x\lt \infty\}$, 其中 $C_0, C_k\neq 0$, 令 $a_n, n\geq 0$, 為一數列, 則 \begin{equation} C_0a_n + C_1a_{n-1} + \cdots + C_ka_{n-k} = f(n), \quad n \ge k \end{equation} 稱為一 $k$ 階常係數遞迴關係式 (linear recurrence relation with constant coefficients of order $k$)。 若 $f(n)=0$, $n\geq k$, 稱此遞迴關係式為齊次 (homogeneous) 遞迴關係式, 否則稱為非齊次 (nonhomogeneous) 遞迴關係式。 例 2.8: $a_{n+2}+4a_{n+1}-12a_n=0$ 是一個常係數齊次二階遞迴關係式。 例 2.9: $a_{n+2}+4a_{n+1}-12a_n=2^n\beta$ 是一個常係數非齊次二階遞迴關係式。 例 2.10: $(n+2)a_{n+2}+4(n+1)a_{n+1}-12na_n=2^n\beta$ 是一個非常係數線性非齊次二階遞迴關係式。 2.2. 著名的例子接著我們來看一些著名的遞迴關係。 例 2.11: (等比數列) 公比為 $r$ 的等比數列 $\{a_n=a_0 r^n\}$ 滿足遞迴關係 \begin{equation} \label{eqnB:geo} a_n = ra_{n-1}, \quad n \ge 1 \end{equation} (\ref{eqnB:geo}) 是一個常係數齊次一階線性遞迴關係。 例 2.12: (等差數列) 公差為 $d$ 的等差數列 $\{a_n=a_0+nd\}$ 滿足遞迴關係 \begin{equation} \label{eqnB:ari} a_n = a_{n-1} + d, \quad n \ge 1 \end{equation} (\ref{eqnB:ari}) 是一個常係數非齊次一階線性遞迴關係。 例 2.13: (部分和數列) 數列 $\{a_n\}$ 的部分和數列 $\{s_n=\sum_{k=0}^n a_k\}$ 滿足遞迴關係 \begin{equation} \label{eqnB:ari1} s_n = s_{n-1} + a_n, \quad n \ge 1 \end{equation} (\ref{eqnB:ari1}) 是一個常係數非齊次一階線性遞迴關係。 例 2.14: (費布那西數列) 費布那西數列 $\{F_n \}$ 滿足遞迴關係 \begin{equation} \label{eqnB:Fib} F_{n+2} = F_{n+1} + F_n, \quad n \ge 0, ~F_0 = 1, ~F_1 = 1 \end{equation} (\ref{eqnB:Fib}) 是一個常係數齊次二階線性遞迴關係。 例 2.15: (Catalan 數列) Catalan數列 $\{C_n={2n\choose n}/(n+1)\}$ 滿足遞迴關係 \begin{equation} \label{eqnB:cat} C_n - C_0 C_{n-1} - C_1 C_{n-2} - \cdots - C_{n-1} C_0 = 0, \ n \ge 1 \end{equation} (\ref{eqnB:cat}) 是一個齊次非線性遞迴關係。 例 2.16: ($\sin^n x$ 的不定積分) 證明 $$ \int \sin^n x dx = - \frac{1}{n} \sin^{n-1} x \cos x + \frac{n-1}{n} \int \sin^{n-2} x dx $$ 其中 $n\gt 1 $是一個正整數。 證明: 利用部分積分, 設 $u=\sin^{n-1}x$ 且 $dv=\sin xdx=d(-\cos x)$。令 $$ I = \int \sin^n x dx = - \sin^{n-1} x\cos x + (n-1) \int \sin^{n-2} x\cos^2 xdx $$ 因為 $\cos^2 x=1-\sin^2x$, 所以 $I=-\sin^{n-1} x\cos x+(n-1)\int\sin^{n-2}x(1-\sin^2x)dx =-\sin^{n-1}x\cos x+(n-1)\int\sin^{n-2}xdx-(n-1)I$, 移項作整理即可得 $I=-\frac{1}{n}\sin^{n-1}x\cos x$ $+\frac{n-1}{n}\int\sin^{n-2}xdx$。 3. 一階線性遞迴關係 (first-order linear recurrence relation)一階線性遞迴關係是最簡單的遞迴關係, 它的一般項可以逐項代入求得一般通式。 3.1. 齊次一階線性遞迴關係(first-order homogeneous linear recurrence relation)齊次一階線性遞迴關係可以得到下面的公式解。 定理 3.1: (齊次一階線性遞迴關係) 設遞迴關係 \begin{equation} \label{eqnB:37446} a_{n+1} = g(n) a_n , \quad n \ge 0 \end{equation} 則 $a_n=(\prod_{k=0}^{n-1} g(k)) a_{0}$。 證明: 將關係式逐項代入即得 $a_n=g(n-1)a_{n-1}=g(n-1)(g(n-2)a_{n-2})=\cdots=(\prod_{k=0}^{n-1} g(k))a_{0}$, 故得證。$\Box$ $a_n$ 是否存在一個簡單的公式依賴於 $\prod_{k=0}^{n-1}g(k)$ 是否可以化簡。 一般而言如果 $g(k)=h(k)/h(k+1)$, 則 $\prod_{k=0}^{n-1} g(k)$ 可以化簡成 $h(0)/h(n)$, 在此情形下 $a_n=(h(0)/h(n))a_0$。 而定理 3.1 的證明可以利用變數代換 $b_n=h(n)a_n$化簡, (\ref{eqnB:37446}) 可以寫成 $b_n=b_{n-1}=\cdots=b_0$, 因此 $a_n=(h(0)/h(n))a_0$。特殊情形 $g(k)=\alpha$ 為一常數時, $h(k)$ 可以取成 $1/\alpha^k$。 當定理 3.1 中的 $g(n)$ 是一常數 $\alpha$ 時, (\ref{eqnB:37446}) 式為常係數齊次一階線性遞迴關係式, 前後項的比 $a_{n+1}/a_n=\alpha$。很明顯 $a_n=\alpha^na_{0}$, 因此 $\{a_n\}$ 是一個公比為 $\alpha$ 的等比數列。 例 3.1: 設 $a_n=4a_{n-1}$, $n\geq 1$, $a_0=6$, 求 $a_n$ 的一般解。 解: 將關係式逐項代入即得 \begin{eqnarray*} a_0 &=& 6 \\ a_1 &=& 4a_0 = 4(6) \\ a_2 &=& 4a_1 = 4^2(6) \\ &\vdots& \\ a_n &=& 4^n(6) \end{eqnarray*} 所以, $a_n=6(4^n)$ 是此遞迴關係式的一般解。$\Box$ 例 3.2: (排列) 設有 $n$ 個不同的字母, 求所有排列的個數。 解: 設排列的個數為 $a_n$, 考慮最後一個位置的排法, 他可以放任一個字母, 故有 $n$ 個放法。 而對於每一個情況前面 $n-1$ 個位置的排法有 $a_{n-1}$ 種。 由計數的乘法原理得 $a_{n}=na_{n-1}$, $n\ge 1$, $a_1=1$, 由定理 3.1 得 $a_n=n!$。$\Box$ 例 3.3: (生長模型) 某種細菌的繁殖率是每小時三倍遞增, 如果六小時之後有 $100000$ 隻細菌, 則請問最初是有多少隻細菌? 解: 設 $a_n$ 是 $n$ 小時後的細菌總數, 則 $a_{n+1}=3a_n$, $n\gt 0$, 所以 $a_n=a_0(3^n)$。 因此 $100000=a_0(3^6)$, 可求出 $a_0=137.174\cong 138$, 所以最初有 $138$ 隻細菌。 $\Box$ 3.2. 非齊次一階線性遞迴關係(first-order nonhomogeneous linear recurrence relation)非齊次一階線性遞迴關係可以得到下面的表達式。 定理 3.2: (非齊次一階線性遞迴關係) 設遞迴關係 \begin{equation} \label{eqnB:27802} a_{n+1} = g(n)a_n + f(n), \ n \ge 0 \end{equation} 則 $a_n=(\prod_{k=0}^{n-1}g(k))a_{0}+\sum_{k=0}^{n-1}(\prod_{m=k+1}^{n-1}g(m))f(k)$, 其中 $\prod_{m=n}^{n-1}g(m)\equiv 1$。 證明: 將關係式逐項代入即得 $a_n=g(n-1)a_{n-1}+f(n-1)=g(n-1)(g(n-2)a_{n-2}+f(n-2))+f(n-1)=\cdots =(\prod_{k=0}^{n-1}g(k))a_{0}+\sum_{k=0}^{n-1}(\prod_{m=k+1}^{n-1}g(m))f(k)$, 故得證。$\Box$ 當定理 3.2 中的 $g(n)$ 是一常數 $\alpha$ 時, (\ref{eqnB:27802}) 式為常係數非齊次一階線性遞迴關係式, $a_n=\alpha^na_{0}+\sum_{k=0}^{n-1}\alpha^kf(n-1-k)$。 例 3.4: 求解遞迴關係 $$ a_n = 2a_{n-1} + 3, \ n \ge 2, ~a_1 = 3 $$ 解: 根據定理 3.2, 逐項代入得 $a_n=2a_{n-1}+3=2(2a_{n-2}+3)+3=2^2a_{n-2}+(2+1)\cdot3=2^2(2a_{n-3}+3)+(2+1)\cdot 3 =2^3a_{n-3}+(2^2+2+1)\cdot 3=\cdots=2^{n-1}a_1+(2^{n-2}+2^{n-3}+\cdots+1)\cdot 3 =2^{n-1}\cdot 3+(2^{n-1}-1)\cdot 3=3(2^n-1)$, $n\geq 1$。$\Box$ 例 3.5: (河內塔問題 (Tower of Hanoi)) 根據一個古老的故事, 在遠東的某處有一個寺院, 裏面有一堆六十四個由大到小純金打造的盤子。 有一回, 這些盤子被疊在一起, 最大的盤子放在最底層。每一個盤子被穿了一個孔, 放在木樁 A 上。 另有兩根木樁 B 和 C。它們可以根據底下的規則由一個位置搬移到另外一個位置: (1) 一次只能移動一個盤子。 (2) 大盤子永遠不能放在小盤子的上面。 求最少次數從木樁 A 全部被搬到木樁 C。 解: 河內塔問題是法國數學家 Edouard Lucas 於 1883年提出的謎題。 首先我們先來討論幾個數量較少的情形: (首先將盤子由小到大依序編號為 $1, 2, \ldots, n$)
當 $n=1$: 直接把盤子從 A 移到 C, 次數只有一次。
當 $n=2$: 移動次序如下:
當$n=3$: 移動次序如下:
可參考圖 1:
當任意 $n$ 個盤子需搬移時, 我們可以歸納出一套規則。
設 $a_{n}$ 為搬 $n$ 個盤子所需搬動次數, $a_{n-1}$ 則是搬 $n-1$ 個盤子所需搬動次數。 很明顯 $a_0=0$, 而 $a_{n}=2a_{n-1}+1$。我們可以直接套用定理 3.2 得 $a_{n}=\sum_{k=0}^{n-1}2^k=2^n-1$, 或是將遞迴關係改寫成 $a_{n}+1=2(a_{n-1}+1)$, 可以得到 $a_{n}+1=2^n(a_{0}+1)=2^n$, 因此 $a_{n}=2^n-1$。 對一堆六十四個盤子而言, 其結果 $a_{64}\!=\!2^{64}\!-\!1\!\approx\! 1.84\!\times\! 10^{19}$ 次的搬動。 如果每秒能搬動一次, 大概需要 5850億年! 如果一部高速電腦每秒能計算出十億次的搬動, 也需要 585年!$\Box$ 關於河內塔的搬動的問題及其遞迴關係可參閱網站 "Towers of Hanoi Puzzle" (Zylla, 2007), 提供一個可以讓你自己親自動手有趣的河內塔 Java網頁。 而 "Tower of Hanoi Puzzle on the Web" (Kolar, 2007) 則列出一些網路上與河內塔相關的網頁連結 (包含故事 、搬動方法 、Java 、IE 等互動網頁)。 例 3.6: ($n$ 點圓分割) 設一個圓上有 $n$ 個點, 每兩點連成一直線, 且沒有任何三條線相交於一點, 試問由此 $n$ 個點所構成的線可劃分成多少塊區域? 解: $n=1, 2, \ldots, 6$ 個點圓分割見圖 2:
仔細觀察, 當圓周上每增加一點時, 數列 $a_1=1$, $a_2=2$, $a_3=4$, $a_4=8$, $a_5=16$, $a_6=31$, \begin{eqnarray*} a_2 &=& a_1 + 1 \\ a_3 &=& a_2 + 1 + 1 \\ a_4 &=& a_3 + 1 + 2 + 1 \\ a_5 &=& a_4 + 1 + 3 + 3 + 1 \\ a_6 &=& a_5 + 1 + 4 + 5 + 4 + 1 \end{eqnarray*} 這有點像巴斯卡 (Pascal) 三角形:
我們猜測其組成規律是, 每一斜列都是等差數列, 首項皆為 $1$, 但公差依次為 $0, 1, 2, 3, \ldots$。 因此, 第 $k$ 橫列一共有 $k$ 項, 如下: $1, k-1, 2k-5, 3k-11, 4k-19, \ldots$, 其中第 $j$ 項的通式為 $(j-1)k-[j(j-1)-1]$, 化簡得 $(j-1)(k-j)+1$, $j=1, 2, \ldots, k$, 於是圓周上 $k$ 個點 $P_1, P_2, \ldots, P_k$ 再增加一點 $P_{k+1}$ 時, 所增加的區域數為 $a_{k+1}-a_{k}=\sum^k_{j=1}[(j-1)(k-j)+1]$, 所以可得 $a_n=a_1+\sum^{n-1}_{k=1}(a_{k+1}-a_k)=1+\sum^{n-1}_{k=1}\sum^k_{j=1}[(j-1)(k-j)+1] =\frac{1}{24}(n-1)n(n^2-5 n+18)+1$。$\Box$ 有關 $n$ 個點所構成的線可劃分成多少塊區域所形成的數列, 可參考網路整數數列百科全書 "The On-Line Encyclopedia of Integer Sequences" (Sloane, 2007, A000127), 裡面詳細列出此數列並有其遞迴公式。 例 3.7: (雪花-碎形) 設 $\Delta ABC$ 是邊長為 $1$ 的等邊三角形。 將三邊分別三等分, 取中間段為一邊向外側做正三角形, 並且將中間這段擦去, 其次將剩下的每一邊再三等分, 取中間段為一邊向外做正三角形, 再將中間這段擦去。 仿此程序繼續做下去, 得一系列的碎形。求
解:
更進一步相關碎形介紹可參閱維基網站: Fractal (2007)。
一階非齊次線性遞迴關係式 \begin{equation} \label{eqnB:34795} a_{n+1} = g(n)a_n + f(n) \end{equation} 也可以利用以下的方法化簡成齊次式的解法。設特解 $a_n^{(p)}$ 滿足原遞迴關係式 (\ref{eqnB:34795}), 即 \begin{equation} \label{eqnB:36040} a_{n+1}^{(p)} =g(n)a_n^{(p)} + f(n) \end{equation} 考慮 (\ref{eqnB:34795}) 減去 (\ref{eqnB:36040}) 即得數列 $\{a_n-a_n^{(p)}\}$ 的一個齊次關係式 $$ \Big (a_{n+1} - a_{n+1}^{(p)}\Big ) = g(n) \Big (a_n - a_n^{(p)}\Big ) $$ 因此 $(a_{n}-a_{n}^{(p)})=g(n-1)(a_{n-1}-a_{n-1}^{(p)})=g(n-1)g(n-2)(a_{n-2}-a_{n-2}^{(p)}) =\cdots=(\prod_{k=0}^{n-1}g(k))(a_{0}-a_{0}^{(p)})$, 所以 $a_n=a_n^{(p)}+(\prod_{k=0}^{n-1}g(k)) (a_{0}-a_{0}^{(p)})$。 例 3.8: 設遞迴關係式 $a_{n+1}=3a_n-2$, $n\ge 0$, $a_0=2$, 求 $a_n$ 的解。 解: 設 $a_n^{(p)}=c$ 代入關係式得 $c=3c-2$, 所以 $c=1$。 因此, $a_n-1=3(a_{n-1}-1)=3^2(a_{n-2}-1)=\cdots=3^n(a_0-1)=3^n$, 所以 $a_n=3^n+1$。 $\Box$ 習題 3下列是一些不錯的題目, 也許讀者有興趣試試, 為了方便讀者, 我們也將答案列入。
參考文獻---本文作者張福春任教國立中山大學應用數學系, 莊淨惠為國立中山大學應用數學系碩士班畢業生--- |