遞迴關係式的母函數解法

本文的閱讀等級:初級

美國數學教授維爾夫 (Herbert Wilf) 說[1]:「母函數 (生成函數,generating function) 是一列用來展示一串數字的掛衣架。」母函數是一數列 a_0,a_1,a_2,\ldots 的一種形式冪級數 (formal power series),其中每一項的係數可以提供關於這個數列的訊息。母函數有多種不同的形式,數列 \{a_n\}_0^\infty 的普通母函數為

\displaystyle  G(x)=a_0+a_1x+a_2x^2+\cdots

母函數 G(x) 本身並不是一個從某個定義域映射至某個值域的函數,變數 x 沒有甚麼特別的意義,取名「函數」僅是出於歷史原因。母函數是一個代數物件而非分析物件,我們只對它的表達形式感興趣,並不關心它是否收斂。母函數經常源自遞迴關係式 (即差分方程)。本文將介紹如何利用母函數方法解出遞迴關係式的代數式。由於我們完全忽略收斂性,母函數方法是否能經得起推敲不免令人生疑。不過母函數至少能夠導出遞迴關係式的猜想,而猜想又可以用數學歸納法來證明。

 
例一:數列 a_0, a_1, a_2,\ldots 滿足 \displaystyle  a_{n+1}=2a_n+1a_0=0,求 a_n 的顯式表達式 (參閱維基百科“河內塔”)。

寫出數列 \{a_n\} 的前幾項 0,1,3,7,15,\ldots,不難推測出 a_n=2^n-1,再以歸納法證明:首先,a_0=2^0-1=0,又當 n\ge 2 時,有 a_n=2a_{n-1}+1=2\cdot(2^{n-1}-1)+1=2^n-1。母函數方法不直接求出數列 \{a_n\},而是去尋找母函數 G(x)=\sum_{n=0}^\infty a_nx^n。一旦得到母函數 G(x),所求 a_n 即為 x^n 的係數。欲求出 G(x),遞迴關係式 \displaystyle  a_{n+1}=2a_n+1 的等號兩邊同乘 x^n,再將所有的 n 加總在一起。因為有邊界條件 a_0=0,等號左邊為

\displaystyle\begin{aligned}  \sum_{n=0}^\infty a_{n+1}x^n&=a_1+a_2x+a_3x^2+\cdots=\frac{G(x)}{x},  \end{aligned}

使用幾何級數公式,等號右邊為

\displaystyle\begin{aligned}  \sum_{n=0}^\infty(2a_n+1)x^n&=2\sum_{n=0}^\infty a_nx^n+\sum_{n=0}^\infty x^n=2G(x)+\frac{1}{1-x},\end{aligned}

上式成立的條件是 \vert x\vert<1。合併兩式,

\displaystyle  \frac{G(x)}{x}=2G(x)+\frac{1}{1-x}

立即解出

\displaystyle  G(x)=\frac{x}{(1-x)(1-2x)}

接著使用部分分式分解將母函數展開,

\displaystyle\begin{aligned}  \frac{x}{(1-x)(1-2x)}&=x\left(\frac{2}{1-2x}-\frac{1}{1-x}\right)\\  &=2x\left(1+2x+(2x)^2+\cdots\right)-x\left(1+x+x^2+\cdots\right)\\  &=(2-1)x+(2^2-1)x^2+(2^3-1)x^3+\cdots\end{aligned}

x^n 的係數可讀出 a_n=2^n-1。讀者或許懷疑這只是一個玩具問題,實在顯不出母函數了不起的地方。下面再舉一個稍微困難的例子。

 
例二:數列 a_0, a_1, a_2\ldots 滿足 \displaystyle  a_{n+1}=2a_n+na_0=1,求 a_n 的表達式。

從數列的前幾項 1,2,5,12,27,58,\ldots 很難觀察出 a_n 的表達式,下面我們用母函數方法解出 \{a_n\}。考慮母函數 G(x)=\sum_{n=0}^\infty a_nx^n。如同例一的計算步驟,遞迴關係式 \displaystyle  a_{n+1}=2a_n+n 的等號兩邊同乘 x^n,再加總所有項。因為 a_0=1,等號左邊是

