如何通过生成函数推导斐波那契数列的通项公式？

生成函数总结 前言 生成函数是什么啊？能吃吗？ 生成函数（generating function），又称母函数，是一种形式幂级数，其每一项的系数可以提供关于这个序列的信息。——oi-wiki 太晦涩了，简而言之，对于一个序列，其生成函数就是以这个序列为系数的多项式。 举个栗子🌰：对于序列 \(A=<0,1,2,3,4,5,\ldots>\) ，其普通生成函数为 \(\sum_{i=0}^{+\infty}A_ix^i=\sum_{i=0}^{+\infty}ix^i\)，而对于序列 \(B=<1,2,3,4,5,\ldots>\)，其普通生成函数为 \(\sum_{i=0}^{+\infty}(i+1)x^i\)。 所以这玩意儿有什么用？用处可大了，至少在我目前看来，生成函数就有两种作用： 能够计算一个序列的第 \(n\) 项的系数，可以用来求通项公式。 广泛运用于组合数学。 形式幂级数 在生成函数的定义里面有一个词叫做形式幂级数。能吃吗？ 先讲讲什么是幂级数叭 幂级数是指级数的每一项均为与级数项序号 \(n\) 相对应的以常数倍的 \((x−a)\) 的 \(n\:(n\in \N)\) 次方。 比如 \[A(x)=\sum_{i\geq 0}a_i(x-x_0)^i \] 它与多项式不同的一点在于多项式只有有限项的系数是非零的。 接着讲形式幂级数 其意思就是：对于我们生成的这个多项式来说，其中的变量 \(x\) 只是作为一个符号而已，只是一个形式，它的取值并不重要，我们关心的只是它所携带的信息而已。好惨一变量…… 就比如在最简单的生成函数方案统计问题中，其指数就是我们要求的方案，而其系数就是答案。后面讲生成函数的时候会细讲。 生成函数 生成函数可以分为很多种，但是用的最广泛的还是普通生成函数和指数生成函数。 普通生成函数 \(Ordinary\:Generating\:Function,OGF\) ：普通生成函数。定义为形式幂级数： \[F(x)=\sum_{n\geq0}a_nx^n \] 封闭形式 每次计算都要写一长串的多项式或者写一个 \(\sum\)，太麻烦了，有没有更好的方法？ 自然是有的，我们发现：对于序列 \(<1,1,1,\ldots>\) 的普通生成函数 \(F(x)=\sum_{n\geq 0}x^n\) ，有 \[F(x)\cdot x+1=F(x) \] 解得 \(F(x)=\frac{1}{1-x}\)，所以我们可以用这个来代替原来琐碎的 \(\sum\) 并简化运算。 真是天衣无缝又十分扯淡 这种方法用的非常多，尤其是在求通项公式的时候，比如求斐波那契和卡特兰数的通项公式时就会用到。 二项式定理 但是我们将一个多项式变成封闭形式之后就无法得到第 \(n\) 项的系数了啊。但是没有关系，我们可以用二项式定理将其展开。 \(Generalized\:Binomial\:Theorem:\) 广义二项式定理： \[(x+y)^\alpha=\sum_{k=0}^\infty \left(\begin{matrix}\alpha\\k\end{matrix}\right)x^{\alpha-k}y^k \] 其中 \(\left(\begin{matrix}\alpha\\k\end{matrix}\right)\) 为广义二项式系数（其实就是实数域下的组合数） \[\left(\begin{matrix}\alpha\\k\end{matrix}\right)=\frac{\alpha^{\underline k}}{k!}=\frac{\alpha(\alpha-1)\ldots(\alpha-k+1)}{k!},\alpha\in\R,k\in\N \] \(\alpha^{\underline k}\) 表示 \(\alpha\) 的 \(k\) 次下降幂，即 \(\alpha(\alpha-1)\ldots(\alpha-k+1)\)。上升幂类似。