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}} \] 标签：infty,frac,dfrac,sum,sqrt,斐波,通项,那契,lambda From： https://www.cnblogs.com/KimJeonghui/p/16901258.html