フィボナッチ数列の汚い部分
フィボナッチ数列は美しい、と聞いたことがある人も多いだろう。1, 1, 2, 3, 5, 8, 13, 21, ...といった具合に、前2つの項の和が次の項になるような数列である。カメラの構図や植物における花や実の数、ときに金融の世界でも現れるこの数列だが(金融の場合は、多くの人がこれを参照するからその特徴が現れるという、ある種「信じるものは救われる」的な部分もあるのも確か)、前後の項の比の極限が黄金比になることも有名な事実だ。しかし、ひとつ学生時代から解せないのがフィボナッチ数列の一般項の汚さだ。これだけ自然界を彩る数列のくせに、自身の一般項という最もベーシックなところがとても汚い。いきなりここでその一般項を紹介するのもいいのだが、折角だからその汚い世界への道程から誘いたい。まず漸化式から考える。前2項の和が次の項になるわけだから、a(n+2)=a(n+1)+anと書ける(ここで、エディタの事情からn番目の値をan, n+1番目をa(n+1)などと書くことにする)。漸化式までは係数もなく綺麗だ。この漸化式はいわゆる3項間漸化式と呼ばれるもので、一般項を求めるときは特性方程式を用いるのが常套手段である。しかし、特性方程式ってなんだよ、という人もいるだろうからこの辺から少し説明したい。自分から話しておいて何だが、そもそも特性方程式なんて言葉はどうでもよくて、我々は漸化式と一般項の表現の往来について、語弊を恐れずに言えば等差数列と等比数列しか知らない。ゆえに、このどちらかの表現に落とし込む必要がある。等差数列(dは公差)ではa(n+1)=an+d↔an=a1+(n-1)d等比数列(rは公比)ではa(n+1)=ran↔an=a1r^(n-1)という関係が漸化式と一般項の間にある。a(n+2)=a(n+1)+anの式においてそれぞれ考えると、a(n+2)-Aa(n+1)=a(n+1)-Aan+dが成立するようなA、dは存在しないので等比数列には持ち込めない。等比数列に持ち込むことを考えると、a(n+2)-Aa(n+1)=r(A(n+1)-Aan)と表せるA、rが存在すればよい。式変形をするとa(n+2)-(A+r)a(n+1)+ARan=0となるので、これとa(n+2)=a(n+1)+anを同じ形にしたa(n+2)-a(n+1)-an=0の係数を比べる。A+r=1Ar=-1となるわけだが、和と積の形で表されていることから解と係数の関係を用いて、A、rはx^2-x-1=0の解となる。これは因数分解できないので解の公式を用いて、・・・として解いていくのである。因数分解できなくて、解の公式を使う時点で今後の計算がどれだけ汚くなるか予想ができることだろう。これを計算して最終的には、an=1/sqrt(5)[{(1+sqrt(5))/2}^n-{(1-sqrt(5))/2}^n]という一般項を得る。ここでsqrt(*)は*の平方根を表す。一行で書いていることも相まって、あまりにも汚い式である。んー。この一般項が綺麗な式だと逆につまらないのだろうか。