■漸化式(その5)

 a0=0,a1=1

an=an-1+an-2 (n≧2)

===================================

f(x)=Σanx^n=a0+a1x+Σanx^n (n≧2)

=a0+a1x+xΣan-1x^n-1+x^2Σan-2x^n-2 (n≧2)

=a0+a1x+x{f(x)-a0}+x^2f(x)

=0+x+x{f(x)-0}+x^2f(x)

===================================

f(x)=(x)/(1-x-x^2)=(1/√5)/(1-αx)-(1/√5)/(1-βx)

α=(1+√5)/2、β=(1-√5)/2

an=1/√5・{α^n-β^n}

最も近い整数をとると

Fn〜[1/√5・{α^n}+1/2]

===================================

 隣り合う2項の和が次の項となる数列はフィボナッチ数列の名で有名ですが,フィボナッチ数列{Fn}の通常型母関数f(x)は

    f(x)=F0+F1x+F2x^2+F3x^3+・・・

   xf(x)=   F0x+F1x^2+F2x^3+・・・

  x^2f(x)=       F0x^2+F1x^3+・・・

また,Fn=Fn-1+Fn-2より

  f(x)=x/(1−x−x^2)=ΣFnx^n

と簡単な式になります.

===================================

 a0=2,a1=1

an=an-1+an-2 (n≧2)

===================================

f(x)=Σanx^n=a0+a1x+Σanx^n (n≧2)

=a0+a1x+xΣan-1x^n-1+x^2Σan-2x^n-2 (n≧2)

=a0+a1x+x{f(x)-a0}+x^2f(x)

=2+x+x{f(x)-2}+x^2f(x)

===================================

f(x)=(2-x)/(1-x-x^2)=(1)/(1-αx)+(1)/(1-βx)

α=(1+√5)/2、β=(1-√5)/2

an={α^n+β^n}

最も近い整数をとると

Ln〜[{α^n}+1/2]

===================================

F2n=FnLn

L2n=(Ln)^2-2(-1)^n

F2n+1=(Fn)^2+(Fn+1)^2

===================================