\displaystyle\begin{aligned}  \sum_{n=0}^\infty a_{n+1}x^n&=a_1+a_2x+a_3x^2+\cdots\\  &=\frac{1}{x}\left((a_0+a_1x+a_2x^2+\cdots)-a_0\right)=\frac{G(x)-1}{x},  \end{aligned}

等號右邊是

\displaystyle\begin{aligned}  \sum_{n=0}^\infty(2a_n+n)x^n&=2\sum_{n=0}^\infty a_nx^n+\sum_{n=0}^\infty nx^n=2G(x)+\frac{x}{(1-x)^2}.\end{aligned}

第二項的計算過程如下:因為導數是線性算子,

\displaystyle\begin{aligned}  \sum_{n=0}^\infty nx^n&=\sum_{n=0}^\infty x\frac{d}{dx}x^n=x\frac{d}{dx}\left(\sum_{n=0}^\infty x^n\right)\\  &=x\frac{d}{dx}\left(\frac{1}{1-x}\right)=\frac{x}{(1-x)^2},\end{aligned}

上式限定 \vert x\vert<1 (以後就不再特別講明)。合併等號兩邊算式,

\displaystyle  \frac{G(x)-1}{x}=2G(x)+\frac{x}{(1-x)^2}

由此解得

\displaystyle  G(x)=\frac{1-2x+2x^2}{(1-x)^2(1-2x)}

寫出部分分式分解:

\displaystyle  \frac{1-2x+2x^2}{(1-x)^2(1-2x)}=\frac{a}{1-x}+\frac{b}{(1-x)^2}+\frac{c}{1-2x}

剩下的問題要找到 a,b,c。使用比較係數法。欲求出 b,等式兩邊通乘 (1-x)^2,再代入 x=1,可得 b=-1。欲求出 c,等式兩邊通乘 (1-2x),再代入 x=1/2,可得 c=2。欲求出 a,代入 x=0,使用已知的 b, c 值,可得 a=0。最後套用幾何級數以及 x/(1-x)^2 的展開式,

\displaystyle\begin{aligned}  G(x)&=\frac{2}{1-2x}-\frac{1}{(1-x)^2}\\  &=2\sum_{n=0}^\infty(2x)^n-\sum_{n=0}^\infty (n+1)x^n\\  &=\sum_{n=0}^\infty (2^{n+1}-n-1)x^n,\end{aligned}

x^n 的係數可讀出 a_n=2^{n+1}-n-1

 
從上面兩個例子可歸納出母函數方法於求解遞迴關係式的執行步驟。

  1. 定義母函數 G(x)=\sum_{n=0}^\infty a_nx^n
  2. 遞迴關係式等號兩邊同乘 x^n,再將所有定義良好的 n 加總。
  3. 將等號左邊和右邊分別以母函數 G(x) 明確表示,解出未知的 G(x)
  4. 利用部分分式分解或其他方法 (如泰勒展開式) 將 G(x) 展開成冪級數。

 
下面我們照上述執行步驟求解一個二項線性遞迴關係式 (例三) 和一個多項非線性遞迴關係式 (例四)。

 
例三:費布納西 (Fibonacci) 數列滿足

F_{n+1}=F_{n}+F_{n-1},~~~F_0=0, F_1=1

F_n 的表達式 (線性代數解法請參閱“費布納西數列的表達式”)。

步驟1. 寫出母函數 G(x)=\sum_{n=0}^\infty F_nx^n

步驟2. 遞迴關係式等號兩邊同乘 x^n,再將所有的 n\ge 1 加總:

\displaystyle  \sum_{n=1}^\infty F_{n+1}x^n=\sum_{n=1}^\infty F_nx^n+\sum_{n=1}^\infty F_{n-1}x^n

步驟3. 將上式以母函數 G(x) 表示為

\displaystyle  \frac{G(x)-x}{x}=G(x)+xG(x)

解出

\displaystyle  G(x)=\frac{x}{1-x-x^2}

步驟4. 分解 G(x) 的分母,如下:

1-x-x^2=(1-\alpha x)(1-\beta x)

