38108 用矩陣方法探討三階遞迴數列

終極密碼

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

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

一、前言

義大利數學家 Fibonacci 於 1202 年在其著作中提出兔子問題, 這個問題造就了現在廣為人知的 Fibonacci 數列: $$F_{n+2}=F_{n+1}+F_n,\qquad F_0=F_1=1,$$ 利用幾何的方式, 我們可以將Fibonacci數列表現出來, 如圖一。

圖一中, 正方形的邊長由小至大恰為 Fibonacci 數列, 在每個正方形內加上以其邊長為半徑的圓, 可以得到一條優美的螺線 (spiral), 這條螺線可以做為對數螺線 (logarithmetic spiral) 的近似。

若我們將圖一中的正方形以正三角形替代, 依照類似的方法排列, 也可以得到類似的結果, 如圖二。這些正三角形的邊長由小到大形成一個新的數列, 稱為 Padovan 數列

Padovan 數列 $\{P_n\}$ 是由 Ian Stewart 在科學人雜誌 1996 年 6 月號所提出, 滿足三階遞迴關係式 $$P_{n+3}=P_{n+1}+P_n,\qquad P_0=P_1=P_2=1,$$ 以建築師 Richard Padovan 的名字命名。

另一個與 $\{P_n\}$ 有關的是 Perrin 數 $\{R_n\}$, 滿足遞迴關係 $$R_{n+3}=R_{n+1}+R_n,\qquad R_0=3,R_1=0,R_2=2,$$ 與 $\{P_n\}$ 具有相同的遞迴式, 但不同的初始值。

對於 Padovan 數及 Perrin 數的研究, 近年來已有一些結果, 使用的工具有生成函數、 矩陣方法$\cdots$等等。本文將利用矩陣方法研究 Padovan 數列, 為此需要先探討一些一般三階遞迴多項式所具備的性質。 在這過程中, 我們也發現我們的成果部分回答了 Gould 於其文章 --- A history of the Fibonacci $Q$-matrix and a higher dimensional problem最末提出該如何推廣二階的 Fibonacci $Q$-矩陣到三階、四階甚至更高階的問題。

利用矩陣方法處理二階遞迴數列已見於多處文獻, 如 , 。 最近在數學傳播 36 卷第二期中林鈺傑 定義 $$Q=\left[\begin{array}{cc} ~c~&~d~\\ ~0~&~1~ \end{array}\right]$$ 並用其處理二階遞迴數列 $\{x_n\}$ 及 $\{y_n\}$, 其中數列 $\{x_n\}$ 滿足遞迴式 $$x_{n+1}=cx_{n+1}+dx_n,\quad x_0=a,\ x_{-1}=0,$$ 數列 $\{y_n\}$ 滿足 $$y_{n+1}=cy_{n+1}+dy_n,\quad y_0=x_0=a,\ y_{1}=b,$$ 他利用 $Q$-矩陣得到一些二階遞迴數列的恆等式。 這讓我們想到若用類似的矩陣方法處理三階遞迴式是否可以與 Gould 提出的問題做連結, 並得到常係數三階遞迴數列的一些性質。

在第二節中, 我們考慮一個三階遞迴數列 $\{a_n\}$ 滿足遞迴式 $$a_{n+3}=pa_{n+2}+qa_{n+1}+ra_n\quad (r\not=0),$$ 其初始條件為 $a_{-2}=a_{-1}=0$、 $a_0=a\not=0$, 令 $$Q=\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]$$ 並證明給定一個所有元素皆由數列 $\{a_n\}$ 以某種固定的形式組成的 $3\times 3$ 方陣, 此種方陣可以表示成 $Q$ 的乘冪, 我們可以由這個性質得到一些數列 $\{a_n\}$ 的恆等式, 其中 Waddill 稱 $Q$ 為 $S$-矩陣。

在第三節中, 我們將第二節證明的性質做了一些調整, 使其可以應用在一般的常係數三階遞迴關係, 從而可以得到一些關於此類遞迴數列的恆等式。

最後在第四節中, 我們以前兩節得到的性質做工具, 導出了一連串關於 Padovan 數列 的恆等式。

二、特殊三階遞迴數列的性質

本文於此節及下一節中同樣以矩陣方法研究三階遞迴數列, 並導出幾個可以與林鈺傑 的二階遞迴數列相對應的三階遞迴數列性質, 我們將在第三節末將其列出比較。

首先, 考慮一個三階遞迴數列 $\{a_n\}_{n\in Z}$, 滿足遞迴式 $$a_{n+3}=pa_{n+2}+qa_{n+1}+ra_n\quad (r\not=0),$$ 其初始條件為 $a_{-2}=a_{-1}=0$、 $a_0=a\not=0$。

直接計算可得 $a_{-3}=\dfrac ar$、 $a_{-4}=-\dfrac{qa}{r^2}$、 $a_1=pa$ 及 $a_2=(p^2+q)a$。

我們可以將遞迴式用矩陣表示如下: $$\left[\begin{array}{c} ~a_{n+3}~\\ ~a_{n+2}~\\ ~a_{n+1}~ \end{array}\right]=\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]\left[\begin{array}{c} ~a_{n+2}~\\ ~a_{n+1}~\\ ~a_{n}~ \end{array}\right].$$ 以下便是這一節的一些主要定理。

定理1. 對任意整數 $n$ 皆有 \begin{equation} Q^n=\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n=\frac 1a\left[\begin{array}{ccc} ~a_n~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right] \label{2.1} \end{equation}

證明: 我們將利用數學歸納法證明。

當 $n=0$ 時, $$\frac 1a\left[\begin{array}{ccc} ~a_0~&~qa_{-1}+ra_{-2}~&~ra_{-1}~\\ ~a_{-1}~&~qa_{-2}+ra_{-3}~&~ra_{-2}~\\ ~a_{-2}~&~qa_{-3}+ra_{-4}~&~ra_{-3}~ \end{array}\right]=\frac 1a\left[\begin{array}{ccc} ~a~&~0~&~0~\\ ~0~&~a~&~0~\\ ~0~&~0~&~a~ \end{array}\right]=I_3=Q^0,$$ 成立。假設 $n=k\ge 0$ 時, 有 $$Q^k=\frac 1a\left[\begin{array}{ccc} ~a_k~&~qa_{k-1}+ra_{k-2}~&~ra_{k-1}~\\ ~a_{k-1}~&~qa_{k-2}+ra_{k-3}~&~ra_{k-2}~\\ ~a_{k-2}~&~qa_{k-3}+ra_{k-4}~&~ra_{k-3}~ \end{array}\right].$$ 現在考慮 $n=k+1$, 則 \begin{eqnarray*} Q^{k+1}=Q^kQ&=&\frac 1a\left[\begin{array}{ccc} ~a_k~&~qa_{k-1}+ra_{k-2}~&~ra_{k-1}~\\ ~a_{k-1}~&~qa_{k-2}+ra_{k-3}~&~ra_{k-2}~\\ ~a_{k-2}~&~qa_{k-3}+ra_{k-4}~&~ra_{k-3}~ \end{array}\right]\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{ccc} ~pa_k+qa_{k-1}+ra_{k-2}~&~qa_{k}+ra_{k-1}~&~ra_{k}~\\ ~pa_{k-1}+qa_{k-2}+ra_{k-3}~&~qa_{k-1}+ra_{k-2}~&~ra_{k-1}~\\ ~pa_{k-2}+qa_{k-3}+ra_{k-4}~&~qa_{k-2}+ra_{k-3}~&~ra_{k-2}~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{ccc} ~a_{k+1}~&~qa_{k}+ra_{k-1}~&~ra_{k}~\\ ~a_{k}~&~qa_{k-1}+ra_{k-2}~&~ra_{k-1}~\\ ~a_{k-1}~&~qa_{k-2}+ra_{k-3}~&~ra_{k-2}~ \end{array}\right].\\ \end{eqnarray*} 故由數學歸納法知 $$Q^n=\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n=\frac 1a\left[\begin{array}{ccc} ~a_{n}~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right]$$ 對所有正整數 皆成立。

