前置知识
在介绍生成函数前，读者需了解以下概念。此部分的基本概念仅供简单回顾，如需详细了解请自行搜索。
-
自然常数 \(e\)，\(e=\lim \limits_{x\rightarrow \infty}(1+\frac{1}{x})^x\).
-
\(\ln\) 运算。即以 \(e\) 为底的对数。
-
导数。即函数的瞬时变化率。即 \(\lim \limits_{\Delta x\rightarrow0}\frac{\Delta y}{\Delta x}\)，求解一个函数的导函数也是必须内容，这里不再赘述，读者请自行搜索。同时，导数也具有一些运算性质，这里简单列举几点。
- \([cf(x)]'=cf'(x)\)
- \([f(x)+g(x)]'=f'(x)+g'(x)\)
- \([f(x)-g(x)]'=f'(x)-g'(x)\)
- \([f(x)\times g(x)]'=f(x)g'(x)+g(x)f'(x)\)
- \([\frac{f(x)}{g(x)}]'=\frac{f'(x)g(x)-g'(x)f(x)}{g^2(x)}\)
- 令 \(u=g(x),[f(g(x))'=f'(u)\times g'(x)]\)
-
牛顿迭代。牛顿迭代法用于求解函数零点。也就是求函数 \(f(x)=0\) 的解。我们在图像上随意选择一个点 \(p\)，过点 \(p\) 作函数的切线。这条切线与 \(x\) 轴的交点一定比原来的点更接近答案。容易发现，这条切线就是导数。
满足 \(f'(x_0)=\frac{\Delta y}{\Delta x}=\frac{f(x)-f(x_0)}{x-x_0}\) ,即 \(x=x_0-\frac{f(x_0)}{f'(x_0)}\) 更多用法请自行搜索，这里不再赘述。
-
多项式：
对于求和式 \(\sum a_{n^{x^n}}\)，如果是有限项相加，称为多项式。记作 \(f(x)=\sum\limits_{n=0}^m a_{n^{x^n}}\).
定义
定义多项式 \(A(x)\) 的系数数列为 \(A\)，则称 \(A(x)\) 为数列 \(A\) 的生成函数。
\(A(x)=\sum \limits_{k=0}^{+\infty}A_kx^k=A_0+A_1x+A_2x+A_3x+\dots\)
当然，这样的定义过于抽象，我们来举个例子。
对于数列 \(\{1,1,1,1\dots\}\)，它的生成函数 \(F(x)=1+x+x^2+x^2+x^3+\dots\)，易得
\(xF(x)=x+x^2+x^3+\dots\)
即 \(xF(x)-F(x)=1\).
解得 \(f(x)=\frac{1}{1-x}\).
也就是 \(1+x+x^2+x^3+x^4+\dots=\frac{1}{1-x}(|x|<1)\).
可以看出，数列作生成函数的系数。
一般来说，当多项式中含有求和或者无限项，我们不好分析。此时，我们可以将其转换为封闭形式，也就是含有有限项的形式。上述转化恰好体现了这一点。
简单例题
数列 \(\{a_n\}\) 满足 \(a_0=0,a_n=3a_{n-1}+2 (n\geq 1)，\)求数列的通项公式。
注意到数列是无限延申的，我们考虑利用生成函数将其封闭。
定义 \(A(x)=\sum \limits_{k=0}^{+\infty}a_k {x^{k}}\)，则。
\[A(x)=a_1x+a_2x^2+a_3x^3\dots \]将条件代入，且将 \(2\) 提出，得：
\[A(x)=0+3a_0x+3a_1x^2+3a_2x^2+\dots+2+2x+2x^2+2x^3\dots \]（这一步如果不理解可以自行推导一下）
我们发现，对于前半部分和后半部分，都可以分别提出公因式，最终得：
\[A(x)=3x A(x)+ \frac{2x}{1-x} \]当然需要移项，最终，通过生成函数，我们得到了它的封闭形式。
\[A(x)=\frac{2x}{(1-3x)(1-x)} \] 标签：dots,frac,函数,limits,2x,生成,数学,Delta From： https://www.cnblogs.com/SXqwq/p/18261344