フィボナッチ数列に関する漸化式概論 破

フィボナッチ数列に関する漸化式概論 序 の最後に、すべての有理関数$R(z)(R(0) \neq0)$が一定の性質を満たす事実のみを述べた。なので、漸化式概論 破ではその説明から始めようと思う。

$R(z)=S(z)+T(z)$　($S(z)$,$T(z)$については序を参照)と表せるということは、すなわち、係数$[z^n]R(z)$に閉じた式が存在するということである。つまり、ここで$S(z)$と$T(z)$を見つけることは、$R(z)$の部分分数展開を見つけることと等価である。
もし$z$の値が$ \frac{1}{\rho_1},..., \frac{1}{\rho_l}$であるならば、$S(z)=∞$であることに注意してほしい。探している数$\rho_k$は、$R(z)$を$S(z)+T(z)$の形に表現する事が出来れば、
$Q(\alpha_k)$を満たす数$\alpha_k$の逆数になる。ここで、$P$と$Q$が多項式で、$R(z)= \frac{P(z)}{Q(z)}$だったことを思い出そう。このとき、$R(z)=∞$となるのは$Q(z)=0$の場合のみである。

ここで、$Q(z)$が次の形をしていると仮定する。

$Q(z)=q_0+q_1z+ \cdots \cdots \cdots+q_mz^m$　　　($q_0 \neq0,q_m \neq 0$)

このとき、次の反転多項式は$Q(z)$と関係があり、

$$ Q^R(z)=q_0z^m+q_1z^{m-1}+ \cdot \cdot \cdot +q_m $$

その関係は

$Q^R(Z)=q_0(z-\rho_1)...(z-\rho_m) \Longleftrightarrow Q(z)=q_0(1-\rho_1z)...(1-\rho_mz)$

すなわち、$Q^R$の根は$Q$の根の逆数であり、その逆も成り立つ。したがって数$\rho_k$を求めるには、反転多項式$Q^R(z)$を因数分解すれば良い道理である。

$Q(z)=1-z-z^2\,\,\,\,\,\,\,\,\,\,\,\,\,Q^R(z)=z^2-z-1$　がフィボナッチ数列では成立している。

そこで$Q^R$の根を見つけるには、二次方程式の根の公式($ \frac{-b±\ \sqrt{b^2-4ac}}{2a}$)に、$(a,b,c)=(1,-1,-1)$を当てはめればよい。そして見知った形である、

$\phi=\frac{1+\sqrt{5}}{2}$　　　　　 $ \widehat{\phi}=\frac{1- \sqrt{5}}{2}$

したがって、$Q^R(z)=(z-\phi)(z- \widehat{\phi})$および$Q(z)=(1-{\phi}z)(1-\widehat{\phi}z)$である。

いったん$\rho$の値が見つかれば、部分分数展開を行えるようになる。すべての根が異なっていれば手っ取り早いので、フィボナッチ数列に関する漸化式概論 急ではそのパターンを考えていくことにする。