■いろいろの漸化式と母関数(その1)

[1]漸化式から母関数へ

 たとえば,漸化式:an=2an-1+an-2 (n≧2),a0=1,a1=3を考える.

 その母関数を

  f(x)=Σanx^n (n≧0)

とおくと,

  anx^n=2xan-1x^n-1+x^2an-2x^n-2 (n≧2)

  Σanx^n=2xΣan-1x^n-1+x^2Σan-2x^n-2

  f(x)−1−3x=2x{f(x)−1}+x^2f(x)

  f(x)=1+x+2xf(x)+x^2f(x)

f(x)=(1+x)/(1−2x−x^2)

f(x)=1/2/(1−αx)+1/2/(1−βx)

  α=1+√2,β=1−√2

  an=(α^n+1+β^n+1)/2

  n→∞のとき,(an)^1/n→1+√2

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

[2]母関数から漸化式へ

 ポリオミノ数の母関数

f(x)=x(1−x)^3/(1−5x+7x^2−4x^3)

からは,漸化式:

  an=5an-1−7an-2+4an-3

が得られる.

 {an}の一般項を示すのは難しそうであるが,

  x^3−5x^2+7x−4=0

の根で,絶対値が最大のものをθとおくと

  n→∞のとき,(an)^1/n→θ〜3.2

となる.

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