一、動機：

定義費氏數列 $\langle F_n\rangle$： $F_0=0$, $F_1=1$, 且滿足遞迴關係式 $F_{n+2}=F_{n+1}+F_n$, 其中 $n=1,2,\ldots$。

對於費氏數列, 從 $F_8=F_7+F_6$ 出發, 簡單地反覆代換, 可得 \begin{eqnarray*} F_8&=&F_7+F_6=(F_6+F_5)+F_6=2F_6+F_5\\ &=&2(F_5+F_4)+F_5=3F_5+2F_4\\ &=&3(F_4+F_3)+2F_4=5F_4+3F_3 \end{eqnarray*}

至此, 得到一個遞迴關係式： $F_8-5F_4-3F_3=0$, 先將這樣的關係式, 稱為由 $F_{n+2}-F_{n+1}-F_n=0$ 導出的 「線性衍生遞迴式」(在接下來的探討中, 會給出更正式的定義)。

類似地, 從 $F_n=F_{n-1}+F_{n-2}$ (其中 $n\in N$ 且 $n\ge 5$)出發, 如上同樣地反覆代換, 可得 $F_n-5F_{n-4}-3F_{n-5}=0$。 以此角度而言, $F_8-5F_4-3F_3=0$ 和 $F_9-5F_5-3F_4=0$ 有著同樣的結構。

眾所周知, $F_{n+2}-F_{n+1}-F_n=0$ 所對應的特徵方程式為 $x^2-x-1=0$。 而在這篇文章中, 定義 $F_8-5F_4-3F_3$ 所對應的 「特徵多項式」為 $x^8-5x^4-3x^3$。 由長除法, 可得 $x^8-5x^4-3x^3=(x^2-x-1)(x^6+x^5+2x^4+3x^3)$, 發現 $x^8-5x^4-3x^3$ 是 $x^2-x-1$ 的倍式！ 這是個巧合嗎? 其中的關聯性是什麼呢? 請讀者先行思考, 再看本文接下來的探討。

二、探討：

(一)定義：

1. 線性衍生遞迴式

設數列 $\langle a_n\rangle$ 滿足遞迴關係式： $a_n+ra_{n-1}+sa_{n-2}=0$, 其中 $n\in N$ 且 $n\ge 2$。 將形如 \begin{eqnarray*} &&\hskip -15pt \sum_{k=0}^{n-2}p_k(a_{n-k}+ra_{n-k-1}+sa_{n-k-2})\\ &=&p_0(a_n+ra_{n-1}+sa_{n-2})+p_1(a_{n-1}+ra_{n-2}+s_{n-3})+\cdots+p_{n-2}(a_2+ra_1+sa_0)=0 \end{eqnarray*} 的等式, 稱為由 $a_{n+2}+ra_{n+1}+sa_n=0$ 所導出的線性衍生遞迴式。

例： Fibonacci 數列 $\langle F_n\rangle$ 滿足遞迴關係式： $F_n-F_{n-1}-F_{n-2}=0$, 由於

