生成函数
定义
一般来说，对于有限数列
a
0
,
a
1
,
a
2
,
⋯
a
n
a_0, a_1, a_2, \cdots a_n
a0,a1,a2,⋯an
多项式
f
(
x
)
=
∑
k
=
0
n
a
k
x
k
=
a
0
+
a
1
x
+
a
2
x
2
+
⋯
+
a
n
x
n
f(x) = \sum_{k = 0}^{n}a_kx^k = a_0 + a_1 x + a_2 x ^ 2 + \cdots + a_nx^n
f(x)=k=0∑nakxk=a0+a1x+a2x2+⋯+anxn
称为数列
{
a
n
}
\lbrace a_n \rbrace
{an} 的生成函数。例如：
f
(
x
)
=
(
1
+
x
)
n
=
C
n
0
+
C
n
1
x
+
C
n
2
x
2
+
⋯
+
C
n
n
x
n
f(x) = (1 + x)^n = C_n^0 + C_n^1x +C_n^2 x^2 + \cdots + C_n^n x^n
f(x)=(1+x)n=Cn0+Cn1x+Cn2x2+⋯+Cnnxn
就是数列：
{
C
n
0
,
C
n
1
,
C
n
2
,
⋯
C
n
n
}
\lbrace C_n^0, C_n^1, C_n^2, \cdots C_n^n \rbrace
{Cn0,Cn1,Cn2,⋯Cnn}
的生成函数。
更一般的，对于无穷数列：
a
0
,
a
1
,
a
2
,
⋯
a
n
,
⋯
a_0, a_1, a_2, \cdots a_n, \cdots
a0,a1,a2,⋯an,⋯
多项式：
f
(
x
)
=
∑
n
=
0
∞
a
n
x
n
=
a
0
+
a
1
x
+
a
2
x
2
+
⋯
f(x) = \sum_{n=0}^{\infty}a_nx^n = a_0 + a_1x + a_2 x^2 + \cdots
f(x)=n=0∑∞anxn=a0+a1x+a2x2+⋯
就是无穷数列
{
a
n
}
\lbrace a_n \rbrace
{an} 的生成函数，这种生成函数也叫作形式幂级数。对于形式幂级数
f
(
x
)
=
∑
n
=
0
∞
a
n
x
n
f(x) = \sum\limits_{n=0}^{\infty}a_nx^n
f(x)=n=0∑∞anxn 和
g
(
x
)
=
∑
n
=
0
∞
b
n
x
n
g(x) = \sum\limits_{n=0}^{\infty} b_nx^n
g(x)=n=0∑∞bnxn 来说，我们有：
f
(
x
)
=
g
(
x
)
当
且
仅
当
a
n
=
b
n
,
n
=
0
,
1
,
2
,
⋯
f
(
x
)
±
g
(
x
)
=
∑
n
=
0
∞
(
a
n
+
b
n
)
x
n
α
f
(
x
)
=
∑
n
=
0
∞
(
α
a
n
)
x
n
(
α
为
常
数
)
f
(
x
)
g
(
x
)
=
∑
n
=
0
∞
c
n
x
n
，
其
中
c
k
=
∑
k
=
0
∞
a
k
b
n
−
k
，
n
=
0
,
1
,
2
,
⋯
\begin{aligned} & f(x) = g(x) \quad 当且仅当 \; \; a_n = b_n \;\; ,n = 0, 1, 2, \cdots \\ & f(x) \pm g(x) = \sum_{n=0}^{\infty} (a_n + b_n)x^n \\ & \alpha f(x) = \sum_{n=0}^{\infty} (\alpha a_n)x^n \quad (\alpha 为常数) \\ & f(x)g(x) = \sum_{n=0}^{\infty}c_nx^n，其中 \;\; c_k = \sum_{k=0}^{\infty} a_kb_{n-k}，n=0, 1, 2,\cdots \end{aligned}
f(x)=g(x)当且仅当an=bn,n=0,1,2,⋯f(x)±g(x)=n=0∑∞(an+bn)xnαf(x)=n=0∑∞(αan)xn(α为常数)f(x)g(x)=n=0∑∞cnxn，其中ck=k=0∑∞akbn−k，n=0,1,2,⋯
一些公式
在利用生成函数解题的时候，需要用到以下一些公式：
(
a
+
b
)
n
=
∑
i
=
0
n
C
n
i
a
n
−
i
b
i
1
1
−
x
=
∑
n
=
0
n
x
n
(
1
−
x
)
−
k
=
∑
n
=
0
∞
C
n
+
k
−
1
k
−
1
x
n
\begin{aligned} & (a +b)^n = \sum_{i=0}^{n}C_n^ia^{n-i}b^i \\ & \frac{1}{1-x} = \sum_{n=0}^n x^n \\ & (1-x)^{-k} = \sum_{n = 0}^{\infty} C_{n+k-1}^{k-1}x^n \end{aligned}
(a+b)n=i=0∑nCnian−ibi1−x1=n=0∑nxn(1−x)−k=n=0∑∞Cn+k−1k−1xn
注：第三个式子可以由第二个式子两边同时求 k - 1 阶导得到。
一个定理
设
p
(
x
)
p(x)
p(x)，
q
(
x
)
q(x)
q(x) 是关于
x
x
x 的实多项式，且
deg
p
(
x
)
<
deg
q
(
x
)
\deg p(x) < \deg q(x)
degp(x)<degq(x)，多项式
q
(
x
)
q(x)
q(x) 有
k
k
k 重实根
α
\alpha
α，即
q
(
x
)
=
(
x
−
α
)
k
q
1
(
x
)
，
q
1
(
α
)
≠
0
q(x) = (x-\alpha)^k q_1(x)，q_1(\alpha) \neq 0
q(x)=(x−α)kq1(x)，q1(α)=0。则实数
λ
\lambda
λ 与多项式
p
1
(
x
)
p_1(x)
p1(x)，
deg
p
1
(
x
)
<
deg
(
x
−
α
)
k
−
1
q
1
(
x
)
\deg p_1(x) < \deg (x-\alpha)^{k-1}q_1(x)
degp1(x)<deg(x−α)k−1q1(x)，成立：
p
(
x
)
q
(
x
)
=
λ
(
x
−
α
)
k
+
p
1
(
x
)
(
x
−
α
)
k
−
1
q
1
(
x
)
\frac{p(x)}{q(x)} = \frac{\lambda}{(x - \alpha)^k}+\frac{p_1(x)}{(x-\alpha)^{k-1}q_1(x)}
q(x)p(x)=(x−α)kλ+(x−α)k−1q1(x)p1(x)
证明: 令
λ
=
p
(
α
)
q
(
α
)
\lambda = \frac{p(\alpha)}{q(\alpha)}
λ=q(α)p(α)，则
x
=
α
x = \alpha
x=α 是多项式
p
(
x
)
−
λ
q
1
(
x
)
p(x) - \lambda q_1(x)
p(x)−λq1(x) 的根，设：
p
(
x
)
−
λ
q
1
(
x
)
=
(
x
−
α
)
p
1
(
x
)
→
p
(
x
)
=
λ
q
1
(
x
)
+
(
x
−
α
)
p
1
(
x
)
p(x) - \lambda q_1(x) = (x - \alpha)p_1(x) \rightarrow p(x) = \lambda q_1(x)+(x-\alpha)p_1(x)
p(x)−λq1(x)=(x−α)p1(x)→p(x)=λq1(x)+(x−α)p1(x)
就能得到：
p
(
x
)
q
(
x
)
=
λ
q
1
(
x
)
+
(
x
−
α
)
p
1
(
x
)
(
x
−
α
)
k
q
1
(
x
)
=
λ
(
x
−
α
)
k
+
p
1
(
x
)
(
x
−
α
)
k
−
1
q
1
(
x
)
\frac{p(x)}{q(x)} = \frac{\lambda q_1(x)+(x-\alpha)p_1(x)}{(x-\alpha)^k q_1(x)} = \frac{\lambda}{(x - \alpha)^k}+\frac{p_1(x)}{(x-\alpha)^{k-1}q_1(x)}
q(x)p(x)=(x−α)kq1(x)λq1(x)+(x−α)p1(x)=(x−α)kλ+(x−α)k−1q1(x)p1(x)
证毕。
题(们)
- 求下列数列的通项
{
a
n
}
\lbrace a_n \rbrace
{an}
(1) a 0 = 2 ， a 1 = 5 ， a n + 2 = 3 a n + 1 − 2 a n ， n = 0 , 1 , 2 , ⋯ a_0 = 2，a_1 = 5，a_{n+2} = 3a_{n+1} - 2a_n，n=0, 1, 2, \cdots a0=2，a1=5，an+2=3an+1−2an，n=0,1,2,⋯
(2) a 0 = 4 ， a 1 = 3 ， a n + 2 = a n + 1 + 6 a n − 12 ， n = 0 , 1 , 2 , ⋯ a_0 = 4，a_1 = 3，a_{n+2} = a_{n+1} + 6a_n - 12，n=0, 1, 2, \cdots a0=4，a1=3，an+2=an+1+6an−12，n=0,1,2,⋯
(1)：
设原数列的生成函数为
f
(
x
)
f(x)
f(x)：
f
(
x
)
=
a
0
+
a
1
x
+
a
2
x
2
+
a
3
x
3
+
a
4
x
4
+
⋯
−
3
x
f
(
x
)
=
−
3
a
0
x
−
3
a
1
x
2
−
3
a
2
x
3
−
3
a
3
x
4
−
⋯
2
x
2
f
(
x
)
=
2
a
0
x
2
+
2
a
1
x
3
+
2
a
2
x
4
+
⋯
\begin{aligned} f(x) & = a_0 + a_1x + \;\;\; a_2x^2 + \; a_3 x ^3 + \; a_4 x ^4 + \cdots \\ -3xf(x) & = \quad -3a_0x - 3a_1x^2 - 3a_2x^3 - 3a_3 x^4 - \cdots \\ 2x^2f(x) & = \qquad \qquad \ \;\;\;2a_0x^2 + 2a_1 x^3 + 2a_2 x^4 + \cdots \end{aligned}
f(x)−3xf(x)2x2f(x)=a0+a1x+a2x2+a3x3+a4x4+⋯=−3a0x−3a1x2−3a2x3−3a3x4−⋯= 2a0x2+2a1x3+2a2x4+⋯
三式相加得到：
(
1
−
3
x
+
2
x
2
)
f
(
x
)
=
(
a
0
+
a
1
x
−
3
a
0
x
)
+
(
2
a
0
−
3
a
1
+
a
2
)
x
2
+
(
2
a
0
−
3
a
1
+
a
2
)
x
3
+
⋯
(1-3x+2x^2)f(x) = (a_0 + a_1x - 3a_0x) + (2a_0-3a_1+a_2)x^2 + (2a_0-3a_1+a_2)x^3 + \cdots
(1−3x+2x2)f(x)=(a0+a1x−3a0x)+(2a0−3a1+a2)x2+(2a0−3a1+a2)x3+⋯
又因为
a
n
+
2
=
3
a
n
+
1
−
2
a
n
→
2
a
n
−
3
a
n
+
1
+
a
n
+
2
=
0
a_{n+2} = 3a_{n+1} - 2a_n \rightarrow 2a_n - 3a_{n+1} + a_{n+2} = 0
an+2=3an+1−2an→2an−3an+1+an+2=0，所以从
x
2
x^2
x2 项之后都是 0。所以：
(
1
−
3
x
+
2
x
2
)
f
(
x
)
=
(
a
0
+
a
1
x
−
3
a
0
x
)
=
(
2
+
5
x
−
6
x
)
=
2
−
x
(1-3x+2x^2)f(x) = (a_0 + a_1x - 3a_0x) = (2+5x-6x) = 2-x
(1−3x+2x2)f(x)=(a0+a1x−3a0x)=(2+5x−6x)=2−x
所以：
f
(
x
)
=
2
−
x
1
−
3
x
+
2
x
2
f(x) = \frac{2-x}{1-3x+2x^2}
f(x)=1−3x+2x22−x
有根据上面那个定理，我们可以对这个式子进行拆分：
f
(
x
)
=
2
−
x
1
−
3
x
+
2
x
2
=
2
−
x
(
2
x
−
1
)
(
x
−
1
)
=
A
(
2
x
−
1
)
+
B
(
x
−
1
)
\begin{aligned} f(x) = & \frac{2-x}{1-3x+2x^2} = \frac{2-x}{(2x-1)(x-1)} = \frac{A}{(2x-1)} + \frac{B}{(x-1)} \end{aligned}
f(x)=1−3x+2x22−x=(2x−1)(x−1)2−x=(2x−1)A+(x−1)B
对于最后一个等号，我们将等式两边同时乘上
(
2
x
−
1
)
(
x
−
1
)
(2x-1)(x-1)
(2x−1)(x−1)，得到：
2
−
x
=
A
(
x
−
1
)
+
B
(
2
x
−
1
)
2-x = A(x-1) + B(2x-1)
2−x=A(x−1)+B(2x−1)
令
x
=
1
2
x = \frac 12
x=21，得：
2
−
1
2
=
(
1
2
−
1
)
A
+
(
2
⋅
1
2
−
1
)
B
→
A
=
−
3
2 - \frac 12 = (\frac 12 - 1) A + (2\cdot\frac 12 -1)B \rightarrow A = -3
2−21=(21−1)A+(2⋅21−1)B→A=−3
令
x
=
1
x = 1
x=1，得：
2
−
1
=
(
1
−
1
)
A
+
(
2
⋅
1
−
1
)
B
→
B
=
1
2 - 1 = (1 - 1)A +(2 \cdot 1 - 1)B \rightarrow B = 1
2−1=(1−1)A+(2⋅1−1)B→B=1
所以：
f
(
x
)
=
A
(
2
x
−
1
)
+
B
(
x
−
1
)
=
3
1
−
2
x
−
1
1
−
x
=
3
∑
n
=
0
∞
(
2
x
)
n
−
∑
n
=
0
∞
x
n
=
∑
n
=
0
n
(
3
⋅
2
n
−
1
)
x
n
\begin{aligned} f(x) = & \frac{A}{(2x-1)} + \frac{B}{(x-1)} \\ = & \frac{3}{1-2x}-\frac{1}{1-x} = 3\sum_{n=0}^{\infty}(2x)^n - \sum_{n=0}^{\infty}x^n = \sum_{n=0}^n (3\cdot 2^n - 1)x^n \end{aligned}
f(x)==(2x−1)A+(x−1)B1−2x3−1−x1=3n=0∑∞(2x)n−n=0∑∞xn=n=0∑n(3⋅2n−1)xn
所以这个数列的通项就是：
a
n
=
3
⋅
2
n
−
1
a_n = 3 \cdot 2^n - 1
an=3⋅2n−1
(2)：
这原数列的生成函数为
f
(
x
)
f(x)
f(x)：
6
f
(
x
)
=
6
a
0
+
6
a
1
x
+
6
a
2
x
2
+
6
a
3
x
3
+
6
a
4
x
4
+
⋯
x
f
(
x
)
=
a
0
x
+
a
1
x
2
+
a
2
x
3
+
a
3
x
4
+
⋯
x
2
f
(
x
)
=
a
0
x
2
+
a
1
x
3
+
a
2
x
4
+
⋯
12
1
−
x
=
12
+
12
x
+
12
x
2
+
12
x
3
+
12
x
4
+
⋯
\begin{aligned} 6f(x) = & 6a_0 + 6a_1x + 6a_2x^2 + 6a_3x^3 + 6a_4x^4 + \cdots \\ xf(x) = & \quad \; \qquad a_0x + \; a_1x^2 + \;\; a_2x^3 + \;\; a_3 x^4 +\cdots \\ x^2f(x) = & \qquad \qquad \qquad \; a_0x^2 + \;\; a_1x^3 + \;\; a_2x^4 + \cdots \\ \frac{12}{1-x} = & 12 + \quad 12x + \; 12x^2 + \; 12x^3 + \;\; 12x^4 + \cdots \end{aligned}
6f(x)=xf(x)=x2f(x)=1−x12=6a0+6a1x+6a2x2+6a3x3+6a4x4+⋯a0x+a1x2+a2x3+a3x4+⋯a0x2+a1x3+a2x4+⋯12+12x+12x2+12x3+12x4+⋯
与 (1) 同理，得：
(
1
−
x
−
6
x
2
)
f
(
x
)
+
12
1
−
x
=
16
+
11
x
f
(
x
)
=
11
x
+
16
−
12
1
−
x
1
−
x
−
6
x
2
=
−
11
x
2
−
5
x
+
4
1
−
x
(
1
−
3
x
)
(
1
+
2
x
)
=
−
11
x
2
−
5
x
+
4
(
1
−
x
)
(
1
−
3
x
)
(
1
+
2
x
)
\begin{aligned} & (1-x-6x^2)f(x) + \frac{12}{1-x} = 16 + 11x\\ & f(x) = \frac{11x+16 - \frac{12}{1-x}}{1-x-6x^2} = \frac{\frac{-11x^2-5x+4}{1-x}}{(1-3x)(1+2x)} = \frac{-11x^2-5x+4}{(1-x)(1-3x)(1+2x)} \end{aligned}
(1−x−6x2)f(x)+1−x12=16+11xf(x)=1−x−6x211x+16−1−x12=(1−3x)(1+2x)1−x−11x2−5x+4=(1−x)(1−3x)(1+2x)−11x2−5x+4
还是根据那个定理：
f
(
x
)
=
−
11
x
2
−
5
x
+
4
(
1
−
x
)
(
1
−
3
x
)
(
1
+
2
x
)
=
A
1
−
x
+
B
1
−
3
x
+
C
1
+
2
x
f(x) = \frac{-11x^2-5x+4}{(1-x)(1-3x)(1+2x)} = \frac{A}{1-x} + \frac{B}{1-3x} + \frac{C}{1+2x}
f(x)=(1−x)(1−3x)(1+2x)−11x2−5x+4=1−xA+1−3xB+1+2xC
还是和 (1) 同理：
A
=
2
，
B
=
C
=
1
A = 2，B = C = 1
A=2，B=C=1，所以：
f
(
x
)
=
2
1
−
x
+
1
1
−
3
x
+
1
1
+
2
x
=
2
∑
n
=
0
∞
x
n
+
∑
n
=
0
∞
(
3
x
)
n
+
∑
n
=
0
∞
(
−
2
x
)
n
=
∑
n
=
0
∞
[
2
+
3
n
+
(
−
2
)
n
]
x
n
\begin{aligned} f(x) = & \frac{2}{1-x} + \frac{1}{1-3x} + \frac{1}{1+2x} \\ = & 2\sum_{n=0}^{\infty}x^n + \sum_{n=0}^{\infty}(3x)^n + \sum_{n=0}^{\infty}(-2x)^n = \sum_{n=0}^{\infty} [2 + 3^n + (-2)^n]x^n \end{aligned}
f(x)==1−x2+1−3x1+1+2x12n=0∑∞xn+n=0∑∞(3x)n+n=0∑∞(−2x)n=n=0∑∞[2+3n+(−2)n]xn
所以原数列的通项就是：
a
n
=
2
+
3
n
+
(
−
2
)
n
a_n = 2 + 3^n + (-2)^n
an=2+3n+(−2)n
- 证明： ∑ k = 0 n ( C n k ) 2 ( 1 + x ) 2 n − 2 k ( 1 − x ) 2 k \sum\limits_{k=0}^n (C_n^k)^2(1+x)^{2n-2k}(1-x)^{2k} k=0∑n(Cnk)2(1+x)2n−2k(1−x)2k 的展开式中 x x x 的奇数次幂不出现。
我们可以构造一个式子：
[
y
+
(
1
+
x
)
2
]
n
[
y
+
(
1
−
x
)
2
]
n
\left[ y + (1+x)^2 \right]^n\left[ y +(1-x)^2 \right]^n
[y+(1+x)2]n[y+(1−x)2]n
使得这个式子的
y
n
y^n
yn 项前面的系数为：
C
n
n
−
k
[
(
1
+
x
)
2
]
n
−
k
⋅
C
n
k
[
(
1
−
x
)
2
]
k
=
(
C
n
k
)
2
(
1
+
x
)
2
n
−
2
k
(
1
−
x
)
2
k
C_n^{n-k}[(1+x)^2]^{n-k} \cdot C_n^k[(1-x)^2]^k = (C_n^k)^2(1+x)^{2n-2k}(1-x)^{2k}
Cnn−k[(1+x)2]n−k⋅Cnk[(1−x)2]k=(Cnk)2(1+x)2n−2k(1−x)2k
也就是原来的式子中求和里的项。我们现在考虑把我们构造出来的式子展开：
[
y
+
(
1
+
x
)
2
]
n
[
y
+
(
1
−
x
)
2
]
n
=
(
y
+
1
+
x
2
+
2
x
)
n
(
y
+
1
+
x
2
−
2
x
)
n
=
[
(
y
+
1
+
x
2
)
2
−
4
x
2
]
n
\begin{aligned} & \left[ y + (1+x)^2 \right]^n\left[ y +(1-x)^2 \right]^n \\ = & (y+1+x^2+2x)^n(y+1+x^2-2x)^n \\ = & [(y+1+x^2)^2 - 4x^2]^n \end{aligned}
==[y+(1+x)2]n[y+(1−x)2]n(y+1+x2+2x)n(y+1+x2−2x)n[(y+1+x2)2−4x2]n
很显然，这里面 y n y_n yn 的系数中肯定没有 x x x 的奇数次幂。所以原式在每个求和项中都没有 x x x 的奇数次幂，所以原式没有 x x x 的奇数次幂。
证毕。
- 证明：对一切正整数 n n n， ∑ k = 0 [ n + 1 2 ] ( − 1 ) k C n + 1 k C 2 n − 2 k − 1 n = 1 2 n ( n + 1 ) \sum\limits_{k=0}^{\left[\frac{n+1}{2}\right]} (-1)^k C_{n+1}^k C_{2n-2k-1}^n = \frac 12 n(n + 1) k=0∑[2n+1](−1)kCn+1kC2n−2k−1n=21n(n+1)
我们考虑 ( 1 + x ) n + 1 (1+x)^{n+1} (1+x)n+1 中 x n − 1 x^{n-1} xn−1 的系数：
一方面： C n + 1 2 = 1 2 n ( n − 1 ) C_{n+1}^2 = \frac 12 n(n-1) Cn+12=21n(n−1)
另一方面：
(
1
+
x
)
n
+
1
=
(
1
−
x
2
)
n
+
1
(
1
−
x
)
n
+
1
=
∑
k
=
0
n
+
1
C
n
k
(
−
x
2
)
k
∑
i
=
0
∞
C
i
+
n
n
x
i
(1+x)^{n+1} = \frac{(1-x^2)^{n+1}}{(1-x)^{n+1}} = \sum_{k=0}^{n+1}C_n^k(-x^2)^k\sum_{i=0}^{\infty}C_{i+n}^nx^i
(1+x)n+1=(1−x)n+1(1−x2)n+1=k=0∑n+1Cnk(−x2)ki=0∑∞Ci+nnxi
在这个式子里面，前半部分，即
∑
k
=
0
n
+
1
C
n
k
(
−
x
2
)
k
\sum\limits_{k=0}^{n+1}C_n^k(-x^2)^k
k=0∑n+1Cnk(−x2)k 对
x
n
−
1
x^{n-1}
xn−1 项的系数的贡献是
2
k
2k
2k，要想凑出
n
−
1
n-1
n−1，那么后面的贡献就应该是
n
−
2
k
−
1
n-2k-1
n−2k−1，也就是说后面的
i
=
n
−
2
k
−
1
i = n-2k-1
i=n−2k−1 的时候的值就是它的贡献。所以总贡献就是：
∑
k
=
0
[
n
+
1
2
]
(
−
1
)
k
C
n
+
1
k
C
2
n
−
2
k
−
1
n
\sum_{k=0}^{\left[\frac{n+1}{2}\right]}(-1)^kC_{n+1}^kC_{2n-2k-1}^n
k=0∑[2n+1](−1)kCn+1kC2n−2k−1n
所以：
∑
k
=
0
[
n
+
1
2
]
(
−
1
)
k
C
n
+
1
k
C
2
n
−
2
k
−
1
n
=
1
2
n
(
n
−
1
)
\sum_{k=0}^{\left[\frac{n+1}{2}\right]}(-1)^kC_{n+1}^kC_{2n-2k-1}^n = \frac 12 n (n-1)
k=0∑[2n+1](−1)kCn+1kC2n−2k−1n=21n(n−1)
证毕。