1. 生成函数
对于任意数列\(\{a_n\}\)，函数
\[f(x)=\sum_{n=0}^\infty a_nx^n \]
称为数列\(\{a_n\}\)的普通型生成函数
生成函数中的\(x\)并无实际意义，一般不用考虑是否收敛等情况
2. 广义二项式定理
众所周知，对于一个多项式\((a+b)^n\)，
\[(a+b)^n=\sum_{k=0}^n\binom{n}{k}a^{n-k}b^k\tag{1} \]
其中\(\displaystyle \binom{n}{k}=\frac{n!}{(n-k)!k!}\)
奈何使用阶乘的定义不够优雅，而且难以推广，因此改写上述公式
\[(a+b)^n=\sum_{k=0}^n\frac{n^{\underline{k}}}{k!}a^{n-k}b^k\tag{2} \]
其中\(\displaystyle n^{\underline{k}}=\prod_{i=n-k+1}^ni\)，易知在\(n\)为正整数时\((1)\)与\((2)\)等价
根据\(n^{\underline{k}}\)的定义，易知当\(k>n\)时，\(n^{\underline{k}}=0\)，因此，我们可以将\((2)\)中求和的上限改为\(\infty\)
\[(a+b)^n=\sum_{k=0}^\infty\frac{n^{\underline{k}}}{k!}a^{n-k}b^k\tag{3} \]
3. (某个用得到的)级数
或许有人认为至今我们都只是在摆弄一些符号，重新提了一遍原始的问题，但观察后发现公式\((3)\)对比公式\((1)\)除去了任何关于\(n\)的限制，可以尝试令\(a=1,b=-\lambda x,n=-1\)
\[\begin{split} \frac{1}{1-\lambda x} &=\sum_{k=0}^\infty\frac{(-1)^\underline{k}(-\lambda x)^k}{k!}\\ &=\sum_{k=0}^\infty\frac{k!(-1)^k(-1)^k\lambda^kx^k}{k!}\\ &=\sum_{k=0}^\infty\lambda^kx^k \end{split} \tag{4} \]
观察发现上述公式仅当\(-1<x<1\)时才收敛，或者说“有意义”，但对于下面的操作，这样的公式足矣
4. 求通项
写出斐波那契数列\(\{f_n\}\)的生成函数
\[F(x)=\sum_{k=0}^\infty f_nx^n \]
因为\(f_n=f_{n-1}+f_{n-2}\)
所以\(F(x)=x^2F(x)+xF(x)+x\)
所以
\[F(x)=\frac{1}{1-x-x^2} \]
之前得到了\(\dfrac{1}{1-\lambda x}\)的级数，尝试化为类似形式
设\(1-x-x^2=(1-\lambda_1x)(1-\lambda_2x)\)，解得
\[\begin{cases} \lambda_1=\dfrac{1-\sqrt{5}}{2}\\ \lambda_2=\dfrac{1+\sqrt{5}}{2} \end{cases} \text{或} \begin{cases} \lambda_1=\dfrac{1+\sqrt{5}}{2}\\ \lambda_2=\dfrac{1-\sqrt{5}}{2} \end{cases} \]
不妨设\(\lambda_1=\dfrac{1-\sqrt{5}}{2}, \lambda_2=\dfrac{1+\sqrt{5}}{2}\)
进一步，设\(F(x)=\dfrac{A}{1-\lambda_1x}+\dfrac{B}{1-\lambda_2x}\)，则
\[\begin{align*} A(1-\lambda_2x)+B(1-\lambda_1x)&=1\\ (A+B-1)-(A\lambda_2+B\lambda_1)x&=0 \end{align*} \]
由于生成函数的特性，上述方程左边必须与\(x\)无关，因此只有可能
\[\begin{cases} A+B-1=0\\ A\lambda_2+B\lambda_1=0 \end{cases} \]
解得
\[\begin{cases} A=-\dfrac{\lambda_1}{\sqrt{5}}\\ B=\dfrac{\lambda_2}{\sqrt{5}} \end{cases} \]
所以
\[\begin{split} F(x)&=-\frac{\lambda_1}{\sqrt{5}}\frac{1}{1-\lambda_1x}+\frac{\lambda_2}{\sqrt{5}}\frac{1}{1-\lambda_2x}\\ &=-\frac{\lambda_1}{\sqrt{5}}\sum_{k=0}^\infty\lambda_1^kx^k+\frac{\lambda_2}{\sqrt{5}}\sum_{k=0}^\infty\lambda_2^kx^k\\ &=\frac{\displaystyle\sum_{k=0}^\infty\left(\lambda_2^{k+1}-\lambda_1^{k+1}\right)}{\sqrt{5}} \end{split} \]
此时将\(F(x)\)写成了描述每一项的形式，再将\(\lambda_1,\lambda_2\)带入得出\(f_n=\dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\dfrac{1-\sqrt{5}}{2}\right)^{n+1}}{\sqrt{5}}\)
但是以上内容均是基于\(n\)从\(0\)开始，即\(f_0=f_1=1\)的定义，因此需再改成熟知的从\(1\)开始编号的形式
\[f_n=\dfrac{\left(\dfrac{1+\sqrt{5}}{2}\right)^n-\left(\dfrac{1-\sqrt{5}}{2}\right)^n}{\sqrt{5}} \]
原文地址：http://www.cnblogs.com/KimJeonghui/p/16901258.html
1. 本站所有资源来源于用户上传和网络，如有侵权请邮件联系站长！
2. 分享目的仅供大家学习和交流，请务用于商业用途!
3. 如果你也有好源码或者教程，可以到用户中心发布，分享有积分奖励和额外收入！
4. 本站提供的源码、模板、插件等等其他资源，都不包含技术服务请大家谅解！
5. 如有链接无法下载、失效或广告，请联系管理员处理！
6. 本站资源售价只是赞助，收取费用仅维持本站的日常运营所需！
7. 如遇到加密压缩包，默认解压密码为"gltf",如遇到无法解压的请联系管理员！
8. 因为资源和程序源码均为可复制品，所以不支持任何理由的退款兑现，请斟酌后支付下载
声明：如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性