1. $(F_n-F_{n-1}-F_{n-2})+1\cdot (F_{n-1}-F_{n-2}-F_{n-3})+2\cdot (F_{n-2}-F_{n-3}-F_{n-4})\\ +3\cdot (F_{n-3}-F_{n-4}-F_{n-5})=0$, 同類項合併得 $F_n-5F_{n-4}-3F_{n-5}=0$, 所以 $F_n-5F_{n-4}-3F_{n-5}=0$ 為由 $F_n-F_{n-1}-F_{n-2}=0$ 所導出的線性衍生遞迴式。 註： 讀者可以看出, 這是將「一、動機」之中提到的代換, 改成用「線性組合」的方式來表達。
2. 特徵多項式 給定一數列 $\langle a_n\rangle$, 定義 $r_ka_k+r_{k-1}a_{k-1}+\cdots+r_1a_1+r_0a_0$ 所對應的「特徵多項式」為 $$r_kx^k+r_{k-1}x^{k-1}+\cdots+r_1x+r_0\hbox{。}$$ 註： 即數列的下標, 恰對應 $x$ 的次方。 例： $a_9-5a_5-3a_4$ 所對應的特徵多項式為 $x^9-5x^5-3x^4$。
3. 數列中各項的線性組合 給定一數列 $\langle a_n\rangle$, 將形如 $r_ka_k+r_{k-1}a_{k-1}+\cdots+r_1a_1+r_0a_0$ 的式子, 稱為 $a_0,a_1,\ldots,a_k$ 的線性組合。
4. 數列的線性組合集合 給定一無窮數列 $\langle a_n\rangle$, 定義一集合 $$S=\{r_ka_k+r_{k-1}a_{k-1}+\cdots+r_1a_1+r_0a_0\mid r_0,r_1,\ldots,r_k\in Z\}$$ 為數列 $\langle a_n\rangle$ 的「線性組合集合」。
5. 特徵對應 規定一個對應 $\varphi$, 其規則為 $$\varphi:\ r_ka_k+r_{k-1}a_{k-1}+\cdots+r_1a_1+r_0a_0\ \to\ r_kx^k+r_{k-1}x^{k-1}+\cdots+r_1x+r_0,$$ 也可記為 $$\varphi(r_ka_k+r_{k-1}a_{k-1}+\cdots+r_1a_1+r_0a_0)=r_kx^k+r_{k-1}x^{k-1}+\cdots+r_1x+r_0,$$ 說明： $\varphi$ 是一個從「數列的線性組合集合」到「特徵多項式」的對應, 將 $\varphi$ 稱為「特徵對應」。 由定義易知 $\varphi$ 是一個一對一對應。

(二)性質：

由上述的定義, 得到以下的性質：設 $ P=p_ka_k+p_{k-1}a_{k-1}+\cdots+p_1a_1+p_0a_0$ 與 $ Q=q_ka_k+q_{k-1}a_{k-1}+\cdots+q_1a_1+q_0a_0 $ 皆為 $a_0,a_1,\ldots,a_k$ 的線性組合, 則有 $\varphi(\alpha P+\beta Q)=\alpha \cdot\varphi(P)+\beta\cdot \varphi(Q)$。

證明： \begin{eqnarray*} &&\hskip -15pt \varphi(\alpha P\!+\!\beta Q)\\ &=&\varphi[\alpha (p_ka_k\!+\!p_{k-1}a_{k-1}\!+\!\cdots\!+\!p_1a_1\!+\!p_0a_0)\!+\!\beta(q_ka_k\!+\!q_{k-1}a_{k-1}\!+\!\cdots\!+\!q_1a_1\!+\!q_0a_0)]\\[5pt] &=&\varphi[(\alpha p_k\!+\!\beta q_k)a_k\!+\!(\alpha p_{k-1}\!+\!\beta q_{k-1})a_{k-1}\!+\!\cdots\!+\!(\alpha p_1\!+\!\beta q_1)a_1\!+\!(\alpha p_0\!+\!\beta q_0)a_0]\\[5pt] &=&(\alpha p_k+\beta q_k)x^k+(\alpha p_{k-1}+\beta q_{k-1})x^{k-1}+\cdots+(\alpha p_1\!+\!\beta q_1)x+(\alpha p_0\!+\!\beta q_0)a_0\\[5pt] &=&\alpha (p_kx^k\!+\!p_{k-1}x^{k-1}\!+\!\cdots\!+\!p_1x\!+\!p_0)\!+\!\beta(q_kx^k\!+\!q_{k-1}x^{k-1}\!+\!\cdots\!+\!q_1x\!+\!q_0)\\[5pt] &=&\alpha \cdot \varphi(p_ka_k\!+\!p_{k-1}a_{k-1}\!+\!\cdots\!+\!p_1a_1\!+\!p_0a_0)\!+\!\beta\cdot\varphi(q_ka_k\!+\!q_{k-1}a_{k-1}\!+\!\cdots\!+\!q_1a_1\!+\!q_0a_0)\\[5pt] &=&\alpha \cdot \varphi(P)\!+\!\beta\cdot \varphi(Q). \end{eqnarray*}