實際上, 此定理也適用於負整數。注意到, 對任意正整數 $n$, \begin{eqnarray*} \left[\begin{array}{c} ~a_{0}~\\ ~a_{-1}~\\ ~a_{-2}~ \end{array}\right]&=& \left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]\left[\begin{array}{c} ~a_{-1}~\\ ~a_{-2}~\\ ~a_{-3}~ \end{array}\right]= \left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^2\left[\begin{array}{c} ~a_{-2}~\\ ~a_{-3}~\\ ~a_{-4}~ \end{array}\right]\\ &=&\cdots= \left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n\left[\begin{array}{c} ~a_{-n}~\\ ~a_{-n-1}~\\ ~a_{-n-2}~ \end{array}\right]. \end{eqnarray*} 從而 $$\left[\begin{array}{c} ~a_{-n}~\\ ~a_{-n-1}~\\ ~a_{-n-2}~ \end{array}\right]= \left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^{-n}\left[\begin{array}{c} ~a_{0}~\\ ~a_{-1}~\\ ~a_{-2}~ \end{array}\right],$$ 於是我們有 \begin{eqnarray*} &&\hskip -25pt \left[\begin{array}{ccc} ~a_{-n}~&~qa_{-n-1}+ra_{-n-2}~&~ra_{-n-1}~\\ ~a_{-n-1}~&~qa_{-n-2}+ra_{-n-3}~&~ra_{-n-2}~\\ ~a_{-n-2}~&~qa_{-n-3}+ra_{-n-4}~&~ra_{-n-3}~ \end{array}\right]\\ &=&\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^{-n} \left[\begin{array}{ccc} ~a_{0}~&~qa_{-1}+ra_{-2}~&~ra_{-1}~\\ ~a_{-1}~&~qa_{-2}+ra_{-3}~&~ra_{-2}~\\ ~a_{-2}~&~qa_{-3}+ra_{-4}~&~ra_{-3}~ \end{array}\right]\\ &=&\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^{-n} \left[\begin{array}{ccc} ~a~&~0~&~0~\\ ~0~&~a~&~0~\\ ~0~&~0~&~a~ \end{array}\right]=a\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^{-n}, \end{eqnarray*} 即 $$\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^{-n}=\frac 1a\left[\begin{array}{ccc} ~a_{-n}~&~qa_{-n-1}+ra_{-n-2}~&~ra_{-n-1}~\\ ~a_{-n-1}~&~qa_{-n-2}+ra_{-n-3}~&~ra_{-n-2}~\\ ~a_{-n-2}~&~qa_{-n-3}+ra_{-n-4}~&~ra_{-n-3}~ \end{array}\right].\tag*{$\Box$}$$

利用 \eqref{2.1}, 我們可以得到一些 $\{a_n\}$ 的恆等式, 如下述的定理 2 及定理 3。 令 $A$ 為一方陣, 我們以 $\det (A)$ 代表方陣 $A$ 的行列式值。

定理2. 對任意整數 $n$ 有 $$\det\left(\begin{array}{ccc} ~a_n~&~a_{n+1}~&~a_{n+2}~\\ ~a_{n-1}~&~a_n~&~a_{n+1}~\\ ~a_{n-2}~&~a_{n-1}~&~a_n~ \end{array}\right)=a^3r^n.$$

證明: \begin{eqnarray*} r^n&=&\det(Q^n)=\frac 1{a^3}\det \left(\begin{array}{ccc} ~a_n~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right)\\ &=&\frac 1{a^3}\det \left(\begin{array}{ccc} ~a_n~&~ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~ra_{n-4}~&~ra_{n-3}~ \end{array}\right)=\frac{r^2}{a^3}\det \left(\begin{array}{ccc} ~a_n~&~a_{n-2}~&~a_{n-1}~\\ ~a_{n-1}~&~a_{n-3}~&~a_{n-2}~\\ ~a_{n-2}~&~a_{n-4}~&~a_{n-3}~ \end{array}\right)\\ &=&\frac{r^2}{a^3}\det \left(\begin{array}{ccc} ~a_{n-2}~&~a_{n-1}~&~a_{n}~\\ ~a_{n-3}~&~a_{n-2}~&~a_{n-1}~\\ ~a_{n-4}~&~a_{n-3}~&~a_{n-2}~ \end{array}\right). \end{eqnarray*} 因此 $$\det\left(\begin{array}{ccc} ~a_{n-2}~&~a_{n-1}~&~a_{n}~\\ ~a_{n-3}~&~a_{n-2}~&~a_{n-1}~\\ ~a_{n-4}~&~a_{n-3}~&~a_{n-2}~ \end{array}\right)=a^3\frac {r^n}{r^2}=a^3r^{n-2}.\tag*{$\Box$}$$

定理3. 對任意整數 $m,n$, 我們有 $$a_{m+n}=\frac 1a[a_ma_n+qa_{n-1}a_{m-1}+r(a_{n-2}a_{m-1}+a_{n-1}a_{m-2})].$$

證明: 考慮 $Q$ 之 $(m+n)$ 次乘冪, 由 \eqref{2.1} 可得 $$Q^{m+n}=\frac 1a\left[\begin{array}{ccc} ~a_{m+n}~&~qa_{m+n-1}+ra_{m+n-2}~&~ra_{m+n-1}~\\ ~a_{m+n-1}~&~qa_{m+n-2}+ra_{m+n-3}~&~ra_{m+n-2}~\\ ~a_{m+n-2}~&~qa_{m+n-3}+ra_{m+n-4}~&~ra_{m+n-3}~ \end{array}\right].$$ 上式等號左邊可寫成 \begin{eqnarray*} Q^{m+n}&=&Q^mQ^n\\ &=&\frac 1{a^2}\left[\begin{array}{ccc} ~a_{m}~&~qa_{m-1}+ra_{m-2}~&~ra_{m-1}~\\ ~a_{m-1}~&~qa_{m-2}+ra_{m-3}~&~ra_{m-2}~\\ ~a_{m-2}~&~qa_{m-3}+ra_{m-4}~&~ra_{m-3}~ \end{array}\right]\left[\begin{array}{ccc} ~a_{n}~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right]. \end{eqnarray*} 比較 $Q^{m+n}$ 中的 (1,1) 元素可得 $$a_{m+n}=\frac 1a[a_ma_n+qa_{n-1}a_{m-1}+r(a_{n-2}a_{m-1}+a_{n-1}a_{m-2})].\tag*{$\Box$}$$

以下我們給出一個 $\{a_n\}_{n\in Z}$ 的實際例子:

Barry 證明了一個三階遞迴數列若具有 $$\dfrac 1{1-kx-kx^2+x^3}$$ 形式的生成函數, 則此三階遞迴數列可以寫成某一個二階遞迴數列連續兩項的乘積, 在文章中他以 Fibonacci 數列 $\{F_n\}_{n\ge 0}$ 連續兩項的乘積 $\{F_nF_{n+1}\}_{n\ge 0}$ 做為整篇文章的楔子。

若令 Fibonacci 數列之初始值為 $F_0=F_1=1$, 並將 $\{F_nF_{n+1}\}_{n\ge 0}$ 的底標延伸到負數, 令 $H_n=F_nF_{n+1}$, 則 $\{H_n\}_{n\in Z}$ 滿足遞迴式 $$H_{n+3}=2H_{n+2}+2H_{n+1}-H_n,\quad H_{-1}=H_{-2}=0,\quad H_0=1.$$

