36205 Fibonacci Q-Matrix在遞迴數列上的延伸和其應用

終極密碼

遊戲規則:本遊戲為猜密碼的遊戲。密碼為0到100之間的其中1個整數,電腦會提示密碼的所在範圍,玩家必須在6次之內猜到密碼才能過關。

★ 終極密碼為0到100之間 ★
您共有六次機會

一、前言

Fibonacci 在 1202 年提出一個問題, 現在有一公一母的小兔子, 一個月之後這對小兔子長大成一對大兔子。 再過了一個月, 大兔子又生下了一公一母的小兔子, 所以有一對大兔子和一對小兔子共2對兔子。 在之後的每個月, 所有小兔子都會長成大兔子, 而每對大兔子都會生下一對小兔子。請問在 $n$ 個月之後, 總共有幾對兔子呢? 我們利用下面的表格來觀察一下

第0個月 第1個月第2個月第3個月第4個月
大兔子 0 1 1 2 3
小兔子 1 0 1 1 2
總和 1 1 2 3 5

會發現首項為1, 次項也為1, 之後每一項都是前兩項相加的數列。 而這就是 Fibonacci 數列 $\{F_n\}_{n=0}^\infty=\{1,1,2,3,\ldots\}$ 也是上面這個問題的答案。 換成數學的寫法可以寫成 $F_0=1$、 $F_1=1$ 而當 $n\ge 2$ 時 $F_n=F_{n-1}+F_{n-2}$ 這種遞迴規則的數列。 這是一個不論在數論或組合上都很有名的數列。 因為 Fibonacci 數列有很多有趣且很特殊的性質, 使得 Fibonacci 從 1202 年寫下它以後, 幾百年來一直到現在還持續的有人在研究它。

而 Fibonacci $Q$ 矩陣指的是 $\left[\begin{array}{cc} ~1~&~1~\\ ~1~&0 \end{array}\right]$ 的這個矩陣, 1960 年時 Charles H. King 在他的碩士論文中研究這個矩陣 (Koshy [10]), 而在 Gould 對 Fibonacci $Q$ 矩陣的歷史探討中也提出是否這矩陣能被延伸到三維的矩陣呢? 這矩陣為什麼會被稱為 Fibonacci $Q$ 矩陣呢? 這是因為這個矩陣和 Fibonacci 數列有一個如下的關係 (Gould [5])。 $$\left[\begin{array}{cc} ~1~&~1~\\ ~1~&0 \end{array}\right]^n=\left[\begin{array}{cc} ~F_n~&~F_{n-1}~\\ ~F_{n-1}~&F_{n-2} \end{array}\right]$$

矩陣有很多的性質可以利用, 所以如果數列和矩陣中間的關係找出來的話, 就能夠利用矩陣性質得到很多有趣的性質。 如 $F_{2n+1}=F_{n+1}^2+F_n^2$ 等 (Huang [9])。

現在我們就利用 $Q$ 矩陣這個放大鏡來檢視看看 Fibonacci 有什麼有趣的地方, 再把這放大鏡移到其他類似於 Fibonacci 的二階數列上看看有什麼結果。 接著再更進一步的來看看像 $h_0=a$, $h_1=b$ 且當 $n\ge 2$ 時 $h_n=ch_{n-1}+dh_{n-2}$, 其中 $a,b,c,d$ 為實數的這種一般的二階遞迴式是否也有一個類似於 Fibonacci $Q$ 矩陣和 Fibonacci 數列的矩陣恆等式呢?

而在知道這些用 $Q$ 矩陣得出的結果後, 我們是不是可以拿這些東西來運用呢? 很巧的, 我們發現這些性質可以應用在處理有關 log-convex 以及 log-concave 的問題上。

二、類似Fibonacci數列的二階遞迴數列

什麼樣的遞迴數列我們說它是類似 Fibonacci 數列的呢? 在觀察 Fibonacci 時會發現, 假設說數列可以一直往前倒著推回去的話, 我們將 Fibonacci 往回倒推一項到第 -1 項讓其也符合遞迴式時, 也就是說 $F_{-1}+F_0=F_1$ 時, 會得到 $F_{-1}=0$。

