C4 递推关系与生成函数
S0 斐波那契数列
1）递推公式：
f
n
+
2
=
f
n
+
1
+
f
n
,
f
0
=
0
,
f
1
=
1
f_{n+2} = f_{n+1}+f_n,f_0 = 0,f_1 = 1
f
n
+
2
=
f
n
+
1
+
f
n
,
f
0
=
0
,
f
1
=
1
2）通项公式：
f
n
=
1
5
[
(
1
+
5
2
)
n
−
(
1
−
5
2
)
n
]
f_n = \frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n – (\frac{1-\sqrt{5}}{2})^n]
f
n
=
5
1
[
(
2
1
+
5
)
n
−
(
2
1
−
5
)
n
]
3）与二项式系数关系：
f
n
=
∑
k
=
0
n
−
1
C
n
−
1
−
k
k
f_n = \sum\limits_{k=0}^{n-1}C_{n-1-k}^k
f
n
=
k
=
0
∑
n
−
1
C
n
−
1
−
k
k
，即 Pascal 三角形从左下到右上每条线的和
4）部分和：
S
n
=
f
n
+
2
−
1
S_n = f_{n+2}-1
S
n
=
f
n
+
2
−
1
S1 生成函数
1）生成函数：
f
(
x
)
=
∑
k
=
0
∞
a
k
x
k
f(x) = \sum\limits_{k=0}^\infin a_k x^k
f
(
x
)
=
k
=
0
∑
∞
a
k
x
k
-
Sn
=
∑
k
=
0
n
a
k
S_n=\sum\limits_{k=0}^na_k
S
n
=
k
=
0
∑
n
a
k
的生成函数：
f(
x
)
1
−
x
\frac{f(x)}{1-x}
1
−
x
f
(
x
)
-
kk
k
元无限多重集
nn
n
组合（
∑i
=
1
k
c
i
x
i
=
n
\sum\limits_{i=1}^k c_ix_i = n
i
=
1
∑
k
c
i
x
i
=
n
的非整数解）个数：
g(
x
)
=
∏
i
=
1
k
1
1
−
x
c
i
g(x) =\prod\limits_{i=1}^k\frac{1}{1-x^{c_i}}
g
(
x
)
=
i
=
1
∏
k
1
−
x
c
i
1
解题时有时可化简，如
(1
+
x
1
+
x
1
2
+
⋯
+
x
1
n
)
=
(
1
−
x
1
n
+
1
)
/
(
1
−
x
1
)
(1+x_1+x_1^2+\cdots+x_1^n) = (1-x_1^{n+1})/(1-x_1)
(
1
+
x
1
+
x
1
2
+
⋯
+
x
1
n
)
=
(
1
−
x
1
n
+
1
)
/
(
1
−
x
1
)
-
{1
,
⋯
,
n
}
\{1,\cdots,n\}
{
1
,
⋯
,
n
}
的逆序数为
tt
t
的排列：
g(
x
)
=
∏
k
=
1
n
(
1
−
x
k
)
(
1
−
x
)
n
g(x) = \frac{\prod\limits_{k=1}^n(1-x^k)}{(1-x)^n}
g
(
x
)
=
(
1
−
x
)
n
k
=
1
∏
n
(
1
−
x
k
)
2）指数生成函数：
g
e
(
x
)
=
∑
k
=
0
∞
a
k
x
k
k
!
g_e(x) = \sum\limits_{k=0}^\infin \frac{a_k x^k}{k!}
g
e
(
x
)
=
k
=
0
∑
∞
k
!
a
k
x
k
-
kk
k
元无限多重集
nn
n
排列：
ge
(
x
)
=
∏
i
=
1
k
f
i
(
x
)
,
f
i
(
x
)
=
∑
j
=
0
∞
x
c
i
j
(
c
i
j
)
!
g_e(x) = \prod\limits_{i=1}^k f_{i}(x),f_i(x) = \sum\limits_{j=0}^\infin\frac{x^{c_ij}}{(c_ij)!}
g
e
(
x
)
=
i
=
1
∏
k
f
i
(
x
)
,
f
i
(
x
)
=
j
=
0
∑
∞
(
c
i
j
)
!
x
c
i
j
S2 递推关系
1）线性递推：
h
n
=
a
1
h
n
−
1
+
a
2
h
n
−
2
+
⋯
+
a
k
h
n
−
k
+
a
0
h_n = a_1 h_{n-1} + a_2h_{n-2}+\cdots+ a_kh_{n-k}+a_0
h
n
=
a
1
h
n
−
1
+
a
2
h
n
−
2
+
⋯
+
a
k
h
n
−
k
+
a
0
-
ak
≠
0
a_k\neq 0
a
k
=
0
，
ai
=
f
(
n
)
a_i =f(n)
a
i
=
f
(
n
)
2）常系数齐次线性递推：
-
齐次递推：
a0
=
0
a_0 = 0
a
0
=
0
-
常系数递推：
ai
∈
R
a_i \in \mathbb{R}
a
i
∈
R
-
求解：
-
特征方程法：
-
特征方程为：
xk
=
a
1
x
k
−
1
+
⋯
+
a
k
x^k = a_1 x^{k-1}+\cdots +a_k
x
k
=
a
1
x
k
−
1
+
⋯
+
a
k
-
求
kk
k
个根
q1
,
⋯
,
q
k
q_1,\cdots,q_k
q
1
,
⋯
,
q
k
，重数为
s1
,
⋯
,
s
k
s_1,\cdots,s_k
s
1
,
⋯
,
s
k
-
解为
∑i
=
1
k
∑
j
=
0
s
i
−
1
c
i
j
n
j
q
i
n
\sum\limits_{i=1}^k\sum\limits_{j=0}^{s_i -1}c_{ij}n^j{q_i}^n
i
=
1
∑
k
j
=
0
∑
s
i
−
1
c
i
j
n
j
q
i
n
-
特征方程为：
-
生成函数法：由
(1
−
∑
i
=
1
k
a
i
x
i
)
g
(
x
)
=
C
(1-\sum\limits_{i = 1}^ka_i x ^ i)g(x) =C
(
1
−
i
=
1
∑
k
a
i
x
i
)
g
(
x
)
=
C
求得-
适用条件：
(1
−
∑
i
=
1
k
a
i
x
i
)
g
(
x
)
=
g
(
x
)
q
(
x
)
=
p
(
x
)
(1-\sum\limits_{i = 1}^ka_i x ^ i)g(x) =g(x)q(x) = p(x)
(
1
−
i
=
1
∑
k
a
i
x
i
)
g
(
x
)
=
g
(
x
)
q
(
x
)
=
p
(
x
)
而
p(
x
)
p(x)
p
(
x
)
是多项式 -
原理：
f(
x
)
=
p
(
x
)
q
(
x
)
f(x) = \frac{p(x)}{q(x)}
f
(
x
)
=
q
(
x
)
p
(
x
)
，
p,
q
p,q
p
,
q
为多项式，则其唯一确定一个数列
p(
x
)
=
d
0
+
d
1
x
+
⋯
+
d
k
−
1
x
k
−
1
p(x) = d_0 + d_1 x + \cdots + d_{k-1}x^{k-1}
p
(
x
)
=
d
0
+
d
1
x
+
⋯
+
d
k
−
1
x
k
−
1
q(
x
)
=
b
0
+
b
1
x
+
⋯
+
b
k
x
k
q(x) = b_0 + b_1 x + \cdots + b_k x^k
q
(
x
)
=
b
0
+
b
1
x
+
⋯
+
b
k
x
k
得
d0
+
d
1
x
+
⋯
+
d
k
−
1
x
k
−
1
=
(
b
0
+
b
1
x
+
⋯
+
b
k
x
k
)
∗
∑
k
=
0
∞
h
k
x
k
d_0 + d_1 x + \cdots + d_{k-1}x^{k-1} = (b_0 + b_1 x + \cdots + b_k x^k)*\sum\limits_{k=0}^\infin h_kx^k
d
0
+
d
1
x
+
⋯
+
d
k
−
1
x
k
−
1
=
(
b
0
+
b
1
x
+
⋯
+
b
k
x
k
)
∗
k
=
0
∑
∞
h
k
x
k
可得
hn
+
b
1
b
0
h
n
−
1
+
⋯
+
b
k
b
0
h
n
−
k
=
0
h_n+\frac{b_1}{b_0} h_{n-1}+\cdots + \frac{b_k}{b_0}h_{n-k} = 0
h
n
+
b
0
b
1
h
n
−
1
+
⋯
+
b
0
b
k
h
n
−
k
=
0
-
与特征方程关系：
xk
r
(
1
x
)
=
q
(
x
)
x^kr(\frac{1}{x}) = q(x)
x
k
r
(
x
1
)
=
q
(
x
)
，即
q(
x
)
q(x)
q
(
x
)
的根是
r(
x
)
r(x)
r
(
x
)
的根的倒数
-
-
特征方程法：
3）常系数非齐次线性递推关系
-
常规解法：
- 求对应齐次解
-
求一非齐次解（时域经典法）
-
若
bn
b_n
b
n
是
nn
n
的
kk
k
次多项式，设
hn
h_n
h
n
为
kk
k
次多项式 -
若
bn
b_n
b
n
是指数函数
rn
r^n
r
n
，-
若
rr
r
不是特征根，设
hn
=
c
r
n
h_n= cr^n
h
n
=
c
r
n
-
若
rr
r
是
kk
k
重特征根，设
hn
=
r
n
∑
i
=
0
k
c
i
n
i
h_n = r^n\sum\limits_{i=0}^kc_in^i
h
n
=
r
n
i
=
0
∑
k
c
i
n
i
-
若
-
若
bn
=
p
(
n
)
r
n
b_n = p(n)r^n
b
n
=
p
(
n
)
r
n
，
rr
r
是
mm
m
重根，
p(
n
)
p(n)
p
(
n
)
是
pp
p
次多项式，特解为
rn
[
c
0
n
m
+
⋯
+
c
p
n
m
+
p
]
r^n[c_0n^m+\cdots+c_pn^{m+p}]
r
n
[
c
0
n
m
+
⋯
+
c
p
n
m
+
p
]
-
若
- 通解 = 特解 + 齐次解
- 生成函数法
- 观察 + 数学归纳法
4）非线性递推：
-
将
n+
1
n+1
n
+
1
多边形完全分割为多个三角形的分法：
hn
=
∑
k
=
1
n
−
1
h
n
h
n
−
k
=
1
n
C
2
n
−
2
n
−
1
(
n
≥
2
)
,
h
1
=
h
2
=
1
h_n = \sum\limits_{k=1}^{n-1}h_nh_{n-k}=\frac{1}{n}C_{2n-2}^{n-1}(n\ge 2),h_1=h_2 = 1
h
n
=
k
=
1
∑
n
−
1
h
n
h
n
−
k
=
n
1
C
2
n
−
2
n
−
1
(
n
≥
2
)
,
h
1
=
h
2
=
1
- 即卡特兰数
-
对应生成函数
g(
x
)
2
=
g
(
x
)
−
x
g(x)^2 = g(x)- x
g
(
x
)
2
=
g
(
x
)
−
x