[註]: 事實上, 任意常係數二階遞迴式 $\{c_n\}$ 滿足遞迴關係 $$c_{n+2}=pc_{n+1}+qc_n,$$ 其連續兩項相乘所得之數列 $\{c_nc_{n+1}\}$ 皆會滿足一個三階遞迴關係, 如下: $$c_{n+3}c_{n+4}=(p^2+q)c_{n+2}c_{n+3}+q(p^2+q)c_{n+1}c_{n+2}-q^3c_nc_{n+1}.$$ 因為 $H_{-1}=H_{-2}=0$, $\{H_n\}$ 跟這一節的 $\{a_n\}$ 是同一類的遞迴數列, 於是由 \eqref{2.1} 知 \begin{equation} Q^n=\left[\begin{array}{ccc} ~2~&~2~&~-1~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n=\left[\begin{array}{ccc} ~H_{n}~&~2H_{n-1}-H_{n-2}~&~-H_{n-1}~\\ ~H_{n-1}~&~2H_{n-2}-H_{n-3}~&~-H_{n-2}~\\ ~H_{n-2}~&~2H_{n-3}-H_{n-4}~&~-H_{n-3}~ \end{array}\right]. \label{2.2} \end{equation} 利用定理2及定理3可分別得到以下恆等式

(i) 對任意整數 $n$ 有 $$\det\left(\begin{array}{ccc} ~H_{n}~&~H_{n+1}~&~H_{n+2}~\\ ~H_{n-1}~&~H_{n}~&~H_{n+1}~\\ ~H_{n-2}~&~H_{n-1}~&~H_{n}~ \end{array}\right)=(-1)^n.$$ (ii) 對任意整數 $m,n$, 我們有 $$H_{m+n}=H_mH_n+2H_{n-1}H_{m-1}-(H_{n-2}H_{m-1}+H_{n-1}H_{m-2}).$$

除了這些可以直接由定理得到的恆等式, 若遞迴數列的特徵多項式夠好時, 我們也可以利用 Cayley-Hamilton 定理 及 \eqref{2.1} 得到其他恆等式, 如下:

因 $Q$ 的特徵多項式為 $x^3-2x^2-2x+1=0$, 由 Cayley-Hamilton 定理可得 \begin{equation} Q^3-2Q^2-2Q+I=(Q+I)(Q^2-3Q+I)=0.\label{2.3} \end{equation}

定理4. 對任意正整數 $n$ 及整數 $r$, 有 $$\sum_{k=0}^n{n\choose k} F_{r+3k}F_{r+3k+1}=2^n\sum_{k=0}^n {n\choose k}F_{n+r+k}F_{n+r+k+1}.$$

證明: 由 \eqref{2.3} 知 $Q^3+I=2Q^2+2Q=2Q(Q+I)$, 等式兩邊同取 $n$ 次乘冪得 $$\sum_{k=0}^n{n\choose k} Q^{3k}=(Q^3+I)^n=2^nQ^n(Q+I)^n=2^n\sum_{k=0}^n {n\choose k}Q^{n+k}.$$ 兩邊同乘 $Q^r$ 並將 \eqref{2.2} 代入, 比較矩陣兩邊 (1,1) 元素可得 $$\sum_{k=0}^n {n\choose k}H_{r+3k}=2^n\sum_{k=0}^n{n\choose k}H_{n+r+k}.$$ 將 $H_{r+3k},H_{n+r+k}$ 換回 $F_{r+3k}F_{r+3k+1}$, $F_{n+r+k}F_{n+r+k+1}$ 可得結果。 $\tag*{$\Box$}$

對定理 4 中等式左邊做逆運算 () $$f_n=\sum_{k=0}^n {n\choose k}g_k\quad (n\ge 0)\Leftrightarrow g_n=\sum_{k=0}^n (-1)^{n-k}{n\choose k}f_k,$$ 將 $2^n\sum\limits_{k=0}^n{n\choose k}H_{n+r+k}$ 代入 $f_n$, $F_{r+3k}F_{r+3k+1}$ 代入 $g_k$, 我們得到以下推論:

推論5. 對任意正整數 $n$ 及整數 $r$, 有 $$F_{3n+r}F_{3n+r+1}=\sum_{k=0}^n\sum_{l=0}^k (-1)^{n-k}{n\choose k}{k\choose l} 2^kF_{k+l+r}F_{k+l+r+1}.$$ 上述定理 4 及推論 5 之結果是 Fibonacci 數列新的恆等式。

三、一般三階遞迴數列的性質

有了第二節的性質, 現在我們希望對一般的常係數三階遞迴數列滿足 $$b_{n+3}=pb_{n+2}+qb_{n+1}+rb_n,$$ 其初始條件為 $b_0=a_0=a$, $b_1=b$, $b_2=c$, $\{b_n\}$ 也能類似 \eqref{2.1} 表示為 $Q$ 的乘冪。 然而經過多番嘗試, 這似乎是難以辦到的, 所以我們退而求其次, 透過將 $b_{n+2}$, $b_{n+1}$, $b_n$ 表示為 $a_n$, $a_{n-1}$, $a_{n-2}$ 的線性組合, 將其以矩陣型式表現出來, 希望透過 $\{b_n\}$ 與 $\{a_n\}$ 間的聯繫來接近我們的目標。

定理6. 對任意正整數 $n$, 我們有 $$\left[\begin{array}{c} ~b_{n+2}~\\ ~b_{n+1}~\\ ~b_{n}~ \end{array}\right]=\frac 1a\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right]\left[\begin{array}{c} ~a_{n}~\\ ~a_{n-1}~\\ ~a_{n-2}~ \end{array}\right],$$ 其中 $$\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right]=\left[\begin{array}{ccc} ~b_2~&~b_3-pb_2~&~rb_1~\\ ~b_1~&~b_2-pb_1~&~rb_0~\\ ~b_0~&~b_1-pb_0~&~rb_{-1}~ \end{array}\right].$$

證明: 我們利用數學歸納法證明。當 $n=0$ 時, \begin{eqnarray*}\frac 1a\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right]\left[\begin{array}{c} ~a_{0}~\\ ~a_{-1}~\\ ~a_{-2}~ \end{array}\right]&=&\frac 1a\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right]\left[\begin{array}{c} ~a~\\ ~0~\\ ~0~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{c} ~ca~\\ ~ba~\\ ~a^2~ \end{array}\right]=\left[\begin{array}{c} ~c~\\ ~b~\\ ~a~ \end{array}\right] \end{eqnarray*} 假設對所有 $n\le k$ 原命題皆成立。則 $n=k+1$, 我們有 \begin{eqnarray*} \left[\begin{array}{c} ~b_{k+3}~\\ ~b_{k+2}~\\ ~b_{k+1}~ \end{array}\right]&=& \left[\begin{array}{c} ~pb_{k+2}+qb_{k+1}+rb_k~\\ ~pb_{k+1}+qb_{k}+rb_{k-1}~\\ ~pb_{k}+qb_{k-1}+rb_{k-2}~ \end{array}\right]=p\left[\begin{array}{c} ~b_{k+2}~\\ ~b_{k+1}~\\ ~b_{k}~ \end{array}\right]+q\left[\begin{array}{c} ~b_{k+1}~\\ ~b_{k}~\\ ~b_{k-1}~ \end{array}\right]+r\left[\begin{array}{c} ~b_{k}~\\ ~b_{k-1}~\\ ~b_{k-2}~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right] \left( p\left[\begin{array}{c} ~a_{k}~\\ ~a_{k-1}~\\ ~a_{k-2}~ \end{array}\right]+q\left[\begin{array}{c} ~a_{k-1}~\\ ~a_{k-2}~\\ ~a_{k-3}~ \end{array}\right]+r\left[\begin{array}{c} ~a_{k-2}~\\ ~a_{k-3}~\\ ~a_{k-4}~ \end{array}\right] \right)\\ &=&\frac 1a\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right] \left[\begin{array}{c} ~pa_{k}+qa_{k-1}+ra_{k-2}~\\ ~pa_{k-1}+qa_{k-2}+ra_{k-3}~\\ ~pa_{k-2}+qa_{k-3}+ra_{k-4}~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right] \left[\begin{array}{c} ~a_{k+1}~\\ ~a_{k}~\\ ~a_{k-1}~ \end{array}\right]. \end{eqnarray*} 當矩陣為 $[b_{-n}\ b_{-n-1}\ b_{-n-2}]^T$ $(n\ge0)$, 類似作法對 $n$ 做數學歸納法可證明原命題對負整數亦成立。 $\tag*{$\Box$}$