註： 此性質表示 $\varphi$ 是「線性」(linear)。

(三)定理：

經過一番實驗與探索, 得到以下的定理：

線性衍生遞迴定理： 設數列 $\langle a_n\rangle$ 滿足遞迴關係式： $a_n+ra_{n-1}+sa_{n-2}=0$, 其中 $n\in N$ 且 $n\ge 2$, 且 $\sum\limits_{k=0}^{n-2} p_k(a_{n-k}+ra_{n-k-1}+s a_{n-k-2})=0$ 為由 $a_n+ra_{n-1}+sa_{n-2}=0$ 所導出的線性衍生遞迴式。 設將 $\sum\limits_{k=0}^{n-2} p_k(a_{n-k}+ra_{n-k-1}+s a_{n-k-2})=0$ 同類項合併之後, 所得等式為 $r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0=0$, 則 $r_nx^n+r_{n-1}x^{n-1}+\cdots+r_1x+r_0$ 必為 $x^2+rx+s$ 的倍式。

說明： 即由原遞迴式出發, 所導出的線性衍生遞迴式, 在同類項合併之後, 所對應的特徵多項式, 必為 $x^2+rx+s$ 的倍式。 此處的同類項合併, 是以 $a_k$ 的下標 $k$ 作分類。

證明： \begin{eqnarray*} &&\hskip -20pt r_nx^n+r_{n-1}x^{n-1}+\cdots+r_1x+r_0=\varphi(r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0)\\ &=&\varphi\Big[\sum_{k=0}^{n-2} p_k(a_{n-k}+ra_{n-k-1}+s a_{n-k-2})\Big]\\ &=&\sum_{k=0}^{n-2} [p_k\cdot\varphi(a_{n-k}+ra_{n-k-1}+s a_{n-k-2})]\qquad (\because\ \varphi\ \hbox{is linear)}\\ &=&\sum_{k=0}^{n-2} p_k(x^{n-k}+rx^{n-k-1}+sx^{n-k-2})\\ &=&\sum_{k=0}^{n-2} [p_kx^{n-k-2}\cdot(x^2+rx+s)]=(x^2+rx+s)\cdot\Big(\sum_{k=0}^m p_kx^{n-k-2}\Big), \quad \hbox{得證。} \end{eqnarray*} 到此, 已足以說明在「一、動機」所觀察到的現象。 反之, 若 $r_nx^n+r_{n-1}x^{n-1}+\cdots+r_1x+r_0$ 為 $x^2+rx+s$ 的倍式, 則 $r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0=0$ 是否為 $a_n+ra_{n-1}+sa_{n-2}=0$ 的線性衍生遞迴式? 答案是肯定的。

逆定理： 設數列 $\langle a_n\rangle$ 滿足遞迴關係式： $a_nra_{n-1}+sa_{n-2}=0$, 其中 $n\in N$ 且 $n\ge 2$。 若 $r_nx^n+r_{n-1}x^{n-1}+\cdots+r_1x+r_0$ 為 $x^2+rx+s$ 的倍式, 則 $r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0=0$ 為由 $a_n+ra_{n-1}+sa_{n-2}=0$ 所導出的線性衍生遞迴式。

