## 費布納西數列的表達式

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…

$\displaystyle\phi=\frac{1+\sqrt{5}}{2}\approx 1.6180339887\ldots$

$F_k$ 代表費布納西數列的第 $k$ 項。費布納西數列的遞歸生成規則可用差分方程表示為

$F_{k+2}=F_{k+1}+F_{k},~~k=0,1,2,\ldots$

\begin{aligned} F_{k+2}&=F_{k+1}+F_k\\ F_{k+1}&=F_{k+1},\end{aligned}

$\begin{bmatrix} F_{k+2}\\ F_{k+1} \end{bmatrix}=\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}\begin{bmatrix} F_{k+1}\\ F_k \end{bmatrix}$

$\mathbf{u}_k=\begin{bmatrix} F_{k+1}\\ F_k \end{bmatrix}$，即得差分方程標準式：

$\mathbf{u}_{k+1}=A\mathbf{u}_k,~~k=0,1,\ldots$

$\mathbf{u}_k=A\mathbf{u}_{k-1}=A(A\mathbf{u}_{k-2})=A^2\mathbf{u}_{k-2}=\cdots=A^k\mathbf{u}_0$

$\mathbf{u}_k=S\Lambda^kS^{-1}\mathbf{u}_0$

\begin{aligned} \mathbf{u}_k&=S\Lambda^k\mathbf{c}\\ &=\begin{bmatrix} \mathbf{x}_1&\cdots&\mathbf{x}_n \end{bmatrix}\begin{bmatrix} \lambda_1^k&~&~\\ ~&\ddots&~\\ ~&~&\lambda_n^k \end{bmatrix}\begin{bmatrix} c_1\\ \vdots\\ c_n \end{bmatrix}\\ &=\begin{bmatrix} \lambda_1^k\mathbf{x}_1&\cdots&\lambda_n^k\mathbf{x}_n \end{bmatrix}\begin{bmatrix} c_1\\ \vdots\\ c_n \end{bmatrix}\\ &=c_1\lambda_1^k\mathbf{x}_1+\cdots+c_n\lambda_n^k\mathbf{x}_n,\end{aligned}

$k=0$，上式便為 $\mathbf{u}_0=S\Lambda^0\mathbf{c}=SI\mathbf{c}=S\mathbf{c}$，解出係數 $c_1,\ldots,c_n$ 即大功告成。

$p(\lambda)=\det(A-\lambda I)=\begin{vmatrix} 1-\lambda&1\\ 1&-\lambda \end{vmatrix}=\lambda^2-\lambda-1$

$\displaystyle\lambda_1=\frac{1+\sqrt{5}}{2},~\lambda_2=\frac{1-\sqrt{5}}{2}$

$\mathbf{x}_1=\begin{bmatrix} \lambda_1\\ 1 \end{bmatrix},~\mathbf{x}_2=\begin{bmatrix} \lambda_2\\ 1 \end{bmatrix}$

$\mathbf{u}_k=c_1\lambda_1^k\mathbf{x}_1+c_2\lambda_2^k\mathbf{x}_2$

$k=0$，代入初始條件 $\mathbf{u}_0$

$\begin{bmatrix} 1\\ 0 \end{bmatrix}=c_1\begin{bmatrix} (1+\sqrt{5})/2\\ 1 \end{bmatrix}+c_2\begin{bmatrix} (1-\sqrt{5})/2\\ 1 \end{bmatrix}$

$\displaystyle \mathbf{u}_k=\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^k\begin{bmatrix} (1+\sqrt{5})/2\\ 1 \end{bmatrix}-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^k\begin{bmatrix} (1-\sqrt{5})/2\\ 1 \end{bmatrix}$

$\displaystyle F_k=\frac{1}{\sqrt{5}}\left[\left(\frac{1+\sqrt{5}}{2}\right)^k-\left(\frac{1-\sqrt{5}}{2}\right)^k\right],~~k=0,1,2,\ldots$

(1) 當 $k$ 增大時，第二項 $\left(\frac{1-\sqrt{5}}{2}\right)^k$ 迅速趨於0，因此

$\displaystyle F_k\approx \frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^k$

$\displaystyle \frac{F_{k+1}}{F_k}\approx\frac{1+\sqrt{5}}{2}$

(2) 冪矩陣 $A^k$ 可用費布納西數表示為

$A^k=\begin{bmatrix} F_{k+1}&F_k\\ F_k&F_{k-1} \end{bmatrix}$

$A^k\begin{bmatrix} 0\\ 1 \end{bmatrix}=A^{k-1}\begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}\begin{bmatrix} 0\\ 1 \end{bmatrix}=A^{k-1}\begin{bmatrix} 1\\ 0 \end{bmatrix}=\mathbf{u}_{k-1}$

(3) 由 (2)，$\det A^k=(\det A)^k=\begin{vmatrix} 1&1\\ 1&0 \end{vmatrix}^k=(-1)^k$，就得到 Cassini 恆等式：

$(-1)^k=F_{k+1}F_{k-1}-F_k^2$

This entry was posted in 特徵分析, 線性代數專欄 and tagged , , , , , . Bookmark the permalink.

### 5 則回應給 費布納西數列的表達式

1. Watt Lin 說：

老師：您的數列，是不是需要再添加一個1？
0,1,2,3,5,8 ….
修改為以下
0,1,1,2,3,5,8 ….

• ccjou 說：

哈，您的眼力真好！我打印出來讀了兩遍，竟然沒發現這個錯誤。

馬上訂正。

2. Watt Lin 說：

老師修改的速度真快！

3. shawn toh 說：

好深好深好深好深的数学。。。。。。

4. 費伯那西與向日癸 說：

Good