其中 \alpha=(1+\sqrt{5})/2\beta=(1-\sqrt{5})/2。使用幾何級數,

\displaystyle\begin{aligned}  \frac{x}{1-x-x^2}&=\frac{x}{(1-\alpha x)(1-\beta x)}\\  &=\frac{1}{\alpha-\beta}\left(\frac{1}{1-\alpha x}-\frac{1}{1-\beta x}\right)\\  &=\frac{1}{\sqrt{5}}\left(\sum_{n=0}^\infty\alpha^nx^n-\sum_{n=0}^\infty\beta^nx^n\right)\\  &=\sum_{n=0}^n\frac{1}{\sqrt{5}}(\alpha^n-\beta^n)x^n  .\end{aligned}

最後得到費布納西數列

\displaystyle  F_n=\frac{1}{\sqrt{5}}(\alpha^n-\beta^n)=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n-\left(\frac{1-\sqrt{5}}{2}\right)^n\right]

 
例四:數列 a_0,a_1,a_2,\ldots 滿足多項非線性遞迴關係式

a_n=a_0a_{n-1}+a_1a_{n-2}+\cdots+a_{n-1}a_0,~~~a_0=1

a_n 的表達式。

步驟1. 寫出母函數 G(x)=\sum_{n=0}^\infty a_nx^n

步驟2. 因為遞迴關係式等號右邊涉及 a_ia_j,等號兩邊同乘 x^n 的作法不再有效。我們改將母函數平方,

\displaystyle  G^2(x)=a_0^2+(a_0a_1+a_1a_0)x+\cdots+(a_0a_{n-1}+a_1a_{n-2}+\cdots+a_{n-1}a_0)x^{n-1}+\cdots

步驟3. 根據遞迴關係式可得

\displaystyle  G^2(x)=a_1+a_2x+\cdots+a_nx^{n-1}+\cdots=\frac{G(x)-1}{x}

由此解出

\displaystyle  G(x)=\frac{1-\sqrt{1-4x}}{2x}

\Gamma(x)=xG(x)。因為 \Gamma(0)=0,我們只能取帶負號的一個解,帶正號的一個解產生 \Gamma(0)=\frac{1+1}{2}=1

步驟4. 使用冪級數展開式 (廣義二項式定理)

\displaystyle  (1+x)^r=1+\binom{r}{1}x+\binom{r}{2}x^2+\cdots=\sum_{k=0}^\infty\binom{r}{k}x^k

其中 r 是實數。將 x-4x 取代,r 設為 1/2,即有

\displaystyle  \sqrt{1-4x}=1+\binom{\frac{1}{2}}{1}(-4x)+\binom{\frac{1}{2}}{2}(-4x)^2+\cdots=\sum_{n=0}^\infty\binom{\frac{1}{2}}{n}(-4x)^n

注意,-\frac{1}{2}\sqrt{1-4x} 展開式的 x^{n+1} 項的係數即為 a_nn\ge 1。重複使用二項式係數的進出公式 (見“二項式係數公式”),可得

\displaystyle\begin{aligned}  a_n&=-\frac{1}{2}\binom{\frac{1}{2}}{n+1}(-4)^{n+1}\\  &=-\frac{1}{2}\cdot\frac{1}{n+1}\left(\frac{1}{2}\right)\binom{-\frac{1}{2}}{n}(-1)^{n+1}4^{n+1}\\  &=\frac{1}{2}\cdot\frac{1}{(n+1)(n)}\left(\frac{1}{2}\right)\left(-\frac{1}{2}\right)\binom{-\frac{3}{2}}{n-1}(-1)^{n}4^{n+1}\\  &=\cdots\\  &=\frac{1}{2}\cdot\frac{1}{(n+1)!}\left(\frac{1}{2}\right)\left(-\frac{1}{2}\right)\left(-\frac{3}{2}\right)\cdots\left(-\frac{2n-1}{2}\right)(-1)^n4^{n+1}\\  &=\frac{1}{2}\cdot\frac{1\cdot 3\cdot 5\cdots(2n-1)}{(n+1)!}\cdot\frac{(-1)^n}{2^{n+1}}(-1)^{n}4^{n+1}\\  &=\frac{1}{2}\cdot\frac{(2n)!}{(n+1)!\cdot 2^n n!}\cdot\frac{4^{n+1}}{2^{n+1}}\\  &=\frac{1}{n+1}\cdot\frac{(2n)!}{n!n!}\\  &=\frac{1}{n+1}\binom{2n}{n}.\end{aligned}

 
以上的例子限定於一個變數,最後我們考慮涉及兩個變數的問題:用母函數方法來推導二項式係數。

 
例五:令 nk 為兩個整數使得 0\le k\le n。從集合 \Psi=\{1,2,\ldots,n\} 選取 k 個元素的組合方式共有多少種?

