MathLabs
定理証明済み

フィボナッチ母関数の閉じた形

内容

F0=0, F1=1F_0=0,\ F_1=1 とし、n≥2n\ge2 に対して Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2} とする。このとき通常型母関数 F(x)=∑n=0∞FnxnF(x)=\sum_{n=0}^{\infty}F_nx^n は F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2} に等しい。

なぜ正しいのか?

係数が定数の線形漸化式は、xxn^n を掛けてすべての nn について和を取れば、常に単純な代数(実際には有理)方程式になる — 漸化式は xx の多項式を掛ける操作になる。

証明の概略

漸化式 Fn=Fn−1+Fn−2F_n=F_{n-1}+F_{n-2}(n≥2n\ge2 で成立)に xnx^n を掛けて n≥2n\ge2 について和を取る: ∑n≥2Fnxn=∑n≥2Fn−1xn+∑n≥2Fn−2xn\sum_{n\ge2}F_nx^n=\sum_{n\ge2}F_{n-1}x^n+\sum_{n\ge2}F_{n-2}x^n。

左辺は F(x)−F0−F1x=F(x)−xF(x)-F_0-F_1x=F(x)-x である。右辺の最初の和は x∑n≥2Fn−1xn−1=x∑m≥1Fmxm=x(F(x)−F0)=xF(x)x\sum_{n\ge2}F_{n-1}x^{n-1}=x\sum_{m\ge1}F_mx^m=x(F(x)-F_0)=xF(x) となる。2番目の和は x2∑n≥2Fn−2xn−2=x2∑k≥0Fkxk=x2F(x)x^2\sum_{n\ge2}F_{n-2}x^{n-2}=x^2\sum_{k\ge0}F_kx^k=x^2F(x) となる。

よって F(x)−x=xF(x)+x2F(x)F(x)-x=xF(x)+x^2F(x)、すなわち (1−x−x2)F(x)=x(1-x-x^2)F(x)=x が成り立つ。

F(x)F(x) について解くと F(x)(1−x−x2)=xF(x)(1-x-x^2)=x となり、したがって F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2} が得られる。これは無限に続くフィボナッチ数列全体を詰め込んだ、ただ1つの有理関数である。

この定理を使うトピック

母関数

ステップごとの証明

この定理のステップごとの証明はまだありません。

参考文献

  1. Herbert S. Wilf (1994). generatingfunctionology
  2. Philippe Flajolet, Robert Sedgewick (2009). Analytic Combinatorics