為了方便, 以後的討論裡我們一律將 $\left[\begin{array}{ccc} ~b_2~&~b_3-pb_2~&~rb_1~\\ ~b_1~&~b_2-pb_1~&~rb_0~\\ ~b_0~&~b_1-pb_0~&~rb_{-1}~ \end{array}\right]$ 記為 $A$。

有定理 6 的幫助, 我們就可以將 $\{b_n\}$ 與其 $S$-矩陣 $Q$ 聯繫再一起。

定理7. 對任意整數 $n$, \begin{equation} \left[\begin{array}{ccc} ~b_{n+2}~&~qb_{n+1}+rb_n~&~rb_{n+1}~\\ ~b_{n+1}~&~qb_n+rb_{n-1}~&~rb_n~\\ ~b_n~&~qb_{n-1}+rb_{n-2}~&~rb_{n-1}~ \end{array}\right]=\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right]\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n=AQ^n \label{3.1} \end{equation}

證明: 由定理 6, \begin{eqnarray*} ~\hskip 2cm &&\hskip -25pt \left[\begin{array}{ccc} ~b_{n+2}~&~qb_{n+1}+rb_n~&~rb_{n+1}~\\ ~b_{n+1}~&~qb_n+rb_{n-1}~&~rb_n~\\ ~b_n~&~qb_{n-1}+rb_{n-2}~&~rb_{n-1}~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right]\left[\begin{array}{ccc} ~a_n~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right]\cdot a\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n\\ &=&\left[\begin{array}{ccc} ~c~&~qb+ra~&~rb~\\ ~b~&~c-pb~&~ra~\\ ~a~&~b-pa~&~c-qa-pb~ \end{array}\right]\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n=AQ^n.\hskip 2.8cm \tag*{$\Box$} \end{eqnarray*}

[註]: 第二節中提到的 $\{a_n\}$ 也適用於定理 7, 因此定理 7 可適用於任何初始值 $b_0\not=0$ 的常係數三次遞迴數列 $\{b_n\}$。 實際上, 若 $b_0=0$, 只要構造一個新的數列 $c_n=b_{n+k}$ 使得 $c_0=b_k\not=0$, 則定理 7 就可以適用於 $\{c_n\}$, 之後只要再換回 $\{b_n\}$ 即可。

例: 若數列 $\{h_n\}$ 滿足 $$h_{n+3}=h_{n+2}+h_{n+1}+h_n,\ h_0=0,\ h_1=h_2=1,$$ 我們可以令 $\hat h_n=h_{n-1}$, 則 $\hat h_0=\hat h_1=1$, $\hat h_{-1}=0$, 定理 7 就可以應用在 $\{\hat h_{n}\}$ 上, 之後在用 $\hat h_n=h_{n-1}$ 換回 $\{h_n\}$。

定理8. 對任意整數 $n$, $$\det\left(\begin{array}{ccc} ~b_n~&~b_{n+1}~&~b_{n+2}~\\ ~b_{n-1}~&~b_n~&~b_{n+1}~\\ ~b_{n-2}~&~b_{n-1}~&~b_n~ \end{array}\right)=\det\left(\begin{array}{ccc} ~b_1~&~b_{2}~&~b_{3}~\\ ~b_{0}~&~b_1~&~b_{2}~\\ ~b_{-1}~&~b_{0}~&~b_1~ \end{array}\right)r^{n-1}.$$

證明: 對 \eqref{3.1} 取行列式可得 $$\det\left(\begin{array}{ccc} ~b_{n+2}~&~qb_{n+1}+rb_n~&~rb_{n+1}~\\ ~b_{n+1}~&~qb_n+rb_{n-1}~&~rb_{n}~\\ ~b_{n}~&~qb_{n-1}+rb_{n-2}~&~rb_{n-1}~ \end{array}\right)=(\det A)r^n,$$ 等式左邊可改寫為 \begin{eqnarray*} \det\left(\begin{array}{ccc} ~b_{n+2}~&~qb_{n+1}+rb_n~&~rb_{n+1}~\\ ~b_{n+1}~&~qb_n+rb_{n-1}~&~rb_{n}~\\ ~b_{n}~&~qb_{n-1}+rb_{n-2}~&~rb_{n-1}~ \end{array}\right)&=&\det\left(\begin{array}{ccc} ~b_{n+2}~&~rb_n~&~rb_{n+1}~\\ ~b_{n+1}~&~rb_{n-1}~&~rb_{n}~\\ ~b_{n}~&~rb_{n-2}~&~rb_{n-1}~ \end{array}\right)\\ &=&r^2\det\left(\begin{array}{ccc} ~b_{n+2}~&~b_n~&~b_{n+1}~\\ ~b_{n+1}~&~b_{n-1}~&~b_{n}~\\ ~b_{n}~&~rb_{n-2}~&~b_{n-1}~ \end{array}\right). \end{eqnarray*} 第二行與第一行對調, 第三行再與第二行對調可得 $$\det\left(\begin{array}{ccc} ~b_{n+2}~&~qb_{n+1}+rb_n~&~rb_{n+1}~\\ ~b_{n+1}~&~qb_n+rb_{n-1}~&~rb_{n}~\\ ~b_{n}~&~qb_{n-1}+rb_{n-2}~&~rb_{n-1}~ \end{array}\right)=r^2\det\left(\begin{array}{ccc} ~b_{n}~&~b_{n+1}~&~b_{n+2}~\\ ~b_{n-1}~&~b_{n}~&~b_{n+1}~\\ ~b_{n-2}~&~rb_{n-1}~&~b_{n}~ \end{array}\right).$$ 而等式右邊中 \begin{eqnarray*} \det(A)&=&\det\left(\begin{array}{ccc} ~b_{2}~&~b_3-pb_2~&~rb_{1}~\\ ~b_{1}~&~b_2-pb_1~&~rb_{0}~\\ ~b_{0}~&~b_{1}-pb_0~&~rb_{-1}~ \end{array}\right)=r\det\left(\begin{array}{ccc} ~b_{2}~&~b_3-pb_2~&~b_{1}~\\ ~b_{1}~&~b_2-pb_1~&~b_{0}~\\ ~b_{0}~&~b_{1}-pb_0~&~b_{-1}~ \end{array}\right)\\ &=&r\det\left(\begin{array}{ccc} ~b_{2}~&~b_3~&~b_{1}~\\ ~b_{1}~&~b_2~&~b_{0}~\\ ~b_{0}~&~b_1~&~b_{-1}~ \end{array}\right) \end{eqnarray*} 第三行與第二行對調, 第二行在再與第一行對調可得 $$\det(A)=r\det\left(\begin{array}{ccc} ~b_{1}~&~b_2~&~b_{3}~\\ ~b_{0}~&~b_1~&~b_{2}~\\ ~b_{-1}~&~b_0~&~b_{1}~ \end{array}\right) \hbox{。}$$ 故 $$r^2\det\left(\begin{array}{ccc} ~b_{n}~&~b_{n+1}~&~b_{n+2}~\\ ~b_{n-1}~&~b_n~&~b_{n+1}~\\ ~b_{n-2}~&~b_{n-1}~&~b_{n}~ \end{array}\right)=r\det\left(\begin{array}{ccc} ~b_{1}~&~b_2~&~b_{3}~\\ ~b_{0}~&~b_1~&~b_{2}~\\ ~b_{-1}~&~b_0~&~b_{1}~ \end{array}\right)\cdot r^n,$$ 即 $$\det\left(\begin{array}{ccc} ~b_{n}~&~b_{n+1}~&~b_{n+2}~\\ ~b_{n-1}~&~b_n~&~b_{n+1}~\\ ~b_{n-2}~&~b_{n-1}~&~b_{n}~ \end{array}\right)=\det\left(\begin{array}{ccc} ~b_{1}~&~b_2~&~b_{3}~\\ ~b_{0}~&~b_1~&~b_{2}~\\ ~b_{-1}~&~b_0~&~b_{1}~ \end{array}\right)\cdot r^{n-1}.\tag*{$\Box$}$$