當然,大家都知道從包含 n 個元素的集合中選取 k 個元素的組合數即為二項式係數 \binom{n}{k}。不過這裡我們假定不知道答案,將它設為 f(n,k),並定義 f(n,k)=0k>n。設 p\in\Psi,由 \Psi 中選取 k 個元素可分開兩種情況討論:若不取 p,則必須從 \Psi-\{p\} 選取 k 個元素,組合數為 f(n-1,k);若選取 p,還要從 \Psi-\{p\} 取其餘 (k-1) 個元素,組合數為 f(n-1,k-1)。所以,

\displaystyle  f(n,k)=f(n-1,k)+f(n-1,k-1),~~f(n,0)=1

這個遞迴關係式稱為帕斯卡 (Pascal) 法則。

 
對於 n=0,1,\ldots,定義母函數

\displaystyle  G_n(x)=\sum_{k=0}^nf(n,k)x^k

遞迴關係式等號兩邊乘以 x^k,再將所有 1\le k\le n 加總:

\displaystyle  \sum_{k=1}^nf(n,k)x^k=\sum_{k=1}^nf(n-1,k)x^k+\sum_{k=1}^nf(n-1,k-1)x^k

套入母函數可得

\displaystyle  G_n(x)-1=(G_{n-1}(x)-1)+xG_{n-1}(x)

將上式改寫為

\displaystyle  G_n(x)=(1+x)G_{n-1}(x),~~n\ge 1,~~ G_0(x)=1

所以,G_n(x)=(1+x)^nn\ge 0。未知函數 f(n,k) 就是 (1+x)^nx^k 項的係數。(牛頓在1664年給出 (x+y)^n 的展開式,稱為二項式定理,見“特殊矩陣 (15):Pascal 矩陣 (上)”。) 因為 G_n(x)0 的泰勒展開式為

\displaystyle  G_n(x)=G_n(0)+G'_n(0)x+\frac{1}{2!}G''_n(0)x^2+\cdots+\frac{1}{k!}G_n^{(k)}(0)x^k+\cdots

可知

\displaystyle\begin{aligned}  f(n,k)&=\frac{1}{k!}\left.\frac{d^k}{dx^k}(1+x)^n\right|_{x=0}\\  &=\frac{1}{k!}\left. n(n-1)\cdots(n-k+1)(1+x)^{n-k}\right|_{x=0}\\  &=\frac{n!}{k!(n-k)!}.\end{aligned}

 
通過帕斯卡法則,母函數可以用來解二項式係數。在組合數學中,二項式係數是一個非常重要的計數序列,這暗示我們母函數方法勢必可以廣泛應用於組合數學問題。

 
參考來源:
[1] 原文是 “A generating function is a clothesline on which we hang up a sequence of numbers for display.” 引用自維爾夫 (Herbert Wilf) 專門討論母函數的電子書 generatingfunctionology

Advertisements
This entry was posted in 特別主題 and tagged , , , , , , . Bookmark the permalink.

發表迴響

在下方填入你的資料或按右方圖示以社群網站登入:

WordPress.com Logo

您的留言將使用 WordPress.com 帳號。 登出 / 變更 )

Twitter picture

您的留言將使用 Twitter 帳號。 登出 / 變更 )

Facebook照片

您的留言將使用 Facebook 帳號。 登出 / 變更 )

Google+ photo

您的留言將使用 Google+ 帳號。 登出 / 變更 )

連結到 %s