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

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

$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)=\infty$であることに注意してほしい。探している数${\rho }_k$は、$R(z)$を$S(z)+T(z)$の形に表現する事が出来れば、
$Q({\alpha }_k)$を満たす数${\alpha }_k$の逆数になる。ここで、$P$と$Q$が多項式で、$R(z)=\frac{P(z)}{Q(z)}$だったことを思い出そう。このとき、$R(z)=\infty$となるのは$Q(z)=0$の場合のみである。

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

$Q(z)=q_0+q_{1}z+\cdots \cdots \cdots +q_m{z}^m$　　　($q_0\ne 0,q_m\ne 0$)

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

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

その関係は

$Q^R(Z)=q_0(z-{\rho }_1)...(z-{\rho }_m)⟺Q(z)=q_0(1-{\rho }_{1}z)...(1-{\rho }_{m}z)$

すなわち、$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\pm \sqrt{b^2-4ac}}{2a}$)に、$(a,b,c)=(1,-1,-1)$を当てはめればよい。そして見知った形である、

$\varphi =\frac{1+\sqrt{5}}{2}$　　　　　 $\hat{\varphi }=\frac{1-\sqrt{5}}{2}$

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

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