定理9. 對任意整數 $m$ 及 $n$, $$b_{m+n}=\frac 1a[b_ma_n+qb_{m-1}a_{n-1}+r(b_{m-2}a_{n-1}+b_{m-1}a_{n-2})].$$

證明: 由 \eqref{3.1} 知 $$AQ^{m+n}=\left[\begin{array}{ccc} ~b_{m+n+2}~&~qb_{m+n+1}+rb_{m+n}~&~rb_{m+n+1}~\\ ~b_{m+n+1}~&~qb_{m+n}+rb_{m+n-1}~&~rb_{m+n}~\\ ~b_{m+n}~&~qb_{m+n-1}+rb_{m+n-2}~&~rb_{m+n-1}~ \end{array}\right].$$ 再一次由 \eqref{3.1} 及 \eqref{2.1}, 上式左方可寫成 \begin{eqnarray*} AQ^{m+n}&=&(AQ^m)Q^n\\ &=&\left[\begin{array}{ccc} ~b_{m+2}~&~qb_{m+1}+rb_{m}~&~rb_{m+1}~\\ ~b_{m+1}~&~qb_{m}+rb_{m-1}~&~rb_{m}~\\ ~b_{m}~&~qb_{m-1}+rb_{m-2}~&~rb_{m-1}~ \end{array}\right] \frac 1a\left[\begin{array}{ccc} ~a_{n}~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{ccc} ~b_{m+2}~&~qb_{m+1}+rb_{m}~&~rb_{m+1}~\\ ~b_{m+1}~&~qb_{m}+rb_{m-1}~&~rb_{m}~\\ ~b_{m}~&~qb_{m-1}+rb_{m-2}~&~rb_{m-1}~ \end{array}\right] \left[\begin{array}{ccc} ~a_{n}~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right]. \end{eqnarray*} 亦即\begin{eqnarray*} &&\hskip -25pt \left[\begin{array}{ccc} ~b_{m+n+2}~&~qb_{m+n+1}+rb_{m+n}~&~rb_{m+n+1}~\\ ~b_{m+n+1}~&~qb_{m+n}+rb_{m+n-1}~&~rb_{m+n}~\\ ~b_{m+n}~&~qb_{m+n-1}+rb_{m+n-2}~&~rb_{m+n-1}~ \end{array}\right]\\ &=&\frac 1a\left[\begin{array}{ccc} ~b_{m+2}~&~qb_{m+1}+rb_{m}~&~rb_{m+1}~\\ ~b_{m+1}~&~qb_{m}+rb_{m-1}~&~rb_{m}~\\ ~b_{m}~&~qb_{m-1}+rb_{m-2}~&~rb_{m-1}~ \end{array}\right] \left[\begin{array}{ccc} ~a_{n}~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right].\end{eqnarray*} 比較等式兩邊矩陣 (3,1) 元素可得 $$b_{m+n}=\frac 1a[b_ma_n+qb_{m-1}a_{n-1}+r(b_{m-2}a_{n-1}+b_{m-1}a_{n-2})].\tag*{$\Box$}$$

假設 $\alpha,\beta,\gamma$ 為 $Q$ 的特徵值, $V(\alpha,\beta,\gamma)$ 為 $\alpha,\beta\gamma$ 的 Vandermonde 矩陣 $$\left[\begin{array}{ccc} ~\alpha^2~&~\beta^2~&~\gamma^2~\\ ~\alpha~&~\beta~&~\gamma~\\ ~1~&~1~&~1~ \end{array}\right].$$ Chen 和 Louck 給出了以下等式 $$Q^nV(\alpha,\beta,\gamma)=V(\alpha,\beta,\gamma)D(\alpha^n,\beta^n,\gamma^n)$$ 其中 $D(\alpha^n,\beta^n,\gamma^n)$ 為對角矩陣。將上式完整寫出來, 我們可以得到 $$\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n\left[\begin{array}{ccc} \alpha^2&\beta^2&\gamma^2\\ \alpha&\beta&\gamma\\ 1&1&1 \end{array}\right]=\left[\begin{array}{ccc} \alpha^2&\beta^2&\gamma^2\\ \alpha&\beta&\gamma\\ 1&1&1 \end{array}\right]\left[\begin{array}{ccc} \alpha^n&0&0\\ 0&\beta^n&0\\ 0&0&\gamma^n \end{array}\right]=\left[\begin{array}{ccc} \alpha^{n+2}&\beta^{n+2}&\gamma^{n+2}\\ \alpha^{n+1}&\beta^{n+1}&\gamma^{n+1}\\ \alpha^{n}&\beta^{n}&\gamma^{n} \end{array}\right].$$ 這個等式提供我們一個將具有三個相異特徵值的 3 階遞迴式的一般式用矩陣表示出來的方法。

定理10. 令 $\{a_n\}$ 滿足遞迴式 $a_{n+3}=pa_{n+2}+qa_{n+1}+ra_{n},$ 其初始條件為 $a_{-2}=a_{-1}=0$, $a_0=a\not=0$。 若 $Q$ 具有三個相異的特徵值, 則 $$a_n=-a\Big[\frac{\alpha^{n+2}(\beta-\gamma)+\beta^{n+2}(\gamma-\alpha)+\gamma^{n+2}(\alpha-\beta)}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)}\Big].$$

