用生成函數求幾類數列的通項公式

李鴻昌

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

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

1 預備知識

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

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

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

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

所以定理1得證.

由定理1,有

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

(2)根據數列的遞推關系求出f(x);

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

(4)求出xn的系數.

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

3 常系數線性齊次遞推數列

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

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

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,

用待定系數法,有

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

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

(1)求數列{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.

②

由①和②,解得

展開成形式冪級數,得到

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

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

4 常系數線性非齊次遞推數列

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

解析設數列{an}的生成函數為

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-…,

三式相加,得

展開成形式冪級數,得

5 一個特殊的數列

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

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

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

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

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

圖1 對角線分凸n邊形

根據假設,凸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+….

那么

根據初始值a1=a2=1和an的遞推關系,得到

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)展開成形式冪級數即可.

利用牛頓二項式定理,有

6 結束語

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