而現在我們就規定說如果第 -1 項為 0 的數列就是類似Fibonacci數列的遞迴數列。 那麼對以下這種型態的二階遞迴數列是否有類似 Fibonacci $Q$ 矩陣的矩陣 $Q$ 呢? $$g_n=\left\{\begin{array}{ccl} 0&~\quad&n=-1\\ a&&n=0\\ cg_{n-1}+dg_{n-2}&&n\ge 1\end{array}\right.$$

先做個猜測, 如果 $Q=\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]$ 是 $\{g_n\}$ 的 $Q$ 矩陣, 則當 $\{g_n\}$ 就是 Fibonacci 數列的情況下, $Q$ 和 Fibonacci $Q$ 矩陣是相同。 接著再觀察一下 $Q$ 的 $n$ 次方的情形。 $$Q^n\left[\begin{array}{cc} g_1\\ g_0 \end{array}\right]=\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^n\left[\begin{array}{cc} g_1\\ g_0 \end{array}\right]=\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^{n-1}\left[\begin{array}{cc} g_2\\ g_1 \end{array}\right]=\cdots=\left[\begin{array}{cc} g_{n+1}\\ g_n \end{array}\right]$$

但是由原來的二階遞迴數列的定義方式我們可以知道 $$\left[\begin{array}{cc} g_{n+1}\\ g_n \end{array}\right]=\left[\begin{array}{cc} cg_n+dg_{n-1}\\ cg_{n-1}+dg_{n-2} \end{array}\right]=\left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right]\left[\begin{array}{cc} ac\\ a \end{array}\right]=\left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right]\left[\begin{array}{cc} g_1\\ g_0 \end{array}\right]$$ 比較兩個等式的相似處, 猜測下面這個式子是否會永遠成立呢? $$Q^n=\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^n\left[\begin{array}{cc} g_1\\ g_0 \end{array}\right]=\left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right], \qquad \forall \ n\ge 1\hbox{。}$$

如果能寫出證明的話, 就能證實我們的猜測了。而我們現在就試著把這猜測的證明寫下來。

定理2-1:

令 $g_n=\left\{\begin{array}{ccl} 0&~\quad&n=-1\\ a&&n=0\\ cg_{n-1}+dg_{n-2}&&n\ge 1\end{array}\right.$, 而 $Q=\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]$

則 $Q^n=\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^n=\left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right]$, $\forall \ n\ge 1$。

證明: 利用數學規納法來證明之

(1) 當 $n=1$ 時 $$\left[\begin{array}{cc} \frac 1a g_1&\frac da g_0\\ ~\frac 1a g_0~&~\frac da g_{-1}~ \end{array}\right]=\left[\begin{array}{cc} \frac 1a ac&\frac da a\\ ~\frac 1a a~&~\frac da 0~ \end{array}\right]=\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^1$$ 定理 2-1 成立。

(2) 假設定理 2-1 對 $n=k$ 時成立, 也就是說 $$\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^k=\left[\begin{array}{cc} \frac 1a g_{k}&\frac da g_{k-1}\\ ~\frac 1a g_{k-1}~&~\frac da g_{k-2}~ \end{array}\right]$$ 那麼當 $n=k+1$ 的時候 \begin{eqnarray*} \left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^{k+1}&=&\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^k\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]=\left[\begin{array}{cc} \frac 1a g_{k}&\frac da g_{k-1}\\ ~\frac 1a g_{k-1}~&~\frac da g_{k-2}~ \end{array}\right]\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]\\ &=&\left[\begin{array}{cc} \frac {cg_k+dg_{k-1}}a&\frac da g_{k}\\ ~\frac {cg_{k-1}+dg_{k-2}}a ~&~\frac da g_{k-1}~ \end{array}\right]=\left[\begin{array}{cc} \frac 1a g_{k+1}&\frac da g_{k}\\ ~\frac 1a g_{k}~&~\frac da g_{k-1}~ \end{array}\right]\hbox{。} \end{eqnarray*}

(3) 由數學歸納法我們可以得出結論 $$Q^n=\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^n=\left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right], \quad \forall \ n\ge 1\hbox{。}{\Box}$$

接著由定理2-1中數列和 $Q$ 矩陣的關係, 藉由一些矩陣的運算我們可以得出一些有關這些數列的特殊性質。

性質2-2: $$(-d)^n=\frac{d}{a^2}(g_ng_{n-2}-g_{n-1}^2)$$

證明: 由定理2-1再取其行列式 $$\det\left(\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]\right)^n=\det\left(\left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right]\right),\quad \forall \ n\ge 1\hbox{。}$$

性質2-3: $$(-d)^{n+2}=\frac d{a^2}(g_n^2-cg_ng_{n-1}-dg_{n-1}^2)\hbox{。}$$

證明: 藉由性質2-2, $(-d)^n=\frac 1{a^2}(g_ng_{n-2}-g_{n-1}^2)$, 再將 $g_n=cg_{n-1}+dg_{n-2}$ 代入平移一項。

性質2-4: $$g_{n+m}=\frac 1a g_ng_m+\frac da g_{n-1}g_{m-1}=\frac 1a g_{n+1}g_{m-1}+\frac da g_ng_{m-2}$$