證明: 因為 $\alpha,\beta,\gamma$ 相異, $V(\alpha,\beta,\gamma)$ 為可逆矩陣, 則 $Q^n$ 可被 $V(\alpha,\beta,\gamma)$ 對角化, 即 $$\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n=\left[\begin{array}{ccc} ~\alpha^2~&~\beta^2~&~\gamma^2~\\ ~\alpha~&~\beta~&~\gamma~\\ ~1~&~1~&~1~ \end{array}\right]\left[\begin{array}{ccc} ~\alpha^n~&~0~&~0~\\ ~0~&~\beta^n~&~0~\\ ~0~&~0~&~\gamma^n~ \end{array}\right]\left[\begin{array}{ccc} ~\alpha^2~&~\beta^2~&~\gamma^2~\\ ~\alpha~&~\beta~&~\gamma~\\ ~1~&~1~&~1~ \end{array}\right]^{-1}.$$ 直接計算可知 $$V(\alpha,\beta,\gamma)^{-1}=\frac{-1}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)}\left[\begin{array}{ccc} ~\beta-\gamma~&~\gamma^2-\beta^2~&~\beta\gamma(\beta-\gamma)~\\ ~\gamma-\alpha~&~\alpha^2-\gamma^2~&~\gamma\alpha(\gamma-\alpha)~\\ ~\alpha-\beta~&~\beta^2-\alpha^2~&~\alpha\beta(\alpha-\beta)~ \end{array}\right].$$ 於是由 \eqref{2.1}, \begin{eqnarray*} &&\hskip -15pt \left[\begin{array}{ccc} ~a_{n}~&~qa_{n-1}+ra_{n-2}~&~ra_{n-1}~\\ ~a_{n-1}~&~qa_{n-2}+ra_{n-3}~&~ra_{n-2}~\\ ~a_{n-2}~&~qa_{n-3}+ra_{n-4}~&~ra_{n-3}~ \end{array}\right]=a\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n\\ &=&\frac{-a}{(\alpha\!-\!\beta)(\beta\!-\!\gamma)(\gamma\!-\!\alpha)} \left[\begin{array}{ccc} ~\alpha^{n+2}~&~\beta^{n+2}~&~\gamma^{n+2}~\\ ~\alpha^{n+1}~&~\beta^{n+1}~&~\gamma^{n+1}~\\ ~\alpha^{n}~&~\beta^{n}~&~\gamma^{n}~ \end{array}\right]\left[\begin{array}{ccc} ~\beta\!-\!\gamma~&~\gamma^2\!-\!\beta^2~&~\beta\gamma(\beta\!-\!\gamma)~\\ ~\gamma\!-\!\alpha~&~\alpha^2\!-\!\gamma^2~&~\gamma\alpha(\gamma\!-\!\alpha)~\\ ~\alpha\!-\!\beta~&~\beta^2\!-\!\alpha^2~&~\alpha\beta(\alpha\!-\!\beta)~ \end{array}\right] \end{eqnarray*} 比較等式兩邊矩陣 (1,1) 的元素可得 $$a_n=-a\Big[\frac{\alpha^{n+2}(\beta-\gamma)+\beta^{n+2}(\gamma-\alpha)+\gamma^{n+2}(\alpha-\beta)}{(\alpha-\beta)(\beta-\gamma)(\gamma-\alpha)}\Big].\tag*{$\Box$}$$

[註]: 定理10的結果一般都用 $\{a_n\}$ 的特徵方程式來處理。

藉由將定理10證明中最後得到的矩陣乘上 $A$, 我們可以將定理 10 的 $\{a_n\}$ 擴展到一般的三階遞迴數列 $\{b_n\}$。

推論11. \begin{eqnarray*} &&\hskip -15pt \left[\begin{array}{ccc} ~b_{n+2}~&~qb_{n+1}+rb_{n}~&~rb_{n+1}~\\ ~b_{n+1}~&~qb_{n}+rb_{n-1}~&~rb_{n}~\\ ~b_{n}~&~qb_{n-1}+rb_{n-2}~&~rb_{n-1}~ \end{array}\right]\\ &=&\frac{-1}{(\alpha\!-\!\beta)(\beta\!-\!\gamma)(\gamma\!-\!\alpha)}A \left[\begin{array}{ccc} ~\alpha^{n+2}~&~\beta^{n+2}~&~\gamma^{n+2}~\\ ~\alpha^{n+1}~&~\beta^{n+1}~&~\gamma^{n+1}~\\ ~\alpha^{n}~&~\beta^{n}~&~\gamma^{n}~ \end{array}\right]\left[\begin{array}{ccc} ~\beta\!-\!\gamma~&~\gamma^2\!-\!\beta^2~&~\beta\gamma(\beta\!-\!\gamma)~\\ ~\gamma\!-\!\alpha~&~\alpha^2\!-\!\gamma^2~&~\gamma\alpha(\gamma\!-\!\alpha)~\\ ~\alpha\!-\!\beta~&~\beta^2\!-\!\alpha^2~&~\alpha\beta(\alpha\!-\!\beta)~ \end{array}\right]. \end{eqnarray*} 在第二節曾提過, 前面得到的一些恆等式可與二階遞迴數列的情況做對應, 現在我們將其列出, 茲比較如下:

三階遞迴數列二階遞迴數列
$\left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n$
$=\dfrac 1a \left[\begin{array}{ccc} a_{n}&qa_{n-1}+ra_{n-2}&ra_{n-1}\\ a_{n-1}&qa_{n-2}+ra_{n-3}&ra_{n-2}\\ a_{n-2}&qa_{n-3}+ra_{n-4}&ra_{n-3} \end{array}\right]$
$\left[\begin{array}{cc} ~c~&~d~\\ ~1~&~0~ \end{array}\right]$
$=\dfrac 1a\left[\begin{array}{cc} ~x_n~&~x_{n+1}~\\ ~x_{n-1}~&~dx_{n-2}~ \end{array}\right]$
$\det\left(\begin{array}{ccc} ~a_{n}~&~a_{n+1}~&~a_{n+2}~\\ ~a_{n-1}~&~a_{n}~&~a_{n+1}~\\ ~a_{n-2}~&~a_{n-1}~&~a_{n}~ \end{array}\right)=a^3r^n$ $\det\left(\begin{array}{cc} ~x_n~&~x_{n+1}~\\ ~x_{n-1}~&~x_n~ \end{array}\right)=a^2(-d)^n$
$a_{m+n}\!=\!\frac 1a[a_ma_n\!+\!qa_{n-1}a_{m-1}$
$\!+\!r(a_{n-2}a_{m-1}\!+\!a_{n-1}a_{m-2})]$
$x_{m+n}\!=\!\frac 1a(x_nx_m+dx_{n-1}x_{m-1})$
$\left[\begin{array}{c} b_{n+2}\\ b_{n+1}\\ b_{n} \end{array}\right]=\dfrac 1a \left[\begin{array}{ccc} ~c~&qb+ra&rb\\ b&c-pb&ra~\\ a&b-pa&c\!-\!qa\!-\!pb \end{array}\right]\left[\begin{array}{c} a_{n}\\ a_{n-1}\\ a_{n-2} \end{array}\right]$ $\left[\begin{array}{c} y_{n+1}\\ y_n \end{array}\right]=\dfrac 1a\left[\begin{array}{cc} ~b~&ra\\ ~a~&b\!-\!ca \end{array}\right]\left[\begin{array}{c} x_{n}\\ x_{n-1} \end{array}\right]$
$\left[\begin{array}{ccc} b_{n+2}&qb_{n+1}+rb_n&rb_{n+1}\\ b_{n+1}&qb_n+rb_{n-1}&rb_{n}\\ b_{n}&qb_{n-1}+rb_{n-2}&rb_{n-1} \end{array}\right]$
$=\left[\begin{array}{ccc} c&qb+ra&rb\\ b&c-pb&ra\\ a&b-pa&c\!-\!qa\!-\!pb \end{array}\right] \left[\begin{array}{ccc} ~p~&~q~&~r~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right]^n$
$\left[\begin{array}{cc} y_{n+1}&dy_n\\ y_n&dy_{n-1} \end{array}\right]\!\!=\!\!\left[\begin{array}{cc} ~b~&ad\\ ~a~&b\!-\!ca \end{array}\right]\left[\begin{array}{cc} c&d\\ 1&0 \end{array}\right]^n$
$\left|\begin{array}{ccc} b_{n}&b_{n+1}&b_{n+2}\\ b_{n-1}&b_n&b_{n+1}\\ b_{n-2}&b_{n-1}&b_{n} \end{array}\right|=\left|\begin{array}{ccc} b_{1}&b_2&b_{3}\\ b_{0}&b_1&b_{2}\\ b_{-1}&b_0&b_{1} \end{array}\right|r^{n-1}$ $\left|\begin{array}{cc} y_n&y_{n+1}\\ y_{n-1}&y_n \end{array}\right|=\left|\begin{array}{cc} y_1&y_2\\ y_0&y_1 \end{array}\right|(-d)^{n-1}$

