フィボナッチ数列に関する漸化式概論 急
フィボナッチ数列に関する漸化式概論 破 では$Q^R$の根の見つけ方とその特徴、そして部分分数展開に言及した。ので最終章の急では、根の一致の是非で場合分け、展開定理を整理する。
$[z^n]R(z)=a_1\rho_1^n+ \cdots +a_l\rho_l^n\,\,\,\,\,(a_k= \frac{-\rho_kP(1/\rho_k)}{Q'(1/\rho_k)})$
ただし、$R(z)= \frac{P(z)}{Q(z)}$であり、$Q(z)=q_0(1-\rho_1z)...(1-\rho_lz)$、数$(\rho_1,...,\rho_l)$はすべて異なり、$P(z)$は次数が$l$未満の多項式である。
数$a_1,...,a_l$を先に述べた定数とする。この式は$R(z)= \frac{P(z)}{Q(z)}$が次式に等しいとき成立。
$S(z)= \frac{a_1}{1-\rho_1z}+\cdots+\frac{a_l}{1-\rho_lz}$
関数$T(z)=R(z)-S(z)$が$z→\frac{1}{\rho_k}$のとき有限であることを示すことで$R(z)=S(z)$を証明することが出来る。それは有理関数$T(z)$は決して無限大に発散しないからである。
したがってT(z)は多項式でなければならない。さらに$z→∞$の時$T(z)→0$であることも示せる。したがって$T(z)$はゼロでなければいけない。
ここで$\alpha_k=\frac{1}{\rho_k}$とおく。式$\displaystyle\lim_{z \to\alpha_k}T(z) \neq∞$を証明するためには、$T(z)$が$z$の有理関数であることから、$\displaystyle\lim_{z \to\alpha_k}(z-\alpha_k)T(z) =0$を示せばよいということになる。つまり、
$\displaystyle\lim_{z \to\alpha_k}(z-\alpha_k)R(z) =\displaystyle\lim_{z \to\alpha_k}(z-\alpha_k)S(z)$ を示したい。
この式の右辺は$\displaystyle\lim_{z \to\alpha_k}\frac{a_k(z-a_k)}{1-\rho_kz}=\frac{-a_k}{\rho_k}$に等しい。
なぜなら、$(1-\rho_kz)=-\rho_k(z-\alpha_k)$かつ$j\neq k$であれば、$\frac{z-\alpha_k}{1-\rho_jz}→0$だからである。
左辺については$L'Hospitalの定理$より、極限値を
$\displaystyle\lim_{z \to\alpha_k}(z-\alpha_k)\frac{P(z)}{Q(z)} =P(\alpha_k)\displaystyle\lim_{z \to\alpha_k}\frac{z-\alpha_k}{Q(z)}=\frac{P(\alpha_k)}{Q'(\alpha_k)}$とできる。 $Q.E.D$
フィボナッチ数について言うと、$P(z)=z$かつ$Q(z)=1-z-z^2=(1-\phi z)(1- \widehat{\phi})$であったので、$Q'(z)=-1-2z$であり、さらに計算を突き詰めると、
$\frac{-\rho P(1/\rho)}{Q'(1/\rho)}=\frac{-1}{-1-2/\rho}=\frac{\rho}{\rho+2}$という結果が得られる。
最後に、$Q(z)$が重根をもつ場合、計算が少し複雑になるので、定理1を拡張して、より一般的な定理の提示とその証明を行う。
$[z^n]R(z)=f_1(n)\rho_1^n+\cdot\cdot\cdot+f_l(n)\rho_l^n$ $(n \geq0)$
ただし、$R(z)= \frac{P(z)}{Q(z)}$であり、$Q(z)=q_0(1-\rho_1z)^{d_1}...(1-\rho_lz)^{d_l}$、数$(\rho_1,...,\rho_l)$はすべて異なり、$P(z)$は次数が$d_1+\cdot\cdot\cdot+d_l$未満の多項式である。
ただし$f_k(n)$は次数$d_k-1$の多項式で、先頭の係数については
$a_k=\frac{(-\rho_k)^{d_k}P(1/\rho_k)d_k}{Q^(d_k)(1/\rho_k)}=\frac{P(1/\rho_k)}{(d_k-1)!q_0 \prod_{j\neq k}^{}(1-\rho_j/\rho_k)^{d_j}}$
これの証明は$R(z)-\frac{a_1(d_1-1)!}{(1-\rho_1z)^{d_1}}-\cdot\cdot\cdot-\frac{a_l(d_l-1)!}{(1-\rho_lz)^{d_l}}$の分母の多項式が、任意の$k$について$(1-\rho_kz)^{d_k}$で割り切れない有理関数である事実から、$max(d_1,...,d_l)$に関する帰納法で
容易に証明できる。
以上で一般展開定理への拡張とする。
一通り漸化式（フィボナッチ数列に関して）について言及したが、見返しのリンクを以下に貼っておくので参考にしてほしい。