递推关系与生成函数
一粒夸克
·
·
个人记录
简单数列
设：
h_0,h_1,h_2,h_3...,h_n,...
表示一个数列，其中 h_n 叫做数列的一般项或通项
我们称 s_i= \sum_{k=0}^n \limits h_k 为 h 数列的部分和
这些部分和形成一个新的数列 s_0,s_1,..s_n,... ，其通项为 s_n
等差数列：
h_0,h_0+q,h_0+2q,...,h_0+nq,...
通项为：
h_n=h_0+nq
部分和为:
s_n=(n+1)h_0+ \frac{qn(n+1)}2
等比数列：
h_0,qh_0,q^2h_0,...,q^nh_0,...
通项为：
h_n=q^nh_0
部分和为:
s_n=\begin{cases}
{\frac {q^{n+1}-1}{q-1}h_0}\ \ \ \ \ \ \ \ (q\ !=1)\\
{(n+1)h_0}\ \ \ \ \ \ \ (q=1)\\
\end{cases}
斐波那契数列：
1. 部分和为：
s_n=\sum_{i=0}^n f_i=f_{n+2}-1
考虑归纳证明：
$$f_0=f_1-1 ⟺ 0=1-1$$
显然成立
若 $s_n=f_{n+2}-1$，有：
$$s_{n+1}=s_n+f_{n+1}=f_{n+1}+f_{n+2}-1=f_{n+3}-1$$
证毕
**2. 通项公式：**
$$f_n=\frac 1 {\sqrt 5}(\frac {1+\sqrt 5}{2})^n-\frac 1 {\sqrt 5}(\frac {1-\sqrt 5}{2})^n$$
证明：
考虑如下形式的递推式
$$f_n-f_{n-1}-f_{n-2}=0$$
先忽略序列的初始值，寻找一种形式为 $f_n=q^n$ 的解
$$q^n-q^{n-1}-q^{n-2}=0$$
$$q^{n-2}(q^2-q-1)=0$$
显然 $q$ 不等于 $1$ ，那么 $q^2-q-1=0
解得 ：
q_1=\frac {1+\sqrt 5}2\ ,\ q_2=\frac {1-\sqrt 5}2
因此，f_n=(\frac {1+\sqrt 5}2)^n 或 f_n=(\frac {1-\sqrt 5}2)^n ，均满足递推关系
进而
f_n=c_0*(\frac {1+\sqrt 5}2)^n+c_1*(\frac {1-\sqrt 5}2)^n
满足递推关系
因此，我们只需求解
\begin{cases}
{c_0+c_1=a}\\
\\
{c_0*\frac {1+\sqrt 5}2+c_1*\frac {1-\sqrt 5}2=b}\\
\end{cases}
即可求得以 a、b 为初值的斐波那契数列的通项
对于 a=1,b=1 的情况，解得：
f_n=\frac 1 {\sqrt 5}(\frac {1+\sqrt 5}{2})^n-\frac 1 {\sqrt 5}(\frac {1-\sqrt 5}{2})^n
证毕
生成函数
绝大部分多项式科技都是在干同一件事 —— 通过代数手段优化卷积
设
h_0,h_1,h_2,h_3...,h_n,...
是无穷数列，它的生成函数定义为无穷级数
g(x)=\sum_{i=0}^{\infty}\limits h_ix^i
对于每一项都是 1 的序列，它的生成函数为：
g(x)=\sum_{i=0}^\infty \limits x^i
由牛顿二项式定理:
(x+y)^n= \sum_{i=0}^\infty \limits \left(\begin{array}{c}a\\ k\end{array}\right)z^k
其中，a 是实数，且
\left(\begin{array}{c}a\\ k\end{array}\right)=\frac {a(a-1)...(a-k+1)}{k!}
令 z=x/y，则 (x+y)^n=y^a(z+1)^a，有：
(1+z)^a=\sum_{i=0}^\infty \left(\begin{array}{c}a\\ k\end{array}\right)z^k
由于：
\left(\begin{array}{c}-n\\ k\end{array}\right)=\frac {-n(-n-1)...(-n-k+1)}{k!}
=(-1)^k\frac {n(n+1)...(n+k-1)}{k!}
=(-1)^k\left(\begin{array}{c}n+k-1\\ k\end{array}\right)
因此：
(1+z)^{-n}=\frac 1 {(1+z)^n}=\sum_{i=0}^\infty (-1)^i\left(\begin{array}{c}n+i-1\\ i\end{array}\right)z^k
令 n=1，有：
\frac 1{1+z}=\sum_{i=0}^\infty (-1)^iz^i
进而：
\frac 1{1-z}=\sum_{i=0}^\infty z^i
因此
g(x)=\sum_{i=0}^\infty \limits x^i= \frac 1 {1-x}
二项式系数\left(\begin{array}{c}m\\ 0\end{array}\right)\left(\begin{array}{c}m\\ 1\end{array}\right)...\left(\begin{array}{c}m\\ m\end{array}\right)的生成函数为：
g(x)=\sum_{i=0}^m\left(\begin{array}{c}m\\ i\end{array}\right)x^i=(1+x)^m
进而，若 a 为实数，对于无穷数列：
\left(\begin{array}{c}a\\ 0\end{array}\right)\left(\begin{array}{c}a\\ 0\end{array}\right)...\left(\begin{array}{c}a\\ n\end{array}\right)...
其生成函数为
g(x)=(1+x)^a=\sum_{i=0}^{\infty}\left(\begin{array}{c}a\\ i\end{array}\right)x^i
设 k 为整数，设数列
h_0,h_1,h_2,h_3...,h_n,...
显然
$$h_n=\left(\begin{array}{c}n+k-1\\ k-1\end{array}\right)$$
它的生成函数是
$$g(x)=\sum_{n=0}^{\infty}\left(\begin{array}{c}n+k-1\\ k-1\end{array}\right)x^n=\frac 1{(1-x)^k}$$
结合前面的证明，有：
$$\frac 1{(1-x)^k}=\prod_{i=1}^{k}\frac{1}{1-x}=\prod_{i=1}^{k}\sum_{e_i=0}^\infty x^{e_i}$$
将每一项取出，发现：
$$\prod_{i=1}^k x^{e_i}=x^n$$
当且仅当：
$$\sum_{i=1}^k e_i=n$$
因此 $\frac 1{(1-x)^k}$ 每一项的系数即为 $e_1+e_2+..+e_k=n$ 的正整数解个数
**例题：**
**求装用苹果、香蕉、橘子和梨填充果篮的方案数 $h_n$，其中苹果数量必须是偶数，香蕉数量必须是 $5$ 的倍数，橘子最多四个，梨最多一个**
类似地，我们可以得到其生成函数：
$$g(x)=(\sum_{i=0}^\infty x^{2i})(\sum_{j=0}^\infty x^{5j})(\sum_{k=0}^4 x^{k})(1+x)$$
$$=\frac 1{1-x^2}\frac{1}{1-x^5}\frac{1-x^5}{1-x}{}(1+x)$$
$$=\frac 1{(1-x)^2}=\sum_{i=0}^\infty \left(\begin{array}{c}i+1\\ i\end{array}\right)x^i=(n+1)x^i$$
因此，我们仅通过代数手段处理数列 $h$ 的生成函数，得到了 $h_i=i+1
生成函数解递推式
*求 $a_n=3a_{n-1}，a_0=2$ 的通项：**
设出其生成函数 G(x)=\sum_{i=0}^\infty \limits a_ix^i
有：
G(x)=a_0+\sum_{i=1}^\infty \limits 3a_{i-1}x*x^{i-1}
=3xG(x)+2
整理得：
(1-3x)G(x)=2
G(x)=\frac 2 {1-3x}=\sum_{i=0}^\infty 2*(3x)^i
因此
a_i=2*3^i
*求 $a_n=8a_{n-1}+10^{n-1}，a_0=1$ 的通项：**
设出其生成函数 G(x)=\sum_{i=0}^\infty \limits a_ix^i
有：
G(x)=a_0+\sum_{i=1}^\infty \limits (8a_{i-1}+10^{i-1})x^{i}
=a_0+\sum_{i=1}^\infty \limits 8a_{i-1}x*x^{i-1}+\sum_{i=1}^\infty \limits 10^{i-1}x^{i}
=a_0+ 8xG(x)+\frac {x}{1-10x}
整理得：
(8x-1)G(x)=-\frac {x}{1-10x}-a_0
(8x-1)G(x)=-\frac {1-9x}{1-10x}
G(x)=\frac {1-9x}{(1-10x)(1-8x)}
=\frac1 2(\frac 1{1-10x}+\frac 1 {1-8x})
=\frac 1 2(\sum_{i=0}^\infty 10^ix^i+\sum_{i=0}^\infty8^ix^i)
=\sum_{i=0}^\infty \frac 1 2(10^i+8^i) x^i
因此
a_i=\frac {10^i+8^1} 2
**关于裂项：**[部分分式展开法](https://zhuanlan.zhihu.com/p/411676642)
**普通生成函数：**[浅谈生成函数之OGF](https://zhuanlan.zhihu.com/p/52817010)
**指数生成函数：**[浅谈生成函数之EGF](https://zhuanlan.zhihu.com/p/53079223)
### [[TJOI2015]概率论](https://www.luogu.com.cn/problem/P3978)
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
int main(){
cin>>n;
printf("%.12lf",1.0*n*(n+1)/2/(2*n-1));
return 0;
}
```