生成函数法求斐波那契数列通项公式 |
您所在的位置：网站首页 › 等比数列求积公式的推导 › 生成函数法求斐波那契数列通项公式 |
|
作用：在无穷级数、函数和数列之间建立关系，通过函数对数列进行操作
举个栗子
对于最简单的一个数列\(\{1,1,1,1,...\}\)，我们可以将其每一项映射到一个函数\(f(x)\)的系数中，即： \[f(x)=1\cdot x^0+1\cdot x^1+1\cdot x^2+... \]其中\(x\)的取值无意义，称为形式幂级数 观察发现，当\(x\in(-1,1)\)时，\(f(x)\)的每一项构成等比数列，由等比数列求和公式得： \[f(x)=\frac{1\cdot(1-x^\infty)}{1-x}=\frac{1}{1-x} \]也就是说，数列\(\{1,1,1,1,...\}\)的生成函数为\(f(x)=\frac1{1-x}\) 同理，对于数列\(\{1,k,k^2,k^3,...\}\)，其生成函数 \[f(x)=k^0\cdot x^0+k^1\cdot x^1+k^2\cdot x^2+...=\frac{1\cdot(1-(kx)^\infty)}{1-kx}=\frac{1}{1-kx} \]因此，如果我们求出了数列\(\{a_n\}\)的生成函数\(f(x)=\frac1{1-kx}\)，那么数列\(\{a_n\}\)即为\(\{1,k,k^2,k^3,...\}\)，\(a_n=k^n\) 你悟了吗（ 普通生成函数的基本运算类比实数的四则运算，生成函数也是有的 对于数列\(\{a_n\}\)、\(\{b_n\}\)，其普通生成函数分别为： \[F(x)=a_0\cdot x^0+a_1\cdot x^1+a_2\cdot x^2+... \\ G(x)=b_0\cdot x^0+b_1\cdot x^1+b_2\cdot x^2+... \]由此， \[\begin{aligned} F(x)+G(x)&=(a_0+b_0)\cdot x^0+(a_1+b_1)\cdot x^1+(a_2+b_2)\cdot x^2+... \\&=\Sigma_{i=0}^{\infty}(a_i+b_i)\cdot x^i \end{aligned} \]这告诉我们，可以将一个数列的生成函数拆成两个数列的生成函数的和，原数列的第\(n\)项即为\(a_n+b_n\) 此外，两个数列的生成函数还能进行“乘法”运算，即：卷积 观察\(F(x)\cdot G(x)\)展开的系数，可以发现：\(x^k\)的系数为\(\Sigma_{i=0}^{k}a_ib_{k-i}\) 因此， \[F(x)\cdot G(x)=\Sigma_{i=0}^{n}x^i\Sigma_{j=0}^{k}a_jb_{k-j} \] |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |