用生成函數(shù)求幾類(lèi)數(shù)列的通項(xiàng)公式

李鴻昌

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

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

1 預(yù)備知識(shí)

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

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

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

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

所以定理1得證.

由定理1,有

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

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

(3)把f(x)展開(kāi)成形式冪級(jí)數(shù);

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

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

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

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

解析因?yàn)閍n+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é)競(jìng)賽試題)已知數(shù)列{an}滿(mǎn)足a1=1,a2=5,an+2=4an+1-3an(n∈N*).

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

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.

②

由①和②,解得

展開(kāi)成形式冪級(jí)數(shù),得到

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

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

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

例4[4]已知數(shù)列{an}滿(mǎn)足an-2an-1+an-2=2n,且a0=a1=1,求通項(xiàng)公式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-…,

三式相加,得

展開(kāi)成形式冪級(jí)數(shù),得

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

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

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

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

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

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

圖1 對(duì)角線(xiàn)分凸n邊形

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

因?yàn)門(mén)1有ak種分法,T2有an-k種分法,故T有akan-k種分法,這種分法是對(duì)固定的點(diǎn)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.

因?yàn)閒1(0)=1,f2(0)=0,而我們要找的f(x)滿(mǎn)足f(0)=0,所以只能取

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

利用牛頓二項(xiàng)式定理,有

6 結(jié)束語(yǔ)

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