離散數學 - 遞推關係

---

---

在本章中，我們將討論遞迴技術如何匯出序列並用於解決計數問題。以遞迴方式查詢序列項的過程稱為遞推關係。我們研究線性遞推關係及其解的理論。最後，我們介紹了用於解決遞推關係的生成函式。

定義

遞推關係是一個遞迴定義序列的方程，其中下一項是前面項的函式（將$F_n$表示為$i < n$的$F_i$的某種組合）。

示例 - 斐波那契數列 - $F_n = F_{n-1} + F_{n-2}$，漢諾塔 - $F_n = 2F_{n-1} + 1$

線性遞推關係

k階或k度的線性遞推方程是一個遞推方程，其格式為$x_n= A_1 x_{n-1}+ A_2 x_{n-1}+ A_3 x_{n-1}+ \dots A_k x_{n-k}$（$A_n$是常數且$A_k \neq 0$）關於數列作為一階多項式。

以下是一些線性遞推方程的示例：

如何求解線性遞推關係

假設，一個二階線性遞推關係為 - $F_n = AF_{n-1} +BF_{n-2}$，其中A和B是實數。

上述遞推關係的特徵方程為 -

$$x^2 - Ax - B = 0$$

在求解根的過程中，可能會出現三種情況：

情況1 - 如果此方程因式分解為$(x- x_1)(x- x_1) = 0$，併產生兩個不同的實根$x_1$和$x_2$，則$F_n = ax_1^n+ bx_2^n$是解。[這裡，a和b是常數]

情況2 - 如果此方程因式分解為$(x- x_1)^2 = 0$，併產生單個實根$x_1$，則$F_n = a x_1^n+ bn x_1^n$是解。

情況3 - 如果方程產生兩個不同的復根，$x_1$和$x_2$，以極座標形式$x_1 = r \angle \theta$和$x_2 = r \angle(- \theta)$表示，則$F_n = r^n (a cos(n\theta)+ b sin(n\theta))$是解。

問題1

解遞推關係$F_n = 5F_{n-1} - 6F_{n-2}$，其中$F_0 = 1$且$F_1 = 4$

解答

遞推關係的特徵方程為 -

$$x^2 - 5x + 6 = 0,$$

所以$(x - 3) (x - 2) = 0$

因此，根為 -

$x_1 = 3$和$x_2 = 2$

根是實數且互異。所以，這屬於情況1

因此，解為 -

$$F_n = ax_1^n + bx_2^n$$

這裡，$F_n = a3^n + b2^n\ (因為\ x_1 = 3\ 且\ x_2 = 2)$

所以，

$1 = F_0 = a3^0 + b2^0 = a+b$

$4 = F_1 = a3^1 + b2^1 = 3a+2b$

解這兩個方程，我們得到$ a = 2$和$b = -1$

因此，最終解為 -

$$F_n = 2.3^n + (-1) . 2^n = 2.3^n - 2^n $$

問題2

解遞推關係 - $F_n = 10F_{n-1} - 25F_{n-2}$，其中$F_0 = 3$和$F_1 = 17$

解答

遞推關係的特徵方程為 -

$$ x^2 - 10x -25 = 0$$

所以 $(x - 5)^2 = 0$

因此，存在單個實根$x_1 = 5$

由於存在單個實數根，所以這屬於情況2

因此，解為 -

$F_n = ax_1^n + bnx_1^n$

$3 = F_0 = a.5^0 + (b)(0.5)^0 = a$

$17 = F_1 = a.5^1 + b.1.5^1 = 5a+5b$

解這兩個方程，我們得到$a = 3$和$b = 2/5$

因此，最終解為 - $F_n = 3.5^n +( 2/5) .n.2^n $

問題3

解遞推關係$F_n = 2F_{n-1} - 2F_{n-2}$，其中$F_0 = 1$且$F_1 = 3$

解答

遞推關係的特徵方程為 -

$$x^2 -2x -2 = 0$$

因此，根為 -

$x_1 = 1 + i$和$x_2 = 1 - i$

以極座標形式，

$x_1 = r \angle \theta$和$x_2 = r \angle(- \theta),$其中$r = \sqrt 2$和$\theta = \frac{\pi}{4}$

根是虛數。所以，這屬於情況3。

因此，解為 -

$F_n = (\sqrt 2 )^n (a cos(n .\sqcap /4) + b sin(n .\sqcap /4))$

$1 = F_0 = (\sqrt 2 )^0 (a cos(0 .\sqcap /4) + b sin(0 .\sqcap /4) ) = a$

$3 = F_1 = (\sqrt 2 )^1 (a cos(1 .\sqcap /4) + b sin(1 . \sqcap /4) ) = \sqrt 2 ( a/ \sqrt 2 + b/ \sqrt 2)$

解這兩個方程，我們得到$a = 1$和$b = 2$

因此，最終解為 -

$F_n = (\sqrt 2 )^n (cos(n .\pi /4 ) + 2 sin(n .\pi /4 ))$

非齊次遞推關係和特解

如果遞推關係的形式為

$F_n = AF_{n-1} + BF_{n-2} + f(n)$，其中$f(n) \ne 0$，則稱為非齊次遞推關係。

其相關的齊次遞推關係為$F_n = AF_{n–1} + BF_{n-2}$