四、Padovan 數列及其他數列

這一節中, 我們將用第二節及第三節中的工具並利用 Cayley-Hamilton 定理來導出一些 Padovan 數列的性質, 這些性質中有些是 的推廣, 有些是我們新的結果。

[註]: 注意到此節中關於 Padovan 數列的討論, 我們得到的所有等式的做法皆可以應用在 Perrin 數 (見 ) 上, 因為 Perrin 數 $\{R_n\}$ 滿足遞迴關係 $$R_{n+3}=R_{n+1}+R_n,\quad R_0=3,\ R_1=0,\ R_2=2,$$ 只有初始值與 Padovan 數列不同, 但有相同的遞迴式。

關於 Padovan 數列及 Perrin 數近年已有一些結果: Yilmaz 及 Bozkurt , 利用 Hessenbergs 矩陣的 permanent 將 Perrin 數及 Padovan 數列表示出來並做出一些與 Padovan 數列有關的新結果; Leonard 及 Liu 用生成函數求得 Perrin 數的封閉表達式並用基礎的方法得到一個 Perrin 數的數論性質。 我們雖然也是用矩陣方法處理 Padovan 數列, 但方向與 Yilmaz 及 Bozkurt 不同, 因此得到的結果也不一樣。

首先, 我們先介紹一些 Padovan 數列已知的結果 :

  1. $P_{n+5}=P_{n+4}+P_n,$
  2. $P_{n+5}-2=\sum\limits_{k=0}^n P_k=P_0+P_1+\cdots+P_n$,
  3. $P_{2n+3}-1=\sum\limits_{k=0}^n P_{2k}=P_0+P_2+\cdots+P_{2n}$,
  4. $P_{2n+4}-1=\sum\limits_{k=0}^n P_{2k+1}=P_1+P_3+\cdots+P_{2n+1}$,
  5. $P_{3n+2}=\sum\limits_{k=0}^n P_{3k}=P_0+P_3+\cdots+P_{3n}$,
  6. $P_{3n+3}-1=\sum\limits_{k=0}^n P_{3k+1}=P_1+P_4+\cdots+P_{3n+1}$,
  7. $P_{3n+4}-1=\sum\limits_{k=0}^n P_{3k+2}=P_2+P_5+\cdots+P_{3n+2}$,
  8. $P_{5n+1}=\sum\limits_{k=0}^n P_{5k}$,

Padovan 數列對應的 $Q$ 及 $A$ 為 $$Q=\left[\begin{array}{ccc} ~0~&~1~&~1~\\ ~1~&~0~&~0~\\ ~0~&~1~&~0~ \end{array}\right],\quad A=\left[\begin{array}{ccc} ~1~&~2~&~1~\\ ~1~&~1~&~1~\\ ~1~&~1~&~0~ \end{array}\right],$$ 特別地在這一節裡 Padovan 數列的 $A=Q^4$。 因 $Q$ 的特徵多項式為 $$x^3-x-1=0$$ 故由 Cayley-Hamilton 定理有 \begin{equation} Q^3=Q+I.\label{4.1} \end{equation} 稍微對 \eqref{4.1} 做些調整, 可以得到幾個與 \eqref{4.1} 等價的等式 \begin{eqnarray} I&=&Q(Q^2-I)=Q(Q+I)(Q-I),\label{4.2}\\ &=&Q(Q^3(Q-I))=Q^4(Q-I))=Q^4(Q-I)=Q^5-Q^4.\label{4.3} \end{eqnarray} 由 \eqref{4.3} 知 $Q^5=Q^4+I$, 等式兩邊同乘上 $AQ^n$ 得 $$AQ^{n+5}=AQ^{n+4}+AQ^n.$$ 利用 \eqref{3.1}, 並比較等式兩邊矩陣 (3,1) 的元素可得 $$P_{n+5}=P_{n+4}+P_n$$ 於是我們得到了前面提過的已知結果(a)$-\{P_n\}$ 的另一遞迴關係。

定理12. 對任意整數 $n$, $$P_{n+5}=P_{n+4}+P_n.$$

定理13. 對任意整數 $n$, $$\det\left(\begin{array}{ccc} P_n&~P_{n+1}~&~P_{n+2}~\\ ~P_{n-1}~&P_{n}&P_{n+1}\\ ~P_{n-2}~&P_{n-1}&P_{n} \end{array}\right)=1.$$

證明: 因為 $\det A=1$, 由定理 8 可得 $$\det\left(\begin{array}{ccc} P_n&~P_{n+1}~&~P_{n+2}~\\ ~P_{n-1}~&P_{n}&P_{n+1}\\ ~P_{n-2}~&P_{n-1}&P_{n} \end{array}\right)=\det(A)\cdot 1^{n-1}=1.\tag*{$\Box$}$$

定理14. 對任意整數 $m$ 及 $n$ $$P_{m+n+5}=P_{m+2}P_{n+1}+P_{m+1}P_{n+2}+P_mP_n.$$

證明: 由 \eqref{3.1}, 對所有整數 $k$ 都有 $$AQ^k=\left[\begin{array}{ccc} P_{k+2}&~P_{k+1}+P_k~&~P_{k+1}~\\ ~P_{k+1}~&P_{k}+P_{k-1}&P_{k}\\ ~P_{k}~&P_{k-1}+P_{k-2}&P_{k-1} \end{array}\right]=\left[\begin{array}{ccc} P_{k+2}&~P_{k+3}~&~P_{k+1}~\\ ~P_{k+1}~&P_{k+2}&P_{k}\\ ~P_{k}~&P_{k+1}&P_{k-1} \end{array}\right]$$ 則 \begin{eqnarray*} AQ^{m+n+4}&=&A^2Q^{m+n}=(AQ^m)(AQ^n)\\ &=&\left[\begin{array}{ccc} P_{m+2}&~P_{m+3}~&~P_{m+1}~\\ ~P_{m+1}~&P_{m+2}&P_{m}\\ ~P_{m}~&P_{m+1}&P_{m-1} \end{array}\right]\left[\begin{array}{ccc} P_{n+2}&~P_{n+3}~&~P_{n+1}~\\ ~P_{n+1}~&P_{n+2}&P_{n}\\ ~P_{n}~&P_{n+1}&P_{n-1} \end{array}\right]. \end{eqnarray*} 另一方面 $$AQ^{m+n+4}=\left[\begin{array}{ccc} P_{m+n+6}&~P_{m+n+7}~&~P_{m+n+5}~\\ ~P_{m+n+5}~&P_{m+n+6}&P_{m+n+4}\\ ~P_{m+n+4}~&P_{m+n+5}&P_{m+n+3} \end{array}\right].$$ 比較矩陣 (2,1)的元素可得待證等式。 $\tag*{$\Box$}$

定理15. 對任意正整數 $n$ 及整數 $r$, $$P_r=\sum_{k=0}^n (-1)^{n-k}{n\choose k}P_{n+r+2k}.$$

證明: 由 \eqref{4.2} $$I=I^n=Q^n(Q^2-I)^n=\sum_{k=0}^n(-1)^{n-k}{n\choose k}Q^{n+2k}.$$ 等式兩邊同乘 $AQ^r$ 可得 $$AQ^r=\sum_{k=0}^n(-1)^{n-k}{n\choose k}AQ^{n+r+2k}.$$ 利用 \eqref{3.1} 改寫上式, 並比較等式兩邊矩陣的(3,1)元素可得 $$P_r=\sum_{k=0}^n (-1)^{n-k}{n\choose k}P_{n+r+2k}.\tag*{$\Box$}$$

定理16. 對任意正整數 $n$ 及整數 $r$, $$P_r=\sum_{k=0}^n (-1)^{n-k}{n\choose k}P_{4n+r+k}.$$