證明: 藉由定理2-1和矩陣相乘得出式子 \begin{eqnarray*} \left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^{n+m}&\!=\!&\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^n\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^m\\ \Leftrightarrow \left[\begin{array}{cc} \frac 1a g_{n+m}&\frac da g_{n+m-1}\\ ~\frac 1a g_{n+m-1}~&~\frac da g_{n+m-2}~ \end{array}\right]&\!=\!& \left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right] \left[\begin{array}{cc} \frac 1a g_{m}&\frac da g_{m-1}\\ ~\frac 1a g_{m-1}~&~\frac da g_{m-2}~ \end{array}\right]\\ &\!=\!&\left[\begin{array}{cc} \frac 1{a^2} g_ng_{m}+\frac d{a^2} g_{n-1}g_{m-1}&\frac d{a^2} g_ng_{m-1}+\frac {d^2}{a^2} g_{n-1}g_{m-2}\\ \frac 1{a^2} g_{n-1}g_{m}+\frac d{a^2} g_{n-2}g_{m-1}~&~\frac d{a^2} g_{n-1}g_{m-1}+\frac {d^2}{a^2} g_{n-2}g_{m-2}\\ \end{array}\right]\\ \end{eqnarray*} 觀察矩陣的左上方及右上方可以得到性質2-4。

性質2-5: $$(-d)^k\cdot g_{n-k}=\frac da g_ng_{k-2}-\frac da g_{n-1}g_{k-1}.$$

證明: 由定理2-1在 $n\gt k\ge 0$ 時, 利用矩陣乘法可以得到 \begin{eqnarray*} \left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^{n-k}&\!=\!&\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^n\left[\begin{array}{cc} ~c~&~d~\\ ~1~&0 \end{array}\right]^{-k}\\ \Leftrightarrow \left[\begin{array}{cc} \frac 1a g_{n-k}&\frac da g_{n-k-1}\\ ~\frac 1a g_{n-k-1}~&~\frac da g_{n-k-2}~ \end{array}\right]&\!=\!& \left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right] \left[\begin{array}{cc} \frac 1a g_{k}&\frac da g_{k-1}\\ ~\frac 1a g_{k-1}~&~\frac da g_{k-2}~ \end{array}\right]^{-1}\\ &\!=\!&\frac{1}{(-d)^k}\left[\begin{array}{cc} \frac d{a^2} g_ng_{k-2}-\frac d{a^2} g_{n-1}g_{k-1}&-\frac d{a^2} g_ng_{k-1}+\frac {d}{a^2} g_{n-1}g_{k}\\ \frac d{a^2} g_{n-1}g_{k-2}-\frac d{a^2} g_{n-2}g_{k-1}~&~-\frac d{a^2} g_{n-1}g_{k-1}+\frac {d}{a^2} g_{n-2}g_{k}\\ \end{array}\right]\\ \end{eqnarray*} 觀察等式左上角可以得到性質2-5。

推論2-6: 現在我們回頭來看 Fibonacci 數列的一些性質, 將以上這些性質代入 Fibonacci 數列可以得到以下結果: \begin{eqnarray*} (-1)^n&=&(F_nF_{n-2}-F_{n-1}^2)\\ (-1)^n&=&(F_n^2-F_nF_{n-1}-F_{n-1}^2)\\ F_{n+m}&=&F_nF_m+F_{n-1}F_{m-1}=F_{n+1}F_{m-1}+F_nF_{m-2}\\ (-1)^k\cdot F_{n-k}&=&F_nF_{k-2}-F_{n-1}F_{k-1} \end{eqnarray*}

又因為Fibonacci $Q$ 矩陣相較於其他的矩陣, 有更好的一些性質, 也就是 $Q^2=Q+I$ 及 $(Q-I)\cdot Q=I$, 所以能夠得到更好的一些結果:

性質2-7: $$F_{2n+p}=\sum_{i=0}^n{n\choose i}\cdot F_{i+p}.$$

證明: \begin{eqnarray*} \left[\begin{array}{cc} ~F_{2n+p}~&~F_{2n+p-1}~\\ ~F_{2n+p-1}~&~F_{2n+p-2}~ \end{array}\right]&=&Q^{2n+p}=Q^pQ^{2n}=Q^p(Q^2)^n\\ &=&Q^p(Q+I)^n=Q^p\sum_{i=0}^n {n\choose i} \cdot Q^i\\ &=& \left[\begin{array}{cc} ~F_p~&~F_{p-1}~\\ ~F_{p-1}~&~F_{p-2}~ \end{array}\right]\cdot \left[\begin{array}{cc} \displaystyle\sum_{i=0}^n {n\choose i} F_i~&~\displaystyle\sum_{i=0}^n {n\choose i} F_{i-1}\\ \displaystyle\sum_{i=0}^n {n\choose i} F_{i-1}~&~\displaystyle\sum_{i=0}^n {n\choose i} F_{i-2}\\ \end{array}\right] \end{eqnarray*} 再去查看矩陣的左上角就可以得到

