0. Intro
这个就是众所周知的Fibonacci数列
用生成函数可以求出该数列的通项公式
1. 生成函数
生成函数分为普通型生成函数(OGF)和指数型生成函数(EGF)，后面默认提到生成函数都是OGF
若有一数列 (A: a_0,a_1,a_2,a_3,cdots) ，则 (A) 的生成函数为
为了熟悉生成函数，先来看一个很基础的例子：
已知数列 (f_n=1) ，求 (f) 的生成函数 (F(x)) 。
直接代到定义式里就好了
发现这里其实就是一个等比数列求和
研究生成函数时我们都假设级数收敛
如果你不知道级数收敛是什么意思 只需要知道生成函数中的 (x) 没有实际意义 所以我们可以任意取值 所以不妨设 (0<x<1)
那么当 (i) 趋向于无穷大时，(x^i) 显然趋于 (0)
于是就得到了一个很简单的式子
同理可以得到三个关于等比数列的生成函数的结论：
数列 (1,q,q^2,q^3,cdots) （下标从0开始，下同）的生成函数是 (F_1(x)=dfrac1{1-qx})
数列 (0,1,q,q^2,q^3,cdots) 的生成函数是 (F_2(x)=dfrac x{1-qx})
数列 (q,q^2,q^3,q^4,cdots) 的生成函数是 (F_3(x)=dfrac q{1-qx}=-dfrac1{x-frac1q})
2. Fibonacci数列通项公式
注意这里的 (f_0=f_1=1) ，和开头的那个不一样，因为这样设推起来更方便
设 (f_n) 的生成函数为 (F(x)) ，那么我们肯定首先要把 (F(x)) 求出来
((1)+(2)-(3)) 得 ((x^2+x-1)F(x)=-1)
所以 (F(x)=dfrac{1}{1-x-x^2})
然而我们并不能由此直接看出 (f) 的通项公式
数列 (1,q,q^2,q^3,cdots) （下标从0开始，下同）的生成函数是 (F_1(x)=dfrac1{1-qx})
数列 (0,1,q,q^2,q^3,cdots) 的生成函数是 (F_2(x)=dfrac x{1-qx})
数列 (q,q^2,q^3,q^4,cdots) 的生成函数是 (F_3(x)=dfrac q{1-qx}=-dfrac1{x-frac1q})
要从生成函数反推出原数列 我们只知道这三个相关的结论
那么我们以这三个结论为目标试着做一些代数变形
分母显然要降次
设方程 (1-x-x^2=0) 的两根为 (x_1=dfrac{-1+sqrt5}2,x_2=dfrac{-1-sqrt5}2) ，则 (1-x-x^2=-(x-x_1)(x-x_2))
而 (dfrac1{x-x_1}-dfrac1{x-x_2}=dfrac{(x-x_2)-(x-x_1)}{(x-x_1)(x-x_2)}=dfrac{x_1-x_2}{(x-x_1)(x-x_2)})
所以 (F(x)=-dfrac1{x_1-x_2}cdotleft(dfrac1{x-x_1}-dfrac1{x-x_2} ight))
其中含 (x) 的部分和 (F_3(x)) 很接近了
先把最前面的负号乘进去
易知 (x_1x_2=-1) ，所以 (x_2=-dfrac1{x_1},x_1=-dfrac1{x_2})
由结论三可知，对于数列 (a_n=(-x_1)^{n+1}) ，它的生成函数是 (G(x)=-dfrac1{x-frac1{-x_1}})
对于数列 (b_n=(-x_2)^{n+1}) ，它的生成函数是 (H(x)=-dfrac1{x-frac1{-x_2}})
这足以说明 (f_n=dfrac{b_n-a_n}{x_1-x_2}) （请读者自行证明）
所以 (f_n=dfrac{(-x_2)^{n+1}-(-x_1)^{n+1}}{x_1-x_2})
将 (x_1=dfrac{-1+sqrt5}2,x_2=dfrac{-1-sqrt5}2) 代入
这样就得到了通项公式
而如果是开头那个版本的斐波拉契数列：
它的通项公式就是
3. 总结
（与前面的内容可能有些出入）
数列 (a_0,a_1,a_2,a_3,cdots) 的普通型生成函数(OGF)（以下称为生成函数）为
首项为 (a) ，公比为 (q) 的等比数列（即 (a,qa,q^2a,q^3a,cdots) ）的生成函数为
当 (a=q) 时可知数列 (q,q^2,q^3,cdots) 的生成函数为
这个结论可以用来推导斐波拉契数列的通项公式
斐波拉契数列的递推式：
（也有 (f_0=f_1=1) 的版本，不唯一）
斐波拉契数列的生成函数（这里 (f_0=f_1=1) ）：
斐波拉契数列的通项公式（这里 (f_0=0,f_1=1) ）