生成函數(shù)在遞推關系問題上的應用

■崔龍飛 劉浩東

武警警官學院

1 生成函數(shù)的相關知識

1.1 生成函數(shù)的定義

母函數(shù)又叫生成函數(shù)，作為離散數(shù)學的一個重要部分的生成函數(shù)方法，其將離散數(shù)學串聯(lián)溝通起連續(xù)數(shù)學，在對組合數(shù)學問題進行分析時，在組合計數(shù)方面生成函數(shù)具有天生的優(yōu)越性，是對組合計數(shù)問題解決的工具。

將需要研究的數(shù)列運用冪級數(shù)或多項式合成一個整體，通過對多項式或冪級數(shù)的性質和對合并同類項的方法這個方法的使用進行研究，最終得到相關的結論，這就是生成函數(shù)的中心思想。

1.2 生成函數(shù)的基本性質

假設，序列（ak），（bk）的生成函數(shù)的分別是：

P(x)=a0+a1x1+a2x2+…Q(x)=b0+b1x1+b2x2…

生成函數(shù)和數(shù)列之間是一一對應的，因此要對兩個數(shù)列之間的關系進行研究可以轉化為研究它們的生成函數(shù)的關系，從而就方便解題[1]。

1.3 生成函數(shù)的計算

將相對復雜的生成函數(shù)化簡成簡單的二次式類型，或者是若干個二項式類型的生成函數(shù)的積，這就是計算生成函數(shù)系數(shù)的方式，從而不難得出所需要的xk的系數(shù)。要運用到牛頓二項式定理和它的生成函數(shù)的性質。

牛頓二項式定理：

舉例求解生成函數(shù)：

求得生成函數(shù)的系數(shù)可借助牛頓二項式定理。

數(shù)學中的遞推關系問題

在數(shù)學領域中，遞推關系在其有著很重要的位置和其應用也很廣泛。一般情況下求解遞

推關系并容易，如果只是運用遞推關系的一些定義是不能解決很多問題，它關聯(lián)到很廣領域。

研究遞推關系是追溯到斐波納契關系：Fn+2=Fn+1+Fn，n≥0，F(xiàn)0=0，F(xiàn)1=1，最先給出的是比薩的數(shù)學家Leonardo。

數(shù)列xn必須有連續(xù)個k項滿足xn+k=f(xn+k-1，xn+k-2，…，xn)，滿足此式的數(shù)列叫它為數(shù)列xn的一個遞推關系式，這就是線性遞推關系定義。

由遞推關系式和滿足k個初始值可以確定的一個數(shù)列xn叫做遞推數(shù)列。所以，不管是設計到遞推數(shù)列解析題，證明題，還是需要建立遞推關系式的綜合題，則求通項公式就是解決遞推數(shù)列的核心，也是最基本的步驟[2]。

3 生成函數(shù)法應用于遞推關系的求解

不少求排列組合計算問題的時候一般都會歸結為求某個數(shù)列xn的通項公式，直接一些求數(shù)列的通項公式一般不是那么容易，然而可以求所滿足的遞推關系，則首選的方法就是生成函數(shù)，在求遞推數(shù)列關系，一種重要的思維與常用的方法就包括生成函數(shù)。

3.1 生成函數(shù)法應用到常系數(shù)線性齊次遞推關系上

定義：常系數(shù)線性齊次遞推關系

將關于an的常系數(shù)線性齊次遞推關系轉化為an的生成函數(shù)G(x)，通常運用錯位相減法，然后運用代數(shù)方法求G(x)，冪級數(shù)的形式把它把展成出來，xn的系數(shù)an就是所求，這就是使用生成函數(shù)法解常系數(shù)線性齊次遞推關系的基本思想。

在上面例中運用到的方法，即錯位相加減法，可以得知，和傳統(tǒng)方法相比，運用生成函數(shù)的方法來求解an更加容易。

3.2 生成函數(shù)法應用在常系數(shù)線性非齊次遞推關系上

使用生成函數(shù)法解常系數(shù)線性非齊次遞推關系的基本思想是：設序列an的生成函數(shù)是Q(X)=anxn將關于an的常系數(shù)線性非齊次遞推關系代入Q(X)=anxn的右端，得到Q(x)的方程，Q(X)的解求得出來。再用冪級數(shù)的形式把它展示出來，xn的系數(shù)an就是所求。

其中a是實數(shù)；b是常數(shù)；k是正整數(shù)。

4 結語

本文通過對問題進行引入、分析、解決和延伸，對生成函數(shù)法求解常系數(shù)線性非齊次遞推關系與常系數(shù)線性齊次遞推關系。通過舉例分析，生成函數(shù)運用到遞推關系問題的求解上是很有用的，已經(jīng)廣泛運用到數(shù)學中。