性質2-8: $$F_1+F_2+\cdots+F_n=F_{n+2}-1$$

證明: \begin{eqnarray*} &&\hskip -25pt (I+Q+Q^2+\cdots+Q^n)\cdot (Q-I)=Q^{n+1}-1\\ &\Rightarrow&I+Q+Q^2+\cdots+Q^n=(Q^{n+1}-I)\cdot(Q-I)^{-1}\\ &\Rightarrow&I+Q+Q^2+\cdots+Q^n=Q^{n+2}-Q\\ &\Rightarrow&\left[\begin{array}{cc} ~\displaystyle\sum_{i=0}^n F_i~&~\displaystyle\sum_{i=0}^n F_{i-1}~\\ ~\displaystyle\sum_{i=0}^n F_{i-1}~&~\displaystyle\sum_{i=0}^n F_{i-2}~ \end{array}\right]=\left[\begin{array}{cc} ~F_{n+2}-F_1~&~F_{n+1}-F_0~\\ ~F_{n+1}-F_0~&~F_n-F_{-1}~ \end{array}\right] \end{eqnarray*}

三、一般二階遞迴數列

在知道了特殊情況下的二階遞迴數列與 $Q$ 矩陣的關係之後, 我們會想要知道是不是所有的二階遞迴數列都有類似關係呢? 一般的二階遞迴數列定義如下 $$h_n=\left\{\begin{array}{ccl} a&~\quad&n=0\\ b&&n=1\\ ch_{n-1}+dh_{n-2}&&n\ge 2\end{array}\right.$$

首先, 想先看看是不是除了類似 Fibonacci 數列之外, 還有其他種類數列和 $Q$ 矩陣有關。 由 Hoggatt & Ruggles [6], 我們可以知道 Lucas 數列和 Fibonacci-$Q$ 矩陣有關係 : $$\left[\begin{array}{cc} ~1~&~2~\\ ~2~&~-1~ \end{array}\right]\left[\begin{array}{cc} ~1~&~1~\\ ~1~&~0~ \end{array}\right]^n=\left[\begin{array}{cc} ~L_{n+1}~&~L_n~\\ ~L_n~&~L_{n-1}~ \end{array}\right]$$ 而 Lucas 數列 $\{L_n\}_{n=1}^\infty$ 就是 $a=2$, $b=1$, $c=1$, $d=1$ 的情形。

如果我們可以知道一般遞迴數列和之前討論的特殊數列的關係。 或許就能夠找出類似 Lucas 數列與 $Q$ 矩陣的關係式。 我們已經知道 Fibonacci-$Q$ 矩陣和 Fibonacci 數列有關, 再由以下運算發現 Lucas 數列和 Fibonacci 數列之間的關係。 \begin{eqnarray*} \left[\begin{array}{cc} ~1~&~2~\\ ~2~&~-1~ \end{array}\right]\left[\begin{array}{cc} ~1~&~1~\\ ~1~&~0~ \end{array}\right]^n&=&\left[\begin{array}{cc} ~L_{n+1}~&~L_n~\\ ~L_n~&~L_{n-1}~ \end{array}\right]\\ \Leftrightarrow \ \left[\begin{array}{cc} ~1~&~2~\\ ~2~&~-1~ \end{array}\right]\left[\begin{array}{cc} ~F_{n}~&~F_{n-1}~\\ ~F_{n-1}~&~F_{n-2}~ \end{array}\right]&=&\left[\begin{array}{cc} ~L_{n+1}~&~L_n~\\ ~L_n~&~L_{n-1}~ \end{array}\right]\\ \Leftrightarrow \ \left[\begin{array}{cc} ~F_n+2F_{n-1}~&~F_{n-1}+2F_{n-2}~\\ ~2F_n-F_{n-1}~&~2F_{n-1}-F_{n-2}~ \end{array}\right]&=&\left[\begin{array}{cc} ~L_{n+1}~&~L_n~\\ ~L_n~&~L_{n-1}~ \end{array}\right] \end{eqnarray*}

所以現在要試著找出一般二階遞迴數列 $\{h_n\}_{n\ge 0}$ 和之前所討論的特殊遞迴數列 $\{g_n\}_{\ge -1}$ 的關係式, 接著再結合定理2-1就可以得到一般遞迴數列和 $Q$ 矩陣的關係。

先比較之前的遞迴數列和一般的二階遞迴數列來猜測結果, 而為了要讓這兩個可以比較, 我們拿有相同遞迴關係及相同首項的兩個數列來觀察。 $$g_n=\left\{\begin{array}{ccl} a&~\quad&n=0\\ ac&&n=1\\ cg_{n-1}+dg_{n-2}&&n\ge 2\end{array}\right.\hskip 1.5cm h_n=\left\{\begin{array}{ccl} a&~\quad&n=0\\ b&&n=1\\ ch_{n-1}+dh_{n-2}&&n\ge 2\end{array}\right.$$

這兩個數列都擁有二階遞迴關係, 如果數列 $g_n$ 中的連續兩項和 $h_n$ 中的其中一項有線性關係, 那麼我們就可以利用遞迴關係去確認 $g_n$ 及 $h_n$ 其他項也會有此種線性關係。

我們可做些猜測, 如果 $h_n=sg_n+tg_{n-1}$

當 $n=0$ 的時候 $h_0=sg_0+tg_{-1}\ \Leftrightarrow\ a=sa+t0 \ \Leftrightarrow\ s=1$

當 $n=1$ 的時候 $h_1=sg_1+tg_{0}\ \Leftrightarrow\ b=sac+ta=ac+ta \ \Leftrightarrow\ t=\frac{b-ac}a$

由此, 我們可以猜出之前的特殊遞迴數列和一般遞迴數列的關係式。

定理3-1: 令 $$g_n=\left\{\begin{array}{ccl} 0&~\quad&n=-1\\ a&&n=0\\ cg_{n-1}+dg_{n-2}&&n\ge 1\end{array}\right.\hskip 1.5cm h_n=\left\{\begin{array}{ccl} a&~\quad&n=0\\ b&&n=1\\ ch_{n-1}+dh_{n-2}&&n\ge 2\end{array}\right.$$ 則 $\left[\begin{array}{cc} ~\frac ba~&~d~\\ ~1~&~\frac{b-ac}{a}~ \end{array}\right] \left[\begin{array}{cc} ~g_n~&~g_{n-1}~\\ ~g_{n-1}~&~g_{n-2}~ \end{array}\right]=\left[\begin{array}{cc} ~h_{n+1}~&~h_n~\\ ~h_n~&~h_{n-1}~ \end{array}\right]$。

證明: 先利用數學規歸納法證明矩陣下半部的式子 $h_n=g_n+\frac{b-ac}ag_{n-1}$

(1) 當 $n=0$, $h_0=a=a+\frac{b-ac}a0=g_0+\frac{b-ac}ag_{-1}$

當 $n=1$, $h_1=b=ac+\frac{b-ac}a a=g_1+\frac{b-ac}a g_{0}$

(2) 假設 $n\le k-1$ 定理 3-1 都是對的, 也就是說 $h_n=g_n+\frac{b-ac}ag_{n-1}$

當 $n=k$ 的時候 \begin{eqnarray*} h_k&=&ch_{k-1}+dh_{k-2}=c\Big(g_{k-1}+\frac{b-ac}a g_{k-2}\Big)+d\Big(g_{k-2}+\frac{b-ac}a g_{k-3}\Big)\\ &=&(cg_{k-1}+dg_{k-2})+\frac{b-ac}a (cg_{k-2}+dg_{k-3})\\ &=&g_k+\frac{b-ac}a g_{k-1} \end{eqnarray*} (3) 由數學歸納法可以知道 $h_n=g_n+\frac{b-ac}a g_{n-1}$

接著要證明上半部的式子, 在已經知道 $h_n=g_n+\frac{b-ac}a g_{n-1}$ 的情形下。 $$h_n=g_n+\frac{b-ac}a g_{n-1}=(cg_{n-1}+dg_{n-2})+\frac{b-ac}a g_{n-1}=\Big(\frac ba\Big)g_{n-1}+dg_{n-2}$$ 推導出矩陣上半部的式子 $h_n=\Big(\frac ba\Big)g_{n-1}+dg_{n-2}$

由這兩個關係式, 我們可以寫出一個矩陣的式子 $$\left[\begin{array}{cc} ~\frac ba~&~d~\\ ~1~&~\frac{b-ac}{a}~ \end{array}\right] \left[\begin{array}{cc} ~g_n~&~g_{n-1}~\\ ~g_{n-1}~&~g_{n-2}~ \end{array}\right]=\left[\begin{array}{cc} ~h_{n+1}~&~h_n~\\ ~h_n~&~h_{n-1}~ \end{array}\right]{\Box}$$

在找出一般遞迴數列和特殊遞迴數列的關係後, 我們可以把定理3-1的結果和定理2-1的結果結合, 得到下面這個定理。

定理3-2: $$ h_n=\left\{\begin{array}{ccl} a&~\quad&n=0\\ b&&n=1\\ ch_{n-1}+dh_{n-2}&&n\ge 2\end{array}\right.$$ $$\left[\begin{array}{cc} ~b~&~ad~\\ ~a~&~{b-ac}~ \end{array}\right] \left[\begin{array}{cc} ~c~&~d~\\ ~1~&~0~ \end{array}\right]^n=\left[\begin{array}{cc} ~h_{n+1}~&~dh_n~\\ ~h_n~&~dh_{n-1}~ \end{array}\right],\qquad n\ge 1.$$

證明: \begin{align*} \left[\begin{array}{cc} ~h_{n+1}~&~dh_n~\\ ~h_n~&~dh_{n-1}~ \end{array}\right]=&\left[\begin{array}{cc} ~h_{n+1}~&~h_n~\\ ~h_n~&~h_{n-1}~ \end{array}\right]\left[\begin{array}{cc} ~1~&~0~\\ ~0~&~d~ \end{array}\right]\\ =&\left[\begin{array}{cc} ~\frac ba~&~d~\\ ~1~&~\frac{b-ac}{a}~ \end{array}\right]\left[\begin{array}{cc} ~g_{n}~&~g_{n-1}~\\ ~g_{n-1}~&~g_{n-2}~ \end{array}\right]\left[\begin{array}{cc} ~1~&~0~\\ ~0~&~d~ \end{array}\right]\\ =&\left[\begin{array}{cc} ~b~&~ad~\\ ~a~&~b-ac~ \end{array}\right]\left[\begin{array}{cc} \frac 1a g_{n}&\frac da g_{n-1}\\ ~\frac 1a g_{n-1}~&~\frac da g_{n-2}~ \end{array}\right]=\left[\begin{array}{cc} ~b~&~ad~\\ ~a~&~b-ac~ \end{array}\right]\left[\begin{array}{cc} ~c~&~d~\\ ~1~&~0~ \end{array}\right]^n. \tag*{$\Box$} \end{align*}

同樣的, 利用定理3-2和矩陣運算, 我們可以發現這些一般二階遞迴數列的一些性質。

性質3-3: $$(h_1^2-h_2h_0)(-d)^n=d(h_{n+1}h_{n-1}-h_n^2).$$

證明: 由定理3-2和矩陣的行列式可以得到 \begin{align*} &\det\left(\left[\begin{array}{cc} ~b~&~ad~\\ ~a~&~b-ac~ \end{array}\right]\left[\begin{array}{cc} ~c~&~d~\\ ~1~&~0~ \end{array}\right]^n\right)=\det\left(\left[\begin{array}{cc} ~h_{n+1}~&~dh_n~\\ ~h_n~&~dh_{n-1}~ \end{array}\right]^n\right),\qquad n\ge 1\\ \Leftrightarrow\quad&(h_1^2-h_2h_0)(-d)^n=d(h_{n+1}h_{n-1}-h_n^2). \tag*{$\Box$} \end{align*}

四、在判斷 log-convex 及log-concave 上的應用

log-concave 是 logarithmically concave 的縮寫, 在 1989 年 Stanley 的文章中 (Stanley [13]) 說明了許多由代數、 組合以及幾何中與log-concave及unimodal數列的一些事物。像是利用直接計算來確認巴斯卡三角形的數列 ${n\choose 0}$, ${n\choose 1}$, $\ldots$, ${n\choose n}$, 是 log-concave、 若 $P(x)=\sum\limits_{j=0}^n {n\choose j} a_jx^j$ 是沒有根的多項式, 則 $\{a_j\}_{j\ge 0}$ 是 log-concave $\cdots$ 等結果。

那麼什麼是 log-concave 呢? 一般將 log-convex 和 log-concave 的定義如下

一個數列 $\{h_n\}_{n\in N\cup0}$ 被稱為 log-concave 如果 $h_{k-1}h_{k+1}\le h_k^2$, $k\ge 1$。

一個數列 $\{h_n\}_{n\in N\cup0}$ 被稱為 log-convex 如果 $h_{k-1}h_{k+1}\ge h_k^2$, $k\ge 1$。

而現在我們將藉由性質3-3, 我們能夠利用不同於其他證明的方法推導出在有關 log-convex 及 log-concave 的結果。

推論4-1: 令 $$h_n=\left\{\begin{array}{ccl} a&~\quad&n=0\\ b&&n=1\\ ch_{n-1}+dh_{n-2}&&n\ge 2\end{array}\right.$$

如 $d\!\lt \!0$ 且 $h_0h_2\!\ge\! h_1^2$, 則數列 $\{h_n\}_{n\in N\cup0}$ 為log-convex, 也就是說 $h_{k-1}h_{k+1}\!\ge\! h_k^2$, $k\!\ge\! 1$。

如 $d\!\lt \!0$ 且 $h_0h_2\!\le\! h_1^2$, 則數列 $\{h_n\}_{n\in N\cup0}$ 為log-concave, 也就是說 $h_{k-1}h_{k+1}\!\le\! h_k^2$, $k\!\ge\! 1$。

證明: 由性質3-3 $(h_1^2-h_2h_0)(-d)^n=d(h_{n+1}h_{n-1}-h_n^2)$

因為 $h_1^2-h_0h_2\le 0$, $d\lt 0$, 所以 $h_{n+1}h_{n-1}-h_n^2\!\ge\! 0 \Rightarrow h_{n+1}h_{n-1}\ge h_n^2$。

因為 $h_1^2-h_0h_2\ge 0$, $d\lt 0$, 所以 $h_{n+1}h_{n-1}-h_n^2\!\le\! 0 \Rightarrow h_{n+1}h_{n-1}\le h_n^2$。

同樣的我們可得到。

推論4-2: $$h_n=\left\{\begin{array}{ccl} a&~\quad&n=0\\ b&&n=1\\ ch_{n-1}+dh_{n-2}&&n\ge 2\end{array}\right.$$

假如 $d\!\gt \!0$ 而且 $h_0h_2\!\ge\! h_1^2$, 那麼 $h_{2k-2}h_{2k}\!\ge\! h_{2k-1}^2$, $k\ge 1$ 而 $h_{2k-1}h_{2k+1}\!\le\! h_{2k}^2$, $k\!\ge\! 1$。

假如 $d\!\gt \!0$ 而且 $h_0h_2\!\le\! h_1^2$, 那麼 $h_{2k-2}h_{2k}\!\le\! h_{2k-1}^2$, $k\ge 1$ 而 $h_{2k-1}h_{2k+1}\!\ge\! h_{2k}^2$, $k\!\ge\! 1$。

證明: 如同推論4-1。

推論4-3: 而在 Lily [12] 和 Doslic & Veljan [4] 提出了一些有關特殊數列的一些性質。

$F_{2k-2}F_{2k}\ge F_{2k-1}^2$, $k\ge 1$,$L_{2k-2}L_{2k}\ge L_{2k-1}^2$, $k\ge 1$,$P_{2k-2}P_{2k}\ge P_{2k-1}^2$, $k\ge 1$
$F_{2k-2}F_{2k+1}\le F_{2k}^2$, $k\ge 1$,$L_{2k-1}L_{2k+1}\le L_{2k}^2$, $k\ge 1$,$P_{2k-1}P_{2k+1}\le P_{2k}^2$, $k\ge 1$

在這裡我們利用不同與前兩篇的方法, 我們可以計算前三項

Fibonacci 數列 $F_n=F_{n-1}+F_{n-2}$, $2=F_0F_2\ge F_1^2=1$。

Lucas 數列 $L_n=L_{n-1}+L_{n-2}$, $6=L_0L_2\ge L_1^2=1$。

Pell 數列 $P_n=2P_{n-1}+P_{n-2}$, $5=P_0P_2\ge P_1^2=4$。

再由推論4-2可以得到和 Lily [12] 和 Doslic & Veljan [4] 相同的結果。

除了性質3-3以外, 將結果稍微調整, 可以得到下面這個性質。

推論4-4: $$(h_1^2-h_2h_0)(-d)^n=(h_{n+1}^2-ch_{n+1}h_n-dh_n^2).$$

證明: 由性質3-3 $(h_1^2-h_2h_0)(-d)^n=d(h_{n+1}h_{n-1}-h_{n}^2)$ 將 $h_{n+1}=ch_n+dh_{n-1}$ 代入, 再把 $n$ 換成 $n+1$ 可以得到 \begin{eqnarray*} (h_1^2-h_2h_0)(-d)^{n+1}&=&d(dh_n^2+ch_{n+1}h_n-h_{n+1}^2) \\ \Leftrightarrow\quad (h_1^2-h_2h_0)(-d)^{n}&=&(h_{n+1}^2-ch_{n+1}h_n-dh_{n}^2) \end{eqnarray*} 而這和 Astin [1] 的結果是相同的

五、致謝

這篇文章是在參加中央研究院數學研究所的暑期研習生計畫時完成, 特別感謝薛昭雄老師的指導以及中央研究院數學研究所給的機會。 同時也感謝審查者用心的建議, 使得這篇文章更完整。

六、附錄

以下是一些著名的數列符合之前所說的情形:

Fibonacci 數列$a=1$, $c=1$, $d=1$Hoggatt Ruggles [6]
Fibonacci 多項式$a=1$, $c=x$, $d=1$Civciv Türkmen [3]
Lucas 數列$a=2$, $b=1$, $c=1$, $d=1$Hoggatt Ruggles [6]
Lucas 多項式$a=2$, $b=x$, $c=x$, $d=1$Horadam [7]
Pell 數列$a=1$, $c=2$, $d=1$Horadam Mahon [8]
Pell 多項式$a=1$, $c=2x$, $d=1$Hordam [8]
Pell-Lucas 多項式$a=2$, $b=2x$, $c=2x$, $d=1$Horadam Mahon [8]
第一種 Chebyshev 多項式$a=1$, $b=x$, $c=2x$, $d=-1$Horadam [7]
第二種 Chebyshev 多項式$a=1$, $c=2x$, $d=-1$Chen [2]
第一種 Dickson 多項式$a=2$, $b=x$, $c=x$, $d=-a$ Lidl Mullen Turnwald [11]
第二種 Dickson 多項式$a=1$, $c=x$, $d=-a$Lidl Mullen Turnwald [11]
Jacobsthal 數列$a=1$, $c=1$, $d=2$Horadam [7]
Jacobsthal 多項式$a=1$, $c=1$, $d=2x$Hordam [7]
Jacobsthal-Lucas 多項式$a=2$, $b=1$, $c=1$, $d=2x$Horadam [7]
Fermat 多項式$a=1$, $c=3x$, $d=-2$Hordam [7]
Femat-Lucas 多項式$a=2$, $b=3x$, $c=3x$, $d=-2$Horadam [7]
Morgan-Voyce 多項式$a=1$, $c=x+2$, $d=-1$Swamy [14] [15]
Mersenne 數列$a=1$, $c=3$, $d=-2$Horadam [7]
Koshy多項式$a=1$, $c=1$, $d=x$Astin [1]

七、參考資料

Astin, Jack, A Discriminant That Forms a Geometric Sequence, The Mathematical Gazette (July2008), pp.286-287. Chen, William Y. C., The combinatorial power of the companion matrix, Linear Algebra and its Applications (1996) 232: pp.261-278. Civciv, Hacl and Türkmen, Ramazan, On the $(s,t)$-Fibonacci and Fibonacci matrix sequences, ARS Combinatoria 87(2008), pp.162-173. Doslic, T. and Veljan, E., Logarithmic behavior of some combinatorial sequences, Discrete Mathematics 308(2008), pp.2182-2212. Gould, H.W., A history of the Fibonacci Q-matrix and a higher-dimensional problem, Fibonacci Quarterly(1981), Volume 19, pp.250-257. Hoggatt, V.E. Jr. and Ruggles, I. D., A primer for the Fibonacci number---Part IV, Fibonacci Quarterly (1963) Volume 1, pp.65-71. Horadam, A.F., A synthesis of certain polynomial sequences, Applications of Fibonacci Numbers(1968), Volume 6, pp.215-229. Horadam, A.F. and Mahon, Bro. J. M., Pell and Pell-Lucas polynomials, Fibonacci Quarterly(1985), Volume 23, pp.7-20. Huang, Danrun, Fibonacci identities, matrices, and graphs, Mathematics Teacher 98(February 2005), pp.400-403. Koshy,Thomas, Fibonacci and Lucas Numbers with Applications, A Wiley-Interscience Publication, 2001. Lidl, .R., Mullen, G. L.and Turnwald, G., Dickson Polynomials, Pitman Monographs and Surveys in Pure and Applied Mathematics, 65, Longman Scientific & Technical, Harlow; copublished in the United States with John Wiley & Sons, Inc., New York, 1993. Liu, Lily L.and Wang, Yi, On the log-convexity of combinatorial sequences, Advances in Applied Mathematics 39(2007), pp.454-476. Stanley, Richard P., Log-concave and unimodal sequences in algebra, combinatorics, and geometry, Ann. New York Acad. Sci. 576 (1989), 500-535. Swamy, M.N.S., Further properties of Morgan-Voyce polynomials, Fibonacci Quarterly(1968) Volume 6, pp.167-175. Swamy, M. N. S., Properties of the polynomials defined by Morgan-Voyce, Fibonacci Quarterly (1966), Volume 4, pp.75-81.

---本文作者於投稿時為國立台灣大學數學系四年級學生---

文章 推薦

電腦模擬與賭局

假設玩家A和B進行賭博。玩家A有m元,玩家B則有n元,然後擲1個公正的硬幣。如果出現正面就算玩家A贏,反面就算玩家B贏。每次賭注都是1元,如果A贏則A變m+1元、而B變n−1元,並稱此為1回合。雙方不斷地進行賭博,直到某方的錢歸零為止。在這個賭博中,有以下兩個問題:(1)玩家A和玩家B贏的機率各是多少?(2)每投1次硬幣決勝負,都稱為1回合,平均要幾回合,賭局才會結束(某方錢輸光)?....閱讀更多