證明： 設 $r_nx^n+r_{n-1}x^{n-1}+\cdots+r_1x+r_0$ 除以 $x^2+rx+s$ 所得的商式為 $\sum\limits_{k=0}^{n-2} p_kx^{n-k-2}$, 可得 \begin{eqnarray*} &&\hskip -20pt \varphi(r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0)=r_nx^n+r_{n-1}x^{n-1}+\cdots+r_1x+r_0\\ &=&(x^2+rx+s)\cdot\Big(\sum_{k=0}^{n-2} p_kx^{n-k-2}\Big)=\sum_{k=0}^{n-2} [p_kx^{n-k-2}\cdot(x^2+rx+s)]\\ &=&\sum_{k=0}^{n-2} p_k(x^{n-k}+rx^{n-k-1}+sx^{n-k-2})=\sum_{k=0}^{n-2} [p_k\cdot\varphi(a_{n-k}+ra_{n-k-1}+s a_{n-k-2})]\\ &=&\varphi\Big[\sum_{k=0}^{n-2} p_k(a_{n-k}+ra_{n-k-1}+s a_{n-k-2})\Big]\\ \end{eqnarray*} 由於 $\varphi$ 是一對一對應, 所以 $$r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0=\sum_{k=0}^{n-2} p_k(a_{n-k}+ra_{n-k-1}+s a_{n-k-2}),$$ 即 $r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0=0$ 為由 $a_n+ra_{n-1}+sa_{n-2}=0$ 所導出的線性衍生遞迴式, 得證。

上述的證明過程, 實際上給出了如何由 $a_n+ra_{n-1}+sa_{n-2}=0$ 導出 $r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0=0$ 的具體操作方法： 將 $r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0$ 所對應的特徵多項式 $r_nx^n+r_{n-1}x^{n-1}+\cdots+r_1x+r_0$ 除以 $x^2+rx+s$, 設所得的商式為 $\sum\limits_{k=0}^{n-2} p_kx^{n-k-2}$, 則 $r_na_n+r_{n-1}a_{n-1}+\cdots+r_1a_1+r_0a_0$ 即可表示為 $\sum\limits_{k=0}^{n-2} p_k(a_{n-k}+ra_{n-k-1}+s a_{n-k-2})$。

例： 設 $\langle F_n\rangle$ 為費氏數列, 試證： $F_n=F_{n-3}+3F_{n-4}+3F_{n-5}+F_{n-6}$, 其中 $n\in N$ 且 $n\ge 6$。

證明： $F_n-F_{n-3}-3F_{n-4}-3F_{n-5}-F_{n-6}$ 所對應的特徵多項式為 $$x^n-x^{n-3}-3x^{n-4}-3x^{n-5}-x^{n-6}= x^{n-6}(x^6-x^3-3x^2-3x-1),$$ 由長除法得 \begin{eqnarray*} &&x^6-x^3-3x^2-3x-1=(x^2-x-1)(x^4+x^3+2x^2+2x+1)\\ \Rightarrow && x^{n-6}(x^6\!-\!x^3\!-\!3x^2\!-\!3x\!-\!1)=(x^2\!-\!x\!-\!1)(x^{n-2}+x^{n-3}+2x^{n-4}+2x^{n-5}+x^{n-6}) \end{eqnarray*} 由 $F_n-F_{n-1}-F_{n-2}=0$ \begin{eqnarray*} \Rightarrow &&1\cdot(F_n-F_{n-1}-F_{n-2})+1\cdot(F_{n-1}-F_{n-2}-F_{n-3})+2\cdot(F_{n-2}-F_{n-3}-F_{n-4})\\ &&+2\cdot(F_{n-3}-F_{n-4}-F_{n-5})+1\cdot(F_{n-4}-F_{n-5}-F_{n-6})=0\\ \Rightarrow &&F_n-F_{n-3}-3F_{n-4}-3F_{n-5}-F_{n-6}=0, \end{eqnarray*} 得證。

三、應用：

(一)費氏數列與二項式係數內積恆等式：

設 $\langle F_n\rangle$ 為費氏數列, 試證： $\sum\limits_{k=0}^n C_k^n F_k=F_{2n}$。

證明：

