フィボナッチ多項式の因数分解
はじめに
この記事では, フィボナッチ多項式の因数分解を導出してみる.
フィボナッチ多項式とは
フィボナッチ多項式とは, イタリアの数学者レオナルド・フィボナッチによって名付けられた数列である｢フィボナッチ数｣の一般化のひとつである.
フィボナッチ数とは, どの項も前2つの項の値を足した値となっている数列であり,
$$
1,\,
1,\,
2,\,
3,\,
5,\,
8,\,
13,\,
21,\,
34,\,
55,\,
89,\,
144,\,\cdots
$$
と続くものである.
定義と諸性質
フィボナッチ多項式とは次の漸化式と初期条件を満たす多項式列$(F_n(X))$のことである:
$$
F_0(X)=0,
\quad
F_1(X)=1,
\quad
F_{n+2}(X)=XF_{n+1}(X)+F_n(X)
$$
はじめのいくつかの項は以下のようになる:
$$
\begin{align*}
F_{0}(x)&=0,\\
F_{1}(x)&=1,\\
F_{2}(x)&=x,\\
F_{3}(x)&=x^{2}+1,\\
F_{4}(x)&=x^{3}+2x,\\
F_{5}(x)&=x^{4}+3x^{2}+1,\\
F_{6}(x)&=x^{5}+4x^{3}+3x,\\
\cdots
\end{align*}
$$
また, 次のような簡潔な表示が存在する.
$$
\varphi(X)+\psi(X)=X,\quad
\varphi(X)\psi(X)=-1
$$
を満たす形式的ベキ級数$\varphi(X)$, $\psi(X)$が存在し, 整数$n$に対して以下の等式が成り立つ:
$$
F_n(X)=\frac{\varphi(X)^n-\psi(X)^n}{\varphi(X)-\psi(X)}.
$$
なお, この表示は一般に隣接二項の線形漸化式に関する議論により導出できるため, 証明は割愛する. 1
主定理
自然数$n$に対して以下の等式が成り立つ.
$$
F_n(X)=\prod_{k=1}^{n-1}\left(X-2i\cos\left(\frac{k}{n}\pi\right)\right)
$$
この定理の証明のために, いくつかの補題を示す.
自然数$m$に対して, $F_m(X)$の次数は$m-1$であり, 最高次係数は1である.
自然数$m$に関する命題
- $P(m)$ : $F_m(X)$の次数は$m-1$であり, 最高次係数は1である.
に対して数学的帰納法(正確には2ステップの累積機能法)を適用して証明を進める.
まず, $F_1(X)=1$は0次多項式であり, 最高次係数は1となるため, 命題$P(1)$を満たす.
また, $F_2(X)=X$は1次多項式であり, 最高次係数は1となるため, 命題$P(2)$を満たす.
次に, 自然数$k$として$P(k)$と$P(k+1)$がともに成り立つものをとったとき, 漸化式
$$
F_{k+2}(X)=XF_{k+1}(X)+F_k(X)
$$
より, $F_{k+2}(X)$は$k+3$次多項式となり, $F_{k+2}$の最高次係数は$F_{k+1}$の最高次係数と等しくなるため1となる.
これらより, $P(k+2)$は真となる.
したがって, 数学的帰納法より任意の自然数$m$に対して$P(m)$は真となる.
$n$を自然数とする.
体$\mathbb{C}$におけるフィボナッチ多項式$F_n(X)$の根全体を$R_n$とすると次が成り立つ.
$$
R_n=\left\{2i\cos\left(\frac{k}{n}\pi\right)
\mathrel{}\middle|\mathrel{}
k=1,2,\ldots,n-1
\right\}
$$
2以上の自然数$n$を任意に取り固定する.
複素数$z$を$F_n(z)=0$を満たすとしてとると, フィボナッチ多項式の閉形式表示より
$$
\varphi(z)^n-\psi(z)^n=0
\,\land\,
\varphi(z)-\psi(z)\neq0
$$
となる.
ここで, $\varphi(z)^n-\psi(z)^n=0$と$\varphi(z)\psi(z)=-1$より$\varphi(z)^{2n}=(-1)^n$が成り立つため, ある整数$m=0,1,2,\ldots,2n-1$が存在し
$$
\varphi(z)=i\exp\left(\frac{m}{n}\pi i\right)
$$
が成り立つ.
他方, $\varphi(z)-\psi(z)\neq0$と$\varphi(z)\psi(z)=-1$より$\varphi(z)^2\neq-1$なため,
$$
\varphi(z)\neq i
\,\land\,
\varphi(z)\neq -i
$$
よって, $m\neq n$かつ$m\neq 0$となる.
また, $\varphi(z)+\psi(z)=z$と$\varphi(z)\psi(z)=-1$より
$$
\begin{align*}
z
&=\varphi(z)+\psi(z)\\
&=\varphi(z)-\varphi(z)^{-1}\\
&=i\left(\exp\left(\frac{m}{n}\pi i\right)+\exp\left(-\frac{m}{n}\pi i\right)\right)\\
&=2i\cos\left(\frac{m}{n}\pi\right)
\end{align*}
$$
となる.
したがって, 以下の同値が成り立つ.
$$
F_n(z)=0
\iff
\exists m\in\{1,\ldots,n-1,n+1,\ldots,2n-1\}\,;\,
z=2i\cos\left(\frac{m}{n}\pi\right)
$$
また, 余弦関数$w=\cos{z}$の軸$z=\pi$における対称性から, $m$の存在範囲を$\{1,\ldots,n-1\}$とすれば$m$は一意的となる.
すなわち,
$$
F_n(z)=0
\iff
\exists! m\in\{1,\ldots,n-1\}\,;\,
z=2i\cos\left(\frac{m}{n}\pi\right)
$$
となる.
自然数$n$を任意に取り固定する.
補題2
より, 定数$C$が存在し以下の等式が成り立つ.
$$
F_n(X)=C\prod_{k=1}^{n-1}\left(X-2i\cos\left(\frac{k}{n}\pi\right)\right)
$$
ここで, $F_n(X)$の最高次係数が1であるため, $C=1$となる.
自然数$n$に対して以下の等式が成り立つ.
$$
F_{2n}(X)=X\prod_{k=1}^{n-1}\left(X^2+4\cos^2\left(\frac{k}{2n}\pi\right)\right)
,\quad
F_{2n-1}(X)=\prod_{k=1}^{n-1}\left(X^2+4\cos^2\left(\frac{k}{2n-1}\pi\right)\right)
$$