斐波那契数列的通项公式（母函数法）

2022-06-30 15:03 作者:げいしも_芸 0人读过 | 我要投稿

预备知识：

斐波那契数列的性质：

$f_n%3Df_%7Bn-1%7D%2Bf_%7Bn-2%7D%EF%BC%88n%5Cgeq%202%EF%BC%89$

$%E9%BB%84%E9%87%91%E5%88%86%E5%89%B2%E6%AF%94%5Cvarphi%3D%5Cfrac%7B1%2B%5Csqrt5%7D2%E6%BB%A1%E8%B6%B3%5Cfrac1%7B%5Cvarphi%7D%2B%5Cvarphi%3D%5Csqrt5%EF%BC%8C%5Cfrac1%7B%5Cvarphi%7D-%5Cvarphi%3D-1$

（注：下文方法来自3Bule1Brown，详见BV1R34y1W7Xn，09：30处）

构建一函数：

$F(x)%3D%5Csum_%7Bn%3D0%7D%5E%E2%88%9Ef_nx%5En%3D0%2B1x%2B1x%5E2%2B2x%5E3%2B3x%5E4%2B5x%5E5%2B%E2%80%A6$

发现：

$xF(x)%3D0x%2B1x%5E2%2B1x%5E3%2B2x%5E4%2B3x%5E5%2B5x%5E6%2B%E2%80%A6$

$x%5E2F(x)%3D0x%5E2%2B1x%5E3%2B1x%5E4%2B2x%5E5%2B3x%5E6%2B5x%5E7%2B%E2%80%A6$

注意到：

$xF(x)%2Bx%5E2F(x)%3D0%2B0x%2B1x%5E2%2B2x%5E3%2B3x%5E4%2B5x%5E5%2B%E2%80%A6$

$%3DF(x)-x$

于是有：

$F(x)-x%3DxF(x)%2Bx%5E2F(x)$

$%E8%A7%A3%E5%BE%97%EF%BC%9AF(x)%3D%5Cfrac%7Bx%7D%7B1-x-x%5E2%7D$

下面对这个式子进行变形：

$F(x)%3D%5Cfrac%20x%7B1-x-x%5E2%7D%3D%5Cfrac%7B%5Csqrt5(1%2B%5Cfrac1%5Cvarphi%20x-1%2B%5Cvarphi%20x)%7D%7B5(1-%5Cvarphi%20x)(1%2B%5Cfrac%201%5Cvarphi%20x)%7D$

$%3D%5Cfrac%7B%5Csqrt5(1%2B%5Cfrac1%5Cvarphi%20x)-%5Csqrt5(1-%5Cvarphi%20x)%7D%7B%5Csqrt5(1-%5Cvarphi%20x)%5Ccdot%20%5Csqrt5(1%2B%5Cfrac1%5Cvarphi%20x)%7D%3D%5Cfrac1%7B%5Csqrt%205%7D(%5Cfrac1%7B1-%5Cvarphi%20x%7D-%5Cfrac1%7B1%2B%5Cfrac1%5Cvarphi%20x%7D)$

$%E8%BF%99%E9%87%8C%E7%94%A8%E5%88%B0%E4%B8%80%E4%B8%AA%E5%85%AC%E5%BC%8F%EF%BC%9A%5Cfrac1%7B1-%5Clambda%20x%7D%3D%5Csum_%7Bn%3D0%7D%5E%E2%88%9E%5Clambda%20%5Enx%5En$

$%E5%88%99F(x)%3D%5Cfrac1%7B%5Csqrt5%7D(%5Csum_%7Bn%3D0%7D%5E%E2%88%9E%5Cvarphi%20%5Enx%5En-%5Csum_%7Bn%3D0%7D%5E%E2%88%9E(-%5Cfrac1%5Cvarphi%20)%5Enx%5En)%3D%5Csum_%7Bn%3D0%7D%5E%E2%88%9E(%5Cfrac1%7B%5Csqrt5%7D(%5Cvarphi%20%5En-(-%5Cfrac1%5Cvarphi)%5En)x%5En%E2%80%8B%E2%80%8B%E2%80%8B%E2%80%8B%E2%80%8B%E2%80%8B$