用生成函數(shù)求幾類數(shù)列的通項公式

李鴻昌

(北京師范大學(xué)貴陽附屬中學(xué),貴州 貴陽 550081)

生成函數(shù)是組合數(shù)學(xué)中的一個重要概念,通過生成函數(shù)可以把離散數(shù)學(xué)和連續(xù)數(shù)學(xué)巧妙地連接起來.利用生成函數(shù)來處理中學(xué)數(shù)學(xué)中的數(shù)列通項問題,問題的可操作性強,學(xué)生容易理解.

1 預(yù)備知識

定義1[1]設(shè)a0,a1,…,an,…是一個給定的數(shù)列,我們稱形式冪級數(shù)a0+a1x+…+anxn+…為這個數(shù)列的生成函數(shù).

例如,數(shù)列1,2,3,…,n,…的母函數(shù)是1+2x+3x2+…+nxn+….

注為了應(yīng)用形式冪級數(shù)去解決數(shù)列通項公式問題,我們引進(jìn)形式冪級數(shù)之間的加法、減法、乘法等運算,并規(guī)定:在進(jìn)行這些運算時,把形式冪級數(shù)看成冪級數(shù),然后按冪級數(shù)的運算法則去進(jìn)行運算.

證明由數(shù)學(xué)分析知識,對于A(x)=1+ax(a≠0,|x|<1),有

所以定理1得證.

由定理1,有

2 利用生成函數(shù)求數(shù)列通項公式的步驟

(2)根據(jù)數(shù)列的遞推關(guān)系求出f(x);

(3)把f(x)展開成形式冪級數(shù);

(4)求出xn的系數(shù).

由此可見,利用生成函數(shù)來理解數(shù)列通項后,求解數(shù)列通項就不再是玩技巧了,而是程序性的操作.

3 常系數(shù)線性齊次遞推數(shù)列

例1設(shè)數(shù)列{an}滿足an-10an-1+21an-2=0,且a1=3,a2=93,求通項公式an.

解析因為an+2-10an+1+21an=0,且a1=3,a2=93,設(shè)數(shù)列{an}的生成函數(shù)為

f(x)=a1x+a2x2+a3x3+…+anxn+….

上式兩邊乘以(-10x),得

-10xf(x)=-10a1x2-10a2x3-…-10an-1xn-…,

上式兩邊乘以21x2,得

21x2f(x)=21a1x3+…+21an-2xn+….

三式相加,得

(1-10x+21x2)f(x)

=a1x+(a2-10a1)x2+(a3-10a2+21a3)x3+…+(an-10an-1+21an-2)xn+…

=a1x+(a2-10a1)x2

=3x+63x2,

用待定系數(shù)法,有

故an=3×7n-6×3n.

例2[3](2020年福建省數(shù)學(xué)競賽試題)已知數(shù)列{an}滿足a1=1,a2=5,an+2=4an+1-3an(n∈N*).

(1)求數(shù)列{an}的通項公式;

f(x)=a1x+a2x2+a3x3+…+anxn+an+1xn+1+an+2xn+2+…,

-4xf(x)=-4a1x2-4a2x3-…-4an+1xn+2-…,

3x2f(x)=3a1x3+…+3anxn+2+…,

將以上三式相加,并利用a1=1,a2=5,an+2=4an+1-3an(n∈N*),得

(1-4x+3x2)f(x)=x+x2.

故an=2×3n-1-1.

(2)由(1)知

A(x)=a1x+a2x2+…+anxn+…,

2xA(x)=2a1x2+…+2an-1xn+…,

-4xB(x)=-4b1x2-…-4bn-1xn-….

三式相加,得

(1+2x)A(x)-4xB(x)=-10x.

①

又B(x)=b1x+b2x2+…+bnxn+…,

5xA(x)=5a1x2+…+5an-1xn+…,

-7xB(x)=-7b1x2-…-7bn-1xn-….

三式相加,得

5xA(x)+(1-7x)B(x)=-13x.

②

由①和②,解得

展開成形式冪級數(shù),得到

所以an=2n-4·3n.

所以bn=2n-5·3n.

4 常系數(shù)線性非齊次遞推數(shù)列

例4[4]已知數(shù)列{an}滿足an-2an-1+an-2=2n,且a0=a1=1,求通項公式an.

解析設(shè)數(shù)列{an}的生成函數(shù)為

f(x)=a0+a1x+a2x2+…+anxn+…,

-2xf(x)=-2a0x-2a1x2-…-2an-1xn-…,

x2f(x)=a0x2+…+an-2xn+…,

四式相加,得

所以an=2n+2-4n-3.

f(x)=a1x+a2x2+…+anxn+…,

-xf(x)=-a1x2-…-an-1xn-…,

三式相加,得

展開成形式冪級數(shù),得

5 一個特殊的數(shù)列

例6[5](卡特蘭數(shù))設(shè)有一凸n邊形,用n-3條在內(nèi)部不相交的對角線把這凸n邊形分成n-2個三角形,那么一共有多少種不同的分法?

解析設(shè)an表示將一個凸n+1邊形劃分為三角形的分法數(shù),并規(guī)定a1=1.

當(dāng)n=2時,凸n+1邊形是三角形,它只有一種分法,所以a2=1.

當(dāng)n=3時,凸n+1邊形是四角形,它只有兩種分法,所以a3=2.

現(xiàn)設(shè)n≥3,我們在凸n+1邊形T中先任意取定一條邊,例如圖1中的AB,另取一點C.設(shè)△ABC左邊的圖形T1是一個凸k+1邊形,那么,△ABC右邊的圖形T2必是一個凸n-k+1邊形.

圖1 對角線分凸n邊形

根據(jù)假設(shè),凸k+1邊形T1有ak種不同的分法,凸n-k+1邊形T2有an-k種不同的分法.T1,T2的每一種分法就給出整個n+1邊形T的一種分法.

因為T1有ak種分法,T2有an-k種分法,故T有akan-k種分法,這種分法是對固定的點C而言的.

an=a1an-1+a2an-2+…+an-1a1.

f(x)=a1x+a2x2+a3x3+…+anxn+….

那么

根據(jù)初始值a1=a2=1和an的遞推關(guān)系,得到

f2(x)=a2x2+a3x3+a4x4+…+anxn+…

=f(x)-a1x

=f(x)-x.

因為f1(0)=1,f2(0)=0,而我們要找的f(x)滿足f(0)=0,所以只能取

下面把f(x)展開成形式冪級數(shù)即可.

利用牛頓二項式定理,有

6 結(jié)束語

給定數(shù)列的遞推公式,求解其通項公式,是高考與競賽中常見的題型.對于簡單的遞推公式,通過構(gòu)造等差數(shù)列或者等比數(shù)列即可得解.但對于復(fù)雜且難度較大的遞推公式,則需要很強的技巧才能解決.但利用生成函數(shù),則可很好地解決難度較大的遞推數(shù)列的通項公式,比如常系數(shù)線性齊次遞推數(shù)列和常系數(shù)線性非齊次遞推數(shù)列.利用生成函數(shù)求數(shù)列的通項公式,不僅操作性強,而且學(xué)生也容易理解.可以說,生成函數(shù)是求解遞推數(shù)列的通項公式的通法.