1. $F_{2n}-(C_n^nF_n+C_{n-1}^nF_{n-1}+\cdots+C_1^n F_1+C_0^nF_0)$ 所對應的特徵多項式為 $x^{2n}-(C_n^nx^n+C_{n-1}^nx^{n-1}+\cdots+C_1^n x^1+C_0^n)=x^{2n}-(x+1)^n$, 令 $f(x)=x^{2n}-(x+1)^n$。
2. 設 $x^2-x-1=0$ 的兩根為 $\alpha $ 與 $\beta$, 且 $\alpha \gt \beta\Rightarrow \alpha ^2=\alpha +1$ 且 $\beta^2=\beta+1$ 注意到 $f(\alpha )=\alpha ^{2n}-(\alpha +1)^n=\alpha ^{2n}-(\alpha ^2)^n=0$ 與 $f(\beta)=\beta^{2n}-(\beta+1)^n=\beta^{2n}-(\beta^2)^n=0$ 由因式定理, 得 $(x-\alpha )(x-\beta)$ 為 $f(x)$ 的因式 $\Rightarrow f(x)$ 為 $x^2-x-1$ 的倍式。
3. 由「線性衍生遞迴定理」的逆定理, 可知 $F_{2n}-(C_n^nF_n+C_{n-1}^nF_{n-1}+\cdots+C_1^n F_1+C_0^nF_0)=0$ 為 $F_n-F_{n-1}-F_{n-2}=0$ 的線性衍生遞迴式, 所以欲證之等式成立。

(二) Padovan 數列相關恆等式

Padovan 數列 $\langle P_n\rangle$ 定義如下： $P_0=P_1=P_2=1$, 且滿足遞迴關係式 $P_n=P_{n-2}+P_{n-3}$, 其中 $n\in N$ 且 $n\ge 3$。 (譯名為「巴都萬數列」)

設 $\langle P_n\rangle$ 為 Padovan 數列, 試證：

1. $P_n=P_{n-1}+P_{n-5}$
2. $P_n=P_{n-2}+P_{n-4}+P_{n-8}$
3. $P_n=P_{n-4}+P_{n-5}+P_{n-6}+P_{n-7}+P_{n-8}$

證明： $P_n-P_{n-2}-P_{n-3}=0$ 所對應的特徵方程式為 $x^3-x+1=0$, $P_n-P_{n-1}-P_{n-5}$, $P_n-P_{n-2}-P_{n-4}-P_{n-8}$ 與 $P_n-(P_{n-4}+P_{n-5}+P_{n-6}+P_{n-7}+P_{n-8})$ 所對應的特徵多項式分別為 $x^{n-5}(x^5-x^4-1)$, $x^{n-8}(x^8-x^6-x^4-1)$ 與 $x^{n-8}(x^8-x^4-x^3-x^2-x-1)$, 由長除法可得 \begin{eqnarray*} x^{n-5}(x^5-x^4-1)&=&(x^3-x-1)(x^{n-3}-x^{n-4}-x^{n-5})\\ x^{n-8}(x^8-x^6-x^4-1)&=&(x^3-x-1)(x^{n-3}+x^{n-6}-x^{n-7}+x^{n-8})\\ x^{n-8}(x^8-x^4-x^3-x^2-x-1)&=&(x^3-x-1)(x^{n-3}+x^{n-5}+x^{n-6}+x^{n-8}) \end{eqnarray*} 即 $x^{n-5}(x^5-x^4-1)$, $x^{n-8}(x^8-x^6-x^4-1)$ 與 $x^{n-8}(x^8-x^4-x^3-x^2-x-1)$ 皆為 $x^3-x-1$ 的倍式, 由「線性衍生遞迴定理」的逆定理, 欲證之等式皆成立。

四、結語：

設 $\langle F_n\rangle$ 為費氏數列, 對於形如 $F_n-5F_{n-4}-3F_{n-5}=0$ 的關係式, 一般會取數列的前幾項代入, 檢驗正確性, 再用數學歸納法證明, 整個問題也就到此為止。

本文從一般熟知的特徵方程式出發, 定義所謂的「特徵多項式」, 以找出「線性衍生遞迴式」的內在結構, 從而將這一類的問題, 轉化為多項式除法, 進而可以對線性的遞迴式, 給出系統性的證明。

參考資料

---本文作者任教台北市立第一女子高級中學---