z変換：フィボナッチ数列の一般項を求める。
目的
フィボナッチ数列の一般項を$z$変換を使って求める。
定義
解法に進む前に準備としていくつか定義を述べる。
$0$以上の整数$n$に対して定義された$f(n)$について$z$変換を
$$
\BEQ
\ZT{f(n)} &:=& \sum ^{\infty }_{n=0}f( n) z^{-n} \;\;( z \in \mathbb{C} )
\EEQ
$$
と定義する。ただし$z$は$|\sum ^{\infty }_{n=0}f( n) z^{-n}| \lt \infty $を満たす。またこの条件を満たす領域を収束領域と呼ぶ。
$$ δ(n):= \begin{eqnarray} \left\{ \begin{array}{l} 1 & (n = 0 ) \\ 0 & (n \neq 0 ) \\ \end{array} \right. \end{eqnarray} $$ただし$n$は$0$以上の整数
$$ u(n):=\sum_{k=0}^{\infty} δ(n-k) $$ただし$n$は$0$以上の整数
この定義から単位階段関数は以下の性質をもつことがわかる。
$$ u(n-l)=u(n)-\sum_{k=0}^{l-1} δ(n-k) $$ただし$n,l$は$0$以上の整数で$n \neq l$
単位階段関数の定義から
$$
\BEQ
u(n-l)&=&\sum_{k=0}^{\infty} δ((n-l)-k)\\
&=&\sum_{k=0}^{\infty} δ(n-(l+k))\\
\EEQ
$$ここで$m=l+k$とおいて
$$
\BEQ
u(n-l)&=&\sum_{m=l}^{\infty} δ(n-m)\\
&=&\sum_{m=0}^{\infty} δ(n-m)- \sum_{m=0}^{l-1} δ(n-m)\\
\EEQ
$$ここで$m$を$k$に置き換えて
$$
\BEQ
u(n-l)&=&\sum_{k=0}^{\infty} δ(n-k)- \sum_{k=0}^{l-1} δ(n-k)\\
&=&u(n)-\sum_{m=0}^{l-1} δ(n-k)\\
\EEQ
$$となり示された。
解法
n番目のフィボナッチ数を$f(n)$としたとき漸化式は
$$
f(n):=
\begin{eqnarray}
\left\{
\begin{array}{l}
0 & (n = 0 ) \\
1 & (n = 1 ) \\
f(n-1)+f(n-2) & (n \ge 2 )
\end{array}
\right.
\end{eqnarray}
$$で与えられる。ただし$n$は$0$以上の整数
漸化式に初期値を埋め込む
与えられた$f(n)$は離散デルタ関数と単位階段関数を使って
$$
f(n)=f(0)δ(n)+f(1)δ(n-1)+\{f(n-1)+f(n-2)\}u(n-2)
$$とあらわせる。離散デルタ関数と単位階段関数を使って漸化式に初期値が埋め込まれている。
ここで$u(n-2)$は単位階段関数の性質から
$$
u(n-2)=u(n-1-1)=u(n-1)-\sum_{k=0}^{0}δ(n-1-k)=u(n-1)-δ(n-1)
$$なので、$f(n)$は
$$
\BEQ
f(n)&=&f(0)δ(n)+f(1)δ(n-1)+f(n-1)u(n-2)+f(n-2)u(n-2)\\
&=&f(0)δ(n)+f(1)δ(n-1)+f(n-1)\{u(n-1)-δ(n-1)\}+f(n-2)u(n-2)\\
&=&f(0)δ(n)+f(1)δ(n-1)+f(n-1)u(n-1)-f(n-1)δ(n-1)+f(n-2)u(n-2)\\
&=&f(0)δ(n)+f(1)δ(n-1)-f(n-1)δ(n-1)+f(n-1)u(n-1)+f(n-2)u(n-2)\\
\EEQ
$$となる。
$z$変換
$f(n)$を$z$変換する。$z$変換の線形性、シフト則、および離散デルタ関数の$z$変換を適用して
$$
F(z)=\ZT{f(n)}=f(0)+f(1)z^{-1}-f(0)z^{-1} +z^{-1}F(z)+z^{-2}F(z)
$$を得る。式を整理して
$$
\BEQ
F(z)
&=&\cfrac{f(0)+\{f(1)-f(0)\}z^{-1}}{1-z^{-1}-z^{-2}}\\
&=&\cfrac{f(0)z^2+\{f(1)-f(0)\}z}{z^2-z-1}\\
\EEQ
$$
$f(n)$の$z$変換が得られた。
部分分数分解する前に両辺を$z$で割る。
$$
\BEQ
\cfrac{F(z)}{z} &=& \cfrac{f(0)z+\{f(1)-f(0)\}}{z^2-z-1}\\
\EEQ
$$
部分分数分解
右辺をヘビサイドの展開定理をもちいて部分分数分解する。分母の多項式$z^2-z-1$の2つの解を$α,β$とおくと
$$
\BEQ
\cfrac{F(z)}{z} & = & \frac{A}{z-α}+\frac{B}{z-β}
\EEQ
$$ただし
$$
\BEQ
A&=&\lim_{z \to α} (z-α)\cfrac{F(z)}{z}\\
&=&\lim_{z \to α}\cfrac{f(0)z+\{f(1)-f(0)\}}{z-β}\\
&=&\cfrac{f(0)α+\{f(1)-f(0)\}}{α-β}\\
&=&\cfrac{1}{α-β}\\
B&=&\lim_{z \to β} (z-β)\cfrac{F(z)}{z}\\
&=&\lim_{z \to β}\cfrac{f(0)z+\{f(1)-f(0)\}}{z-α}\\
&=&\cfrac{f(0)β+\{f(1)-f(0)\}}{β-α}\\
&=&\cfrac{1}{β-α}=\cfrac{-1}{α-β}\\
\EEQ
$$両辺に$z$を掛けて整理して
$$
\BEQ
F(z) & = & \frac{A z}{z-α}+\frac{B z}{z-β}\\
&=&\cfrac{1}{α-β} \left(\frac{ z}{z-α}-\frac{ z}{z-β}\right)\\
\EEQ
$$
収束領域は$|z|>\max(α,β)$。
逆$z$変換
両辺を逆$z$変換する。
$$
\BEQ
f(n)&=&\cfrac{1}{α-β}(α^n-β^n)=\cfrac{α^n-β^n}{α-β}
\EEQ
$$ここで$α=\cfrac{1+\sqrt{5}}{2},β=\cfrac{1-\sqrt{5}}{2}$を代入して
$$
\BEQ
f(n)&=&\cfrac{1}{\sqrt{5}} \left(\left(\cfrac{1+\sqrt{5}}{2}\right)^n-\left(\cfrac{1-\sqrt{5}}{2}\right)^n \right)
\EEQ
$$
フィボナッチ数列の一般項が得られた。この公式はビネの公式と呼ばれる。