證明: 由 \eqref{4.3} $$I=Q^{4n}(Q-I)^n=\sum_{k=0}^n(-1)^{n-k}{n\choose k}Q^{4n+k}.$$ 等式兩邊同乘 $AQ^r$ 可得 $$AQ^r=AQ^{4n+r}(Q-I)^n=\sum_{k=0}^n(-1)^{n-k}{n\choose k}AQ^{4n+r+k}.$$ 利用 \eqref{3.1} 改寫上式, 並比較等式兩邊矩陣的(3,1)元素可得 $$P_r=\sum_{k=0}^n (-1)^{n-k}{n\choose k}P_{4n+r+k}.\tag*{$\Box$}$$ 定理15及定理16中, 分別令 $r=0$, 我們可以得到以下推論:

推論17.

(a) $\sum\limits_{k=0}^n (-1)^{n-k}\displaystyle{n\choose k}P_{n+2k}=1$,

(b) $\sum\limits_{k=0}^n (-1)^{n-k}\displaystyle{n\choose k}P_{4n+k}=1$.

定理18. 對任意正整數 $n$ 及整數 $l$ 和 $r$, $$P_{(l+3)n+r}=\sum_{k=0}^n (-1)^{n-k}{n\choose k}P_{ln+r+k}.$$

證明: 在 \eqref{4.1} 的等式兩邊同乘 $Q^l$ 可得 $$Q^{l+3}=Q^{l+1}+Q^l.$$ 兩邊同取 $n$ 次方, 則 $$Q^{(l+3)n}=(Q^{l+1}+Q^l)^n=Q^{ln}(Q+I)^n =Q^{ln}\sum_{k=0}^n{n\choose k}Q^k=\sum_{k=0}^n{n\choose k}Q^{ln+k}.$$ 兩邊再同乘 $AQ^r$ 並將 \eqref{4.1} 代入, 比較兩邊矩陣的 (3,1) 元素即得證。 $\tag*{$\Box$}$

定理19. 對任意正整數 $n$ 及整數 $l$ 和 $r$, $$P_{(l+5)n+r}=\sum_{k=0}^n{n\choose k}P_{ln+r+4k}.$$

證明: 由 \eqref{4.3} 有 $Q^5=Q^4+I$, 剩下的步驟與定理 16 類似, 故省略。

定理20. 對任意正整數 $n$ 及整數 $r$ $$P_{n+r+5}-P_{r+4}=\sum_{k=0}^n P_{r+k}.$$

證明: 考慮 $(Q-I)^{-1}(Q^{n+1}-I)=Q^n+Q^{n+1}-I)=Q^n+Q^{n-1}+\cdots+I$。 由 \eqref{4.2} 及 \eqref{4.1} 可知 $(Q-I)^{-1}=Q(Q+I)=Q^4$, 代入上式得 $$Q^{n+5}-Q^4=Q^n+Q^{n-1}+\cdots+I.$$ 兩邊同乘 $AQ^r$ 後將 \eqref{3.1} 代入, 比較兩邊矩陣的 (3,1) 元素即得證。 $\tag*{$\Box$}$

定理20中令 $r=0$, 就可以得到 Padovan 數列的性質(b)。

定理21. 對任意正整數 $n$ 及整數 $r$ $$P_{2n+r+3}-P_{r+1}=\sum_{k=0}^n P_{r+2k}.$$

證明: 考慮 $(Q^2-I)^{-1}(Q^{2(n+1)}-I)=Q^{2n}+Q^{2(n-1)}+\cdots+Q^2+I$。 由 \eqref{4.2} 顯然有 $(Q^2-I)^{-1}=Q$, 從而 $$Q^{2n+3}-Q=Q^{2n}+Q^{2(n-1)}+\cdots+I.$$ 兩邊同乘 $AQ^r$ 後, 用與定理18同樣的做法及得證。

定理21中, 若令 $r\!=\!0$ 及 $r\!=\!1$, 分別可以得到 Padovan 數列的性質 (c) 及 (d)。 $\tag*{$\Box$}$

定理22. 對任意正整數 $n$ 及整數 $r$ $$P_{3n+r+2}-P_{r-1}=\sum_{k=0}^n P_{r+3k}.$$

證明: 考慮 $(Q^3-I)^{-1}(Q^{3(n+1)}-I)=Q^{3n}+Q^{3(n-1)}+\cdots+Q^3+I$。 由 \eqref{4.1} 顯然有 $(Q^3-I)^{-1}=Q^{-1}$。 接下來用與證定理 18 類似的方法即可得證。 $\tag*{$\Box$}$

定理22中, 若令 $r\!=\!0$、$r\!=\!1$ 及 $r\!=\!2$, 分別可以得到 Padovan 數列的性質 (e)、 (f) 及 (g)。

定理23. 對任意正整數 $n$ 及整數 $r$ $$P_{5n+r+1}-P_{r-4}=\sum_{k=0}^n P_{r+5k}.$$

證明: 考慮 $(Q^5-I)^{-1}(Q^{5(n+1)}-I)=Q^{5n}+Q^{5(n-1)}+\cdots+Q^5+I$。 由 \eqref{4.3} 顯然有 $(Q^5-I)=Q^{-4}$。 接下來用與證定理18類似的方法即可得證。 $\tag*{$\Box$}$

定理 23 中, 若令 即可得 Padovan 數列的性質 (h)。

致謝

感謝中研院數學所暑期組合數學與圖論專題提供機會, 讓筆者能在暑假跟隨美國內華達大學數學系薛昭雄教授做暑期研究, 也由衷感謝薛昭雄教授的指導及鼓勵, 因為薛教授適時的鼓勵及建議本文才能完稿。

參考文獻

P. Barry, Symmetric third-order recurring sequences, Chebyshev polynomials, and Riordan array, J. Integer Sequences 12(2009), Article 09.8.6. William Y. C. Chen, J. D. Louck, The combinatorial power of the companion matrix, Linear Algebra Appl. 232(1996), pp.261-278. L. Comtet, Advanced Combinatorics, D. Reidel, Dordrecht, 1974. J. Feng, More identities on the Tribonacci numbers, Ars Combinatoria 100(2011), pp.73-78. H. W. Gould, A history of the Fibonacci Q-matrix and a higher-dimensional problem, The Fibonacci Quarterly 19(1981), No.3, pp.250-257. K. Hoffman and R. Kunze, Linear Algebra (2nd edition), Prentice-Hall, Inc. , Englewood Cliffs, New Jersey, 1961. T. Koshy, Fibonacci matrices, In: Fibonacci and Lucas Numbers with Applications, John Wiley & Sons, Inc. , New York, 2001, pp.362-386. I. E. Leonard, A. C. F. Liu, A familiar recurrence occurs again, Amer. Math. Monthly, 119(2012), pp.333-336. A. G. Shannon, A.F. Horadam, Some properties of third-order recurrence relations, The Fibonacci Quarterly 10(1972), No.2, pp.135-146. M. E. Waddill, Using matrix techniques to establish properties of a generalized Tribonacci sequence, In: Application of Fibonnaci Numbers, Vol 4, G.E. Bergun etal, Eds., Kluwer Acad. Publishers, Holland, 1993, pp.299-308. http://en.wikipedia.org/wiki/Padovan_sequence F. Yilmaz, D. Bozkurt, Hessenberg matrices and the Pell and Perrin numbers, J. Number Theory, 131 (2011), pp.1390-1396. F. Yilmaz, D. Bozkurt, Some properties of Padovan sequence by matrix method, Ars Combinatoria, 104 (2012), pp.149-160. 林鈺傑, Fibonacci Q-Matrix 在遞迴數列上的延伸和其應用, 數學傳播 36 卷第二期(2012), pp.52-63.

---本文作者為交通大學應用數學系學生---