z変換：フィボナッチ数列の一般項を求める。

204

目的

フィボナッチ数列の一般項を $z$ 変換を使って求める。

定義

解法に進む前に準備としていくつか定義を述べる。

z

変換

$0$ 以上の整数 $n$ に対して定義された $f (n)$ について $z$ 変換を
$\begin{array}{rcl} Z [f (n)] & := & \sum_{n = 0}^{\infty} f (n) z^{- n} (z \in C) \end{array}$
と定義する。ただし $z$ は $| \sum_{n = 0}^{\infty} f (n) z^{- n} | < \infty$ を満たす。またこの条件を満たす領域を収束領域と呼ぶ。

離散デルタ関数

$δ (n) := \begin{array}{r} {\begin{cases} 1 & (n = 0) \\ 0 & (n \neq 0) \end{cases} \end{array}$ ただし $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$

単位階段関数の定義から
$\begin{array}{rcl} u (n - l) & = & \sum_{k = 0}^{\infty} δ ((n - l) - k) \\ = & \sum_{k = 0}^{\infty} δ (n - (l + k)) \end{array}$ ここで $m = l + k$ とおいて
$\begin{array}{rcl} u (n - l) & = & \sum_{m = l}^{\infty} δ (n - m) \\ = & \sum_{m = 0}^{\infty} δ (n - m) - \sum_{m = 0}^{l - 1} δ (n - m) \end{array}$ ここで $m$ を $k$ に置き換えて
$\begin{array}{rcl} 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) \end{array}$ となり示された。

解法

フィボナッチ数列

n番目のフィボナッチ数を $f (n)$ としたとき漸化式は
$f (n) := \begin{array}{r} {\begin{cases} 0 & (n = 0) \\ 1 & (n = 1) \\ f (n - 1) + f (n - 2) & (n \geq 2) \end{cases} \end{array}$ で与えられる。ただし $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)$ は
$\begin{array}{rcl} 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) \end{array}$ となる。

$z$ 変換

$f (n)$ を $z$ 変換する。 $z$ 変換の線形性、シフト則、および離散デルタ関数の $z$ 変換を適用して
$F (z) = Z [f (n)] = f (0) + f (1) z^{- 1} - f (0) z^{- 1} + z^{- 1} F (z) + z^{- 2} F (z)$ を得る。式を整理して
$\begin{array}{rcl} F (z) & = & \frac{f (0) + {f (1) - f (0)} z^{- 1}}{1 - z^{- 1} - z^{- 2}} \\ = & \frac{f (0) z^{2} + {f (1) - f (0)} z}{z^{2} - z - 1} \end{array}$
$f (n)$ の $z$ 変換が得られた。
部分分数分解する前に両辺を $z$ で割る。
$\begin{array}{rcl} \frac{F (z)}{z} & = & \frac{f (0) z + {f (1) - f (0)}}{z^{2} - z - 1} \end{array}$

部分分数分解

右辺をヘビサイドの展開定理をもちいて部分分数分解する。分母の多項式 $z^{2} - z - 1$ の2つの解を $α, β$ とおくと
$\begin{array}{rcl} \frac{F (z)}{z} & = & \frac{A}{z - α} + \frac{B}{z - β} \end{array}$ ただし
$\begin{array}{rcl} A & = & lim_{z \to α} (z - α) \frac{F (z)}{z} \\ = & lim_{z \to α} \frac{f (0) z + {f (1) - f (0)}}{z - β} \\ = & \frac{f (0) α + {f (1) - f (0)}}{α - β} \\ = & \frac{1}{α - β} \\ B & = & lim_{z \to β} (z - β) \frac{F (z)}{z} \\ = & lim_{z \to β} \frac{f (0) z + {f (1) - f (0)}}{z - α} \\ = & \frac{f (0) β + {f (1) - f (0)}}{β - α} \\ = & \frac{1}{β - α} = \frac{- 1}{α - β} \end{array}$ 両辺に $z$ を掛けて整理して
$\begin{array}{rcl} F (z) & = & \frac{A z}{z - α} + \frac{B z}{z - β} \\ = & \frac{1}{α - β} (\frac{z}{z - α} - \frac{z}{z - β}) \end{array}$
収束領域は $| z | > max (α, β)$ 。

逆 $z$ 変換

両辺を逆 $z$ 変換する。
$\begin{array}{rcl} f (n) & = & \frac{1}{α - β} (α^{n} - β^{n}) = \frac{α^{n} - β^{n}}{α - β} \end{array}$ ここで $α = \frac{1 + \sqrt{5}}{2}, β = \frac{1 - \sqrt{5}}{2}$ を代入して
$\begin{array}{rcl} f (n) & = & \frac{1}{\sqrt{5}} ({(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n}) \end{array}$
フィボナッチ数列の一般項が得られた。この公式はビネの公式と呼ばれる。

参考文献

投稿日：2020年12月9日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

zeta

3774

他の人のコメント

コメントはありません。

読み込み中

zeta

z変換：フィボナッチ数列の一般項を求める。

目的
定義
解法
漸化式に初期値を埋め込む
$z$変換
逆$z$変換
参考文献

z変換：フィボナッチ数列の一般項を求める。

目的

定義

解法

漸化式に初期値を埋め込む

z変換

部分分数分解

逆z変換

参考文献

この記事を高評価した人

この記事に送られたバッジ

投稿者

コメント

他の人のコメント

$z$ 変換

逆 $z$ 変換