文章未完成，更新较慢，见谅

作为解决组合计数等问题的利器，生成函数常常在数学中的各种地方现形。本文尝试从一个高中学生的角度出发，简单的介绍一些生成函数的相关知识，另一方面也算是自己的学习笔记。由于笔者也是一名高三学生， 文章中可能会出现一些问题与纰漏，欢迎各位在评论区勘误。也欢迎大家在评论区讨论！

想要轻松阅读本文，建议你了解以下预备知识：

下面是一些文中会用到的记号：

为了便于表达与记录，本文所有的数列采用 a_0 为首项。

[命题P] 在 P 为真时取 1 ，否则取 0 。

经过高中数学的学习，我们知道二项式定理：(x+y)^n = \sum_{k=0}^{n}C_n^kx^ky^{n-k} \\

这描述了一个二项式的展开。展开后的形式是什么呢？一个二元多项式。首先让我们只保留一个元，令 y=1 得到：

(x+1)^n = \sum_{k=0}^{n}C_n^kx^k \\

这是二项式的代数意义，接下来让我们看看与其紧密相关的二项分布：X \, \sim \, B(n,p) \;\;\;\;\;\; P\{X=k\} = C_{n}^{k} p^k(1-p)^{n-k} \\

令 q=1-p，容易发现，P\{X=k\} 实际上就是 (p+q)^n 展开式中的的一项。

如果我们把 P\{X=k\} 的系数 C_n^k 看成一个数列中的一项，而不是概率，我们把他改写成 p_k 。并把 (x+1)^n 看成一个关于 x 的函数 P(x)

我们就得到了：

P(x)=\sum_{k=1}^n p_k x^k \\

只研究有限项的求和显然十分没意思，我们把剩下的部分用 0 补齐，得到一个无限级数\displaystyle \sum_k p_kx^k。

P(x)=\sum_{k} p_k x^k = p_0+p_1x^1+p_2x^2+p_3x^3+\cdots \\

我们手头有的是数列的递推关系和初始条件。我们需要做的是求出其通项公式，并且使用生成函数。因此我们需要做的是：

思路实际上还挺清晰的，让我们开始吧。

首先设 F(z)=\sum_k f_kz^k . 下一步我们要把递推关系转化成函数关系。

这是一个线性递推，关键在于如何处理 f_{n-1} 与 f_{n-2} 。如果你还记的生成函数的运算的话，其实这两个玩意儿的生成函数就是 zF(z) 与 z^2F(z) 了。然后把递推式转换得到：

f_n=f_{n-1}+f_{n-2} \implies F(z)=zF(z)+z^2F(z) \\

接着消去 F(n) 得到 1=z+z^2 。嗯？？不对啊，我们不是要求 F(z) 吗？怎么消掉了？甚至求出了具体的 z 值？

事实上，满足这个递推式的数列有无数个，而把数列确定下来的条件在于初始条件。之前我们说过，把负的次数的系数用 0 替换，这规避了平移数列时带来的定义问题。这个时候，只需要令 f_1=1 就有 f_2=f_1+f_0=1，于是可以确定这个数列。我们可以用 [n=1] 补充完整递推式得到，同时对应的生成函数也会多一项 z ：

\begin{align*} &f_n=f_{n-1}+f_{n-2} +[n=1] \\ &\implies F(z) = zF(z) + z^2F(z) + z \\ &\implies F(z) = \frac{z}{1-z-z^2} \end{align*}\\

至此，不算太麻烦，我们已经求出了 \{f_n\} 的生成函数。最后一步要做的找到这个生成函数对应的数列了。是的，这个函数看起来有点复杂，无法一眼看出原数列。不过，既然我们知道生成函数的定义，不妨一步一步的来拆解掉。

对于分子的 z，其作用相当于平移数列，可以暂时放在一边。观察剩余的式子 \displaystyle \frac{1}{1-z-z^2}，记两根为 \phi 与 \hat\phi， 可以将其因式分解为 \displaystyle \frac{1}{(1-\phi z)}\frac{1}{(1-\hat\phi z)}，这个 \displaystyle\frac{1}{1-cz} 的形式就是我们所熟悉的了，将其展开成和式：

F(z)=z\frac{1}{(1-\phi z)}\frac{1}{(1-\hat\phi z)}=z\sum_k \phi^kz^k\sum_k\hat\phi^k z^k \\

两个和式的乘法有点吓人。但这里事实上是一个卷积，我们可以用多项式乘法来理解。两者相乘后仍然是一个多项式。那么结果中 z^m 一项应该是由两和式中所有 次数相加为 m 的项 相乘后相加得到（其实这也是数列卷积的定义），接着再把 z 放回去平移一下系数，也就是：

=z\sum_k(\sum_{i=0}^k \phi^i\hat\phi^{k-i})z^k= \sum_k(\sum_{i=0}^{k} \phi^i\hat\phi^{k-i})z^{k+1}\\

然后我们就得到 f_{n+1}=\sum_{i=0}^{n} \phi^i\hat\phi^{n-i}，如何处理这个和式呢？试试先把常数提出来：

=\hat\phi^{n}\sum_{i=0}^{n} \left( \frac{\phi}{\hat\phi}\right)^i \\

是一个等比数列求和！接下来的事就好办了：

=\hat\phi^n\frac{1-\frac{\phi^{n+1}}{\hat\phi^{n+1}}}{1-\frac{\phi}{\hat\phi}}=\frac{1}{\hat\phi}\frac{\hat\phi^{n+1}-\phi^{n+1}}{1-\frac{\phi}{\hat\phi}}=\frac{\hat\phi^{n+1}-\phi^{n+1}}{\hat\phi-\phi} \\

所以有：

f_{n+1}=\frac{\phi^{n+1}-\hat\phi^{n+1}}{\phi-\hat\phi} \\

换一下下标就是：

f_{n}=\frac{\phi^{n}-\hat\phi^{n}}{\phi-\hat\phi}=\frac{\phi^{n}-\hat\phi^{n}}{\sqrt{5}} \\

问题解决！

\color{gray}{\mathcal{SOLVED}} \\