Fibonacci的通项

发表于 | 更新于

f(n)=f(n−1)+f(n−2)f(n)=f(n-1)+f(n-2) 定义生成函数为G(x)G(x) G(x)=f1x+f2x2+f3x3+...+fnxn+...G(x)=f_1x+f_2x^2+f_3x^3+...+f_nx^n+... G(x)−f1x−f2x2G(x)-f_1x-f_2x^2 =(f1+f2)x3+(f2+f3)x4+...+(fn−2+fn−1)xn+...=x2G(x)+xG(x)−xf1x=(f_1+f_2)x^3+(f_2+f_3)x^4+...+(f_{n-2}+f_{n-1})x^n+...=x^2G(x)+xG(x)-xf_1x G(x)−x=x2G(x)+xG(x)G(x)-x=x^2G(x)+xG(x) (1−x−x2)G(x)=x(1-x-x^2)G(x)=x G(x)=x1−x−x2=−(x+1−52)(x+1+52)G(x)=\dfrac x{1-x-x^2=-(x+\dfrac{1-\sqrt 5}2)(x+\dfrac{1+\sqrt5}2)} =ax+1−52−bx+1+52=\dfrac a{x+\dfrac{1-\sqrt 5}2}-\dfrac b{x+\dfrac{1+\sqrt5}2} 解得a=5−510,b=5+510a=\dfrac {\sqrt5-5}{10},b=\dfrac {\sqrt5+5}{10} G(x)=5−510x+1−52−5+510x+1+52G(x)=\dfrac {\dfrac {\sqrt5-5}{10}}{x+\dfrac{1-\sqrt 5}2}-\dfrac {\dfrac {\sqrt5+5}{10}}{x+\dfrac{1+\sqrt5}2} =15(11−1+52x−11−1−52x)=\dfrac 1{\sqrt 5}(\dfrac 1{1-\dfrac{1+\sqrt 5}2x}-\dfrac 1{1-\dfrac {1-\sqrt 5}2x}) 根据等比数列求和公式 a+aq+aq2+..+aqn−1=a(1−qn)1−qa+aq+aq^2+..+aq^{n-1}=\dfrac {a(1-q^n)}{1-q} 当−1<q<1-1 < q < 1时 limn→∞qn=0\lim\limits_{n\rightarrow \infty}q^n=0 所以1+x+x2+x3+...=11−x1+x+x^2+x^3+...=\dfrac 1{1-x} 设α=1+52,β=1−52\alpha=\dfrac {1+\sqrt 5}2,\beta=\dfrac {1-\sqrt 5}2 则上式 =15(11−αx−11−βx)=\dfrac 1{\sqrt 5}(\dfrac 1{1-\alpha x}-\dfrac 1{1-\beta x}) 下一步用到的公式的前提条件是∣x∣<1|x|< 1。so?