近期学习了数列，便整理了一些生成函数相关的知识，并将其部分基础放在此处。
生成函数
对于一个数列 \(\left\{a_i\right\}\) ，设其生成函数为
\[ \begin{aligned} F(x) &= \sum_{i=0}^{\infty} a_ix^i \\ &= a_0 + a_1x + a_2x^2 + a_3x^3 + a_4x^4 + \cdots \end{aligned} \]
若设数列第一项为 \(a_0\) ，此时 \(a_0\) 即为数列第一项，有其对应意义。此处我们以 \(a_1\) 为数列第一项，因此 \(a_0\) 无意义，仅为保持形式整齐所用，其取值不影响数列。
这样，一个生成函数可以唯一表达一个数列。在此处，生成函数中的 \(x\) 变量仅为形式化表达，其取值可以是任意的，只要存在合法取值使得对其的操作成立即可。
另外对于无穷数列，其生成函数可以不是多项式函数的形式，因为可以在 \(x\) 一定的范围内用无穷多项式函数无限逼近，从而将其转换为多项式函数（即泰勒展开）。
求数列生成函数
将数列所对应的生成函数由无穷多项式转化为分式或其他有限长度形式的过程。
对于斐波那契数列 \(\left\{a_i\right\}\) ，有初始条件 \(a_1 = a_2 = 1\) ， \(a_n = a_{n-1} + a_{n-2}\ \ (n \geqslant 3)\) 。设其生成函数为 \(F(x)\) 。
在数列的递推式中，涉及 \(a_n, a_{n-1}\) 和 \(a_{n-2}\) ，故在这里可以列出 \(F(x), xF(x)\) 和 \(x^2F(x)\) 的表。
\[\begin{alignedat}{5} F(x) &=\ &x + &x^2& + &2&x^3& + &3&x^4 + 5&x^5 + 8&x^6 + \cdots \\ xF(x) &=\ & &x^2& + &&x^3& + &2&x^4 + 3&x^5 + 5&x^6 + \cdots \\ x^2F(x) &=\ & & & &&x^3& + &&x^4 + 2&x^5 + 3&x^6 + \cdots \\ \end{alignedat}\]此处可以发现
\[F(x) = xF(x) + x^2F(x) + x\]
此公式中包含了斐波那契数列的初始条件和递推公式的所有信息。
故有
\[F(x) = \dfrac{x}{1-x-x^2}\]
即为斐波那契数列的生成函数。
求数列通项公式
裂项简化
利用生成函数，可以将数列的有限长生成函数转换为通项公式，其要点在于将生成函数重新化为无限长多项式的形式，并求出其 \(x^i\) 系数 \(a_i\) 的通项公式。由生成函数的定义， \(a_i\) 即为数列第 \(i\) 项。
对于 \(F(x)\) ，注意到其分子为 \(x\) ，分母 \(\Delta > 0\) ，故可以因式分解并化简为两分式之和，具体见下。
\[\begin{aligned} F(x) &= \dfrac{x}{1-x-x^2} \\ &= -\dfrac{x}{\left(x-\frac{\sqrt{5}-1}{2}\right)\left(x+\frac{\sqrt{5}+1}{2}\right)} \\ &= -\dfrac{1}{\sqrt{5}}\left(\dfrac{1}{\frac{\sqrt{5}-1}{2}x+1} + \dfrac{1}{\frac{\sqrt{5}+1}{2}x-1}\right) \end{aligned}\]由生成函数定义可知两生成函数相加得到的结果，其对应的数列每一元素也与原来两个数列对应位置相加的元素大小相同，即生成函数的可加性。也可形式化表达为：若 \(\left\{a_i\right\}\) 对应生成函数是 \(F_1(x)\) ， \(\left\{b_i\right\}\) 对应生成函数是 \(F_2(x)\) ，则有 \(\left\{a_i +b_i\right\}\) 对应的生成函数为 \(F_1(x) + F_2(x)\) 。同理，亦可证明生成函数的可数乘性。
由生成函数的可加性和可数乘性，我们可以分别计算 \(F(x)\) 两个小分式对应的数列，再最后相加（减）求得斐波那契通项公式。
由生成函数到数列
注意到所要求的两个小分式都是 \(\dfrac{1}{ax+b}\) 的结构，只要求出此分式所对应的数列即可。在此，我们分别用初等和高等方法给出其解。
设 \(G(x) = \dfrac{1}{ax+b}\) ，其对应的原数列是 \(\left\{g_i\right\}\) 。
故有
\[ \dfrac{1}{ax+b} = \sum^\infty_{i=0}g_ix^i \]
法一
已知
\[ (1+x+x^2+x^3+\cdots + x^n)(1-x) = 1-x^{n+1} \]
即
\[ 1+x+x^2+x^3+\cdots +x^n = \dfrac{1-x^{n+1}}{1-x} \]
当 \(n \to \infty\) 时，即有
\[ 1+x+x^2+x^3+\cdots = \dfrac{1}{1-x} \]
将 \(x\) 替换为 \(-x\) 代入，即有
\[ \dfrac{1}{x+1} = 1-x+x^2-x^3+\cdots \]
两侧同乘 \(\dfrac{1}{b}\)
\[ \dfrac{1}{bx+b} = \dfrac{1}{b}\left(1-x+x^2-x^3+\cdots\right) \]
再将 \(x\) 替换为 \(\dfrac{a}{b}x\) 代入，有
\[ \begin{aligned} \dfrac{1}{ax+b} &= \dfrac{1}{b}\left(1-\dfrac{a}{b}x+\dfrac{a^2}{b^2}x^2-\dfrac{a^3}{b^3}x^3+\cdots\right) \\ &= \dfrac{1}{b}-\dfrac{a}{b^2}x+\dfrac{a^2}{b^3}x^2-\dfrac{a^3}{b^4}x^3+\cdots \end{aligned} \]
故有 \(x^n\) 系数 \(g_n\) 为
\[ g_n = (-1)^na^nb^{-n-1} \]
法二
若要求 \(g_n\) ，可以做以下操作：
先对两边求 \(n\) 阶导。对于左式而言，其实非常简单，若不能够理解，亦可以列表发现以下规律：
\[ \begin{aligned} G^{(1)}(x) &= -a(ax+b)^{-2} \\ G^{(2)}(x) &= 2a^2(ax+b)^{-3} \\ G^{(3)}(x) &= -6a^3(ax+b)^{-4} \\ G^{(4)}(x) &= 24a^4(ax+b)^{-5} \\ &\ \ \vdots \\ G^{(n)}(x) &= (-1)^n \cdot n! \cdot a^n \cdot (ax+b)^{-n-1} \\ \end{aligned} \]
对于右侧，多项式求导亦不难。
\[ G^{(n)}(x) = \sum^\infty_{i=n}\dfrac{i!}{(i-n)!} g_ix^{i-n} \]
在此，考虑到取 \(x=0\) 时等式左右仍成立，且较为易算，不妨取 \(x=0\) ，代入则有
\[ (-1)^n \cdot n! \cdot a^n \cdot b^{-n-1} = n! \cdot g_n \]
其中式右侧多项式非常数项全部被消除。整理得
\[g_n = (-1)^na^nb^{-n-1}\]
即为所求。另：利用泰勒级数或麦克劳林级数亦可得到此式，且此式即为麦克劳林级数的 \(n\) 次系数。
将此结果代入到原两个小分式中，有
\[ \begin{aligned} A=\dfrac{1}{\frac{\sqrt{5}-1}{2}x+1}:\quad\quad&\left\{\left(\frac{1-\sqrt{5}}{2}\right)^n\right\} \\ B=\dfrac{1}{\frac{\sqrt{5}+1}{2}x-1}:\quad\quad&\left\{-\left(\frac{1+\sqrt{5}}{2}\right)^n\right\} \\ \end{aligned} \]
又有 \(F(x) = -\dfrac{1}{\sqrt{5}}\left(A +B\right)\) ，故有原斐波那契数列的第 \(n\) 项大小为
\[ a_n = \dfrac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n\right] \]
2021-03-07 Update: 增加了初等方法推导数列。