フィボナッチ多項式

フィボナッチ多項式は、次の漸化式より得られる^[1]：

${\displaystyle F_{n}(x)={\begin{cases}0,&{\mbox{if }}n=0\\1,&{\mbox{if }}n=1\\xF_{n-1}(x)+F_{n-2}(x),&{\mbox{if }}n\geq 2\end{cases}}}$

初めのいくつかのフィボナッチ多項式を書くと、次のようになる：

${\displaystyle F_{0}(x)=0\,}$

${\displaystyle F_{1}(x)=1\,}$

${\displaystyle F_{2}(x)=x\,}$

${\displaystyle F_{3}(x)=x^{2}+1\,}$

${\displaystyle F_{4}(x)=x^{3}+2x\,}$

${\displaystyle F_{5}(x)=x^{4}+3x^{2}+1\,}$

${\displaystyle F_{6}(x)=x^{5}+4x^{3}+3x\,}$

リュカ多項式は、初めの値が異なるだけで、同様の漸化式より得られる^[2]： ${\displaystyle L_{n}(x)={\begin{cases}2,&{\mbox{if }}n=0\\x,&{\mbox{if }}n=1\\xL_{n-1}(x)+L_{n-2}(x),&{\mbox{if }}n\geq 2.\end{cases}}}$

初めのいくつかのリュカ多項式は次のようになる：

${\displaystyle L_{0}(x)=2\,}$

${\displaystyle L_{1}(x)=x\,}$

${\displaystyle L_{2}(x)=x^{2}+2\,}$

${\displaystyle L_{3}(x)=x^{3}+3x\,}$

${\displaystyle L_{4}(x)=x^{4}+4x^{2}+2\,}$

${\displaystyle L_{5}(x)=x^{5}+5x^{3}+5x\,}$

${\displaystyle L_{6}(x)=x^{6}+6x^{4}+9x^{2}+2.\,}$

フィボナッチ数およびリュカ数は、それぞれの多項式において x = 1 とすることで得られる。ペル数は F_n に対し x = 2 とすることで得られる。F_n の次数は n − 1 で、L_n の次数は n である。これらの多項式列の通常母関数は次のようになる^[3]：

${\displaystyle \sum _{n=0}^{\infty }F_{n}(x)t^{n}={\frac {t}{1-xt-t^{2}}}}$

${\displaystyle \sum _{n=0}^{\infty }L_{n}(x)t^{n}={\frac {2-xt}{1-xt-t^{2}}}.}$

これらの多項式列は、リュカ数列を使うことで次のように表現することが出来る：

${\displaystyle F_{n}(x)=U_{n}(x,-1),\,}$

${\displaystyle L_{n}(x)=V_{n}(x,-1).\,}$

Summarize Timeline Top Qs Fact Check

リュカ数列の特別な場合として、フィボナッチ多項式は以下に述べる多くの関係式を満たす。

初めに、負の添え字に対しては次の関係式が成り立つ^[4]：

${\displaystyle F_{-n}(x)=(-1)^{n-1}F_{n}(x),\,L_{-n}(x)=(-1)^{n}L_{n}(x).}$

また、次の関係式が成り立つ^[4]：

${\displaystyle F_{m+n}(x)=F_{m+1}(x)F_{n}(x)+F_{m}(x)F_{n-1}(x)\,}$

${\displaystyle L_{m+n}(x)=L_{m}(x)L_{n}(x)-(-1)^{n}L_{m-n}(x)\,}$

${\displaystyle F_{n+1}(x)F_{n-1}(x)-F_{n}(x)^{2}=(-1)^{n}\,}$

${\displaystyle F_{2n}(x)=F_{n}(x)L_{n}(x).\,}$

ビネットの公式と同様に、閉形式表現は次のようになる^[4]：

${\displaystyle F_{n}(x)={\frac {\alpha (x)^{n}-\beta (x)^{n}}{\alpha (x)-\beta (x)}},\,L_{n}(x)=\alpha (x)^{n}+\beta (x)^{n}.}$

ただし

${\displaystyle \alpha (x)={\frac {x+{\sqrt {x^{2}+4}}}{2}},\,\beta (x)={\frac {x-{\sqrt {x^{2}+4}}}{2}}}$

は次の（t に関する）方程式の解である：

${\displaystyle t^{2}-xt-1=0.\,}$

F_n(x) における x^k の係数を F(n,k) と表す。すなわち

${\displaystyle F_{n}(x)=\sum _{k=0}^{n}F(n,k)x^{k},\,}$

とする。このとき F(n,k) は、 2 × 1 のドミノとちょうど k 個の 1 × 1 の正方形を使って、n−1 × 1 の長方形を埋める方法の数に等しい^[1]。また同値であるが、F(n,k) は、1 をちょうど k 回使って、1 と 2 のみからなる順序付の和で n−1 を書く方法の数に等しい。例えば F(6,3)=4 であるが、これ 1 をちょうど 3 回使って、1 と 2 のみからなる順序付の和で 6-1 = 5 を書く方法 1+1+1+2, 1+1+2+1, 1+2+1+1, 2+1+1+1 の数 4 に等しい。そのような和で用いられる 1 と 2 の数を数えることで、F(n,k) は二項係数

${\displaystyle F(n,k)={\binom {\tfrac {n+k-1}{2}}{k}}}$

に等しい。ここで n と k は異なるパリティ（奇偶性）を持つ。このことから、右図のようにパスカルの三角形からフィボナッチ多項式の係数を求めることが出来る。