非齊次遞推關係的解$(a_n)$有兩部分。

第一部分是相關齊次遞推關係的解$(a_h)$，第二部分是特解$(a_t)$。

$$a_n=a_h+a_t$$

第一部分的解使用上一節中討論的方法來完成。

為了找到特解，我們找到一個合適的試驗解。

令$f(n) = cx^n$；令$x^2 = Ax + B$為相關齊次遞推關係的特徵方程，並令$x_1$和$x_2$為其根。

• 如果$x \ne x_1$且$x \ne x_2$，則$a_t = Ax^n$

• 如果$x = x_1$，$x \ne x_2$，則$a_t = Anx^n$

• 如果$x = x_1 = x_2$，則$a_t = An^2x^n$

示例

令一個非齊次遞推關係為$F_n = AF_{n–1} + BF_{n-2} + f(n)$，其特徵根為$x_1 = 2$和$x_2 = 5$。對於$f(n)$的不同可能值，試驗解如下所示：

問題

解遞推關係$F_n = 3F_{n-1} + 10F_{n-2} + 7.5^n$，其中$F_0 = 4$和$F_1 = 3$

解答

這是一個線性非齊次關係，其中相關的齊次方程為$F_n=3F_{n-1}+10F_{n-2}$，且$f(n)=7.5^n$

其相關齊次關係的特徵方程為 -

$$x^2 - 3x -10 = 0$$

或者， $(x - 5)(x + 2) = 0$

或者， $x_1= 5$和$x_2 = -2$

因此$a_h = a.5^n + b.(-2)^n$，其中a和b是常數。

由於$f(n) = 7.5^n$，即$c.x^n$的形式，因此$at$的一個合理的試驗解將是$Anx^n$

$a_t = Anx^n = An5^n$

將解代入遞推關係後，我們得到 -

$An5^n = 3A(n – 1)5^{n-1} + 10A(n – 2)5^{n-2} + 7.5^n$

兩邊同除以$5^{n-2}$，我們得到

$An5^2 = 3A(n - 1)5 + 10A(n - 2)5^0 + 7.5^2$

或者， $25An = 15An - 15A + 10An - 20A + 175$

或者， $35A = 175$

或者， $A = 5$

所以， $F_n = An5^n= 5n5^n=n5^{n+1}$

遞推關係的解可以寫成 -

$F_n = a_h + a_t$

$=a.5^n+b.(-2)^n+n5^{n+1}$

將$F_0 = 4$和$F_1 = 3$的值代入上述方程，我們得到$a = -2$和$b = 6$

因此，解為 -

$F_n = n5^{n+1} + 6.(-2)^n -2.5^n$

生成函式

生成函式表示序列，其中序列的每一項都表示為形式冪級數中變數x的係數。

在數學上，對於一個無限序列，例如$a_0, a_1, a_2,\dots, a_k,\dots,$生成函式將是 -

$$G_x=a_0+a_1x+a_2x^2+ \dots +a_kx^k+ \dots = \sum_{k=0}^{\infty}a_kx^k$$

一些應用領域

生成函式可用於以下目的：

• 用於解決各種計數問題。例如，用面值為1元、2元、5元、10元、20元和50元的紙幣兌換100元人民幣的方法數

• 用於解決遞推關係

• 用於證明一些組合恆等式

• 用於查詢序列項的漸近公式

問題1

序列$\lbrace {a_k} \rbrace$的生成函式是什麼，其中$a_k = 2$和$a_k = 3k$？

解答

當$a_k = 2$時，生成函式，$G(x) = \sum_{k = 0}^{\infty }2x^{k} = 2 + 2x + 2x^{2} + 2x^{3} + \dots$

當$a_{k} = 3k$時，$G(x) = \sum_{k = 0}^{\infty }3kx^{k} = 0 + 3x + 6x^{2} + 9x^{3} + \dots\dots$

問題2

無限級數的生成函式是什麼；$1, 1, 1, 1, \dots$？

解答

這裡，$a_k = 1$，對於$0 \le k \le \infty$

因此，$G(x) = 1 + x + x^{2} + x^{3}+ \dots \dots= \frac{1}{(1 - x)}$

一些有用的生成函式

• 對於 $a_k = a^{k}$，$G(x) = \sum_{k = 0}^{\infty }a^{k}x^{k} = 1 + ax + a^{2}x^{2} +\dots \dots \dots = 1/ (1 - ax)$

• 對於 $a_{k} = (k + 1)$，$G(x) = \sum_{k = 0}^{\infty }(k + 1)x^{k} = 1 + 2x + 3x^{2} \dots \dots \dots =\frac{1}{(1 - x)^{2}}$

• 對於 $a_{k} = c_{k}^{n}$，$G(x) = \sum_{k = 0}^{\infty} c_{k}^{n}x^{k} = 1+c_{1}^{n}x + c_{2}^{n}x^{2} + \dots \dots \dots + x^{2} = (1 + x)^{n}$

• 對於 $a_{k} = \frac{1}{k!}$，$G(x) = \sum_{k = 0}^{\infty }\frac{x^{k}}{k!} = 1 + x + \frac{x^{2}}{2!} + \frac{x^{3}}{3!}\dots \dots \dots = e^{x}$