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

フィボナッチ数列に関する漸化式概論破では $Q^{R}$ の根の見つけ方とその特徴、そして部分分数展開に言及した。ので最終章の急では、根の一致の是非で場合分け、展開定理を整理する。

根が異なる場合の有理関数の展開定理

$[z^{n}] R (z) = a_{1} ρ_{1}^{n} + \dots + a_{l} ρ_{l}^{n} (a_{k} = \frac{- ρ_{k} P (1 / ρ_{k})}{Q^{'} (1 / ρ_{k})})$

ただし、 $R (z) = \frac{P (z)}{Q (z)}$ であり、 $Q (z) = q_{0} (1 - ρ_{1} z) . . . (1 - ρ_{l} z)$ 、数 $(ρ_{1}, . . ., ρ_{l})$ はすべて異なり、 $P (z)$ は次数が $l$ 未満の多項式である。

数 $a_{1}, . . ., a_{l}$ を先に述べた定数とする。この式は $R (z) = \frac{P (z)}{Q (z)}$ が次式に等しいとき成立。

$S (z) = \frac{a_{1}}{1 - ρ_{1} z} + \dots + \frac{a_{l}}{1 - ρ_{l} z}$

関数 $T (z) = R (z) - S (z)$ が $z \to \frac{1}{ρ_{k}}$ のとき有限であることを示すことで $R (z) = S (z)$ を証明することが出来る。それは有理関数 $T (z)$ は決して無限大に発散しないからである。
したがってT(z)は多項式でなければならない。さらに $z \to \infty$ の時 $T (z) \to 0$ であることも示せる。したがって $T (z)$ はゼロでなければいけない。

ここで $α_{k} = \frac{1}{ρ_{k}}$ とおく。式 $lim_{z \to α_{k}} T (z) \neq \infty$ を証明するためには、 $T (z)$ が $z$ の有理関数であることから、 $lim_{z \to α_{k}} (z - α_{k}) T (z) = 0$ を示せばよいということになる。つまり、

$lim_{z \to α_{k}} (z - α_{k}) R (z) = lim_{z \to α_{k}} (z - α_{k}) S (z)$ 　　を示したい。

この式の右辺は $lim_{z \to α_{k}} \frac{a_{k} (z - a_{k})}{1 - ρ_{k} z} = \frac{- a_{k}}{ρ_{k}}$ に等しい。

なぜなら、 $(1 - ρ_{k} z) = - ρ_{k} (z - α_{k})$ かつ $j \neq k$ であれば、 $\frac{z - α_{k}}{1 - ρ_{j} z} \to 0$ だからである。

左辺については $L^{'} H o s p i t a l の定理$ より、極限値を

$lim_{z \to α_{k}} (z - α_{k}) \frac{P (z)}{Q (z)} = P (α_{k}) lim_{z \to α_{k}} \frac{z - α_{k}}{Q (z)} = \frac{P (α_{k})}{Q^{'} (α_{k})}$ とできる。　　　　　 $Q . E . D$

フィボナッチ数について言うと、 $P (z) = z$ かつ $Q (z) = 1 - z - z^{2} = (1 - ϕ z) (1 - \hat{ϕ})$ であったので、 $Q^{'} (z) = - 1 - 2 z$ であり、さらに計算を突き詰めると、

$\frac{- ρ P (1 / ρ)}{Q^{'} (1 / ρ)} = \frac{- 1}{- 1 - 2 / ρ} = \frac{ρ}{ρ + 2}$ という結果が得られる。

最後に、 $Q (z)$ が重根をもつ場合、計算が少し複雑になるので、定理1を拡張して、より一般的な定理の提示とその証明を行う。

有理母関数の一般展開定理

$[z^{n}] R (z) = f_{1} (n) ρ_{1}^{n} + \cdot \cdot \cdot + f_{l} (n) ρ_{l}^{n}$ $(n \geq 0)$

ただし、 $R (z) = \frac{P (z)}{Q (z)}$ であり、 $Q (z) = q_{0} (1 - ρ_{1} z)^{d_{1}} . . . (1 - ρ_{l} z)^{d_{l}}$ 、数 $(ρ_{1}, . . ., ρ_{l})$ はすべて異なり、 $P (z)$ は次数が $d_{1} + \cdot \cdot \cdot + d_{l}$ 未満の多項式である。

ただし $f_{k} (n)$ は次数 $d_{k} - 1$ の多項式で、先頭の係数については

$a_{k} = \frac{(- ρ_{k})^{d_{k}} P (1 / ρ_{k}) d_{k}}{Q^{(} d_{k}) (1 / ρ_{k})} = \frac{P (1 / ρ_{k})}{(d_{k} - 1)! q_{0} \prod_{j \neq k}^{} (1 - ρ_{j} / ρ_{k})^{d_{j}}}$

これの証明は $R (z) - \frac{a_{1} (d_{1} - 1)!}{(1 - ρ_{1} z)^{d_{1}}} - \cdot \cdot \cdot - \frac{a_{l} (d_{l} - 1)!}{(1 - ρ_{l} z)^{d_{l}}}$ の分母の多項式が、任意の $k$ について $(1 - ρ_{k} z)^{d_{k}}$ で割り切れない有理関数である事実から、 $m a x (d_{1}, . . ., d_{l})$ に関する帰納法で
容易に証明できる。