數學傳播

一、前言

義大利數學家 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)。

致謝

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

參考文獻

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