壹、前言

各位讀者, 你知道 Fibonacci 數列與 Padovan 數列有什麼關聯性嗎？ 對於這兩個引起大量研究興趣的數列, 表面看似並不相關。 本文將揭示其內在的共通性, 並在下一篇文章研究涉及此兩數列的一個恆等式。

對於著名的 Fibonacci 數列 $\langle F_n\rangle : \left\{\begin{array}{l} F_0=0,\ F_1=1\\[5pt] F_{n+2}=F_{n+1}+F_n\end{array}\right.$, 已知其一般項為 $$F_n=\frac{1}{\sqrt 5}\Big[\Big(\frac{1+\sqrt 5}{2}\Big)^n-\Big(\frac{1-\sqrt 5}{2}\Big)^n\Big]$$(參考資料 )。

設 $\alpha$ 與 $\beta$ 為特徵方程式 $x^2-x-1=0$ 的兩根, 且 $\alpha\gt \beta$, 則 $$F_n=\frac{1}{\sqrt 5}(\alpha^n-\beta^n)=\frac{\alpha^n-\beta^n}{\alpha-\beta}=\alpha^{n-1}+\alpha^{n-2}\beta+\cdots+\alpha \beta^{n-2}+\beta^{n-1}.$$ 其中的 $\alpha^{n-1}+\alpha^{n-2}\beta+\cdots+\alpha \beta^{n-2}+\beta^{n-1}$, 恰為 $\alpha$ 與 $\beta$ 的「完全齊次對稱多項式」, 記作 $h_{n-1}(\alpha,\beta)$。 以上說明了 $F_n=h_{n-1}(\alpha,\beta)$, 亦即可將費氏數列的一般項, 表示成完全齊次對稱多項式。

相對地, 另一個引起研究興趣的遞迴數列是所謂的： $$\hbox{Padovan 數列}\ \langle P_n\rangle : \left\{\begin{array}{l} P_0=P_1=P_2=1\\[5pt] P_n=P_{n-2}+P_{n-3}\end{array}\right.\hbox{。}$$(參考資料 ) 數列的前幾項為 1, 1, 1, 2, 2, 3, 4, 5, 7, $\ldots$。

根據參考資料 的說法, 此三階遞迴數列, 是在 1996 年, 由 Ian Stewart 在科學人雜誌提出。

本文的主要動機是 : 相較於 Fibonacci 數列可表示成完全齊次對稱多項式, 是否能將 Padovan數 列也表示成完全齊次對稱多項式？

答案是肯定的, 在本篇文章中, 將證明 $P_n=h_{n+2}(a,b,c)$, 其中 $a,b,c$ 是 $\langle P_n\rangle $ 的特徵方程式 $x^3-x-1=0$ 的三個根。

貳、本文

一、定義、記號與已知公式：

1. 三階遞迴數列生成恆等式 (參考資料 )

設 $\langle a_n\rangle$ 為三階遞迴數列, 滿足遞迴關係 $a_{n+3}=pa_{n+2}+qa_{n+1}+ra_n$, 其中 $n=0,1,2,\ldots$, 則有 \begin{eqnarray*} &&\hskip -20pt a_0x^{n+3}+(a_1-pa_0)x^{n+2}+(a_2-pa_1-qa_0)x^{n+1}\\ &=&(x^3-px^2-qx-r)(a_0x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-2}x^2+a_{n-1}x+a_n)\\ &&+(pa_n+qa_{n-1}+ra_{n-2})x^2+(qa_n+ra_{n-1})x+ra_n,\qquad \hbox{其中 $n\ge 2$。} \end{eqnarray*}

說明： 將 $(x^3-px^2-qx-r)(a_0x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-2}x^2+a_{n-1}x+a_n)$ 乘開, 得 $a_0x^{n+3}+(a_1-pa_0)x^{n+2}+(a_2-pa_1-qa_0)x^{n+1}-[(pa_n+qa_{n-1}+ra_{n-2})x^2$ $+(qa_n+ra_{n-1})x+ra_n],$ 移項之後即得。

2. 完全齊次對稱多項式 (Complete Homogeneous Symmetric Polynomial)

定義： $$h_k(a_1,a_2,\ldots,a_n)=\sum_{\lambda_1+\lambda_2+\cdot+\lambda_n=k\atop \lambda_1,\lambda_2,\ldots,\lambda_n\ge 0}(a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_n^{\lambda_n}),$$ 稱為「變數 $a_1,a_2,\ldots,a_n$ 的 $k$ 次完全齊次對稱多項式」。特別地, $h_0(a_1,a_2,\ldots,a_n)=1$, 且 $h_k(a)=a^k$。

例： $$h_2(a_1,a_2,a_3)=\sum_{\lambda_1+\lambda_2+\lambda_3=2\atop \lambda_1,\lambda_2,\lambda_3\ge 0}(a_1^{\lambda_1}a_2^{\lambda_2} a_3^{\lambda_3})=a_1^2+a_2^2+a_3^2+a_1a_2+a_2a_3+a_3a_1.$$

例： $h_2(a,b,c)=a^2+b^2+c^2+ab+bc+ca.$

例： $h_3(a,b)=a^3+b^3+a^2b+ab^2.$

3. 拉格朗日插值型式

定義： $$L_k(a_1,a_2,\ldots,a_n)=\sum_{i=1}^n \frac{a_i^k}{\prod\limits_{1\le j\le n\atop j\not=i} (a_i-a_j)},$$ 稱為「變數 $a_1,a_2,\ldots,a_n$ 的 $k$ 次拉格朗日插值型式」。

註： 以分子的次方來定義 $L$ 的下標。

例： \begin{eqnarray*} L_2(a_1,a_2,a_3)&=&\sum_{i=1}^3 \frac{a_i^2}{\prod\limits_{1\le j\le 3\atop j\not=i} (a_i-a_j)}=\frac{a_1^2}{(a_1-a_2)(a_1-a_3)} +\frac{a_2^2}{(a_2-a_1)(a_2-a_3)}\\ &&+\frac{a_3^2}{(a_3-a_1)(a_3-a_2)}.\end{eqnarray*}

例： \begin{eqnarray*} L_{\color{red} 8}(a,b,c,d)&=&\frac{a^{\color{red} 8}}{(a-b)(a-c)(a-d)}+\frac{b^{\color{red} 8}}{(b-a)(b-c)(b-d)}+\frac{c^{\color{red} 8}}{(c-a)(c-b)(c-d)}\\ &&+\frac{d^{\color{red} 8}}{(d-a)(d-b)(d-c)}.\end{eqnarray*}

4. ${h-L}$ 轉換公式 : $h_k(a_1,a_2,\ldots,a_n)=L_{k+n-1}(a_1,a_2,\ldots,a_n)$, 其中 $n\ge 2$, $k\ge 0$。 (參考資料 )

說明： 此一公式, 可將「完全齊次對稱多項式」與「拉格朗日插值型式」互相轉換。

例： 取 $n=3$, $k=5$, 得 $h_5(a_1,a_2,a_3)=L_{5+3-1}(a_1,a_2,a_3)=L_7(a_1,a_2,a_3)$。

說明： 對於 $$L_7(a_1,a_2,a_3)=\frac{a_1^7}{(a_1-a_2)(a_1-a_3)}+ \frac{a_2^7}{(a_2-a_1)(a_2-a_3)}+\frac{a_3^7}{(a_3-a_1)(a_3-a_2)} ,$$ 首先, 有 3 個變數 $a_1,a_2,a_3$, 則 $n=3$。 接著, $\dfrac{a_1^7}{(a_1-a_2)(a_1-a_3)}$ 的分母為 2 次方, 分子為 7 次方, 所以化簡後所得齊次式 $h_k(a_1,a_2,a_3)$ 的次方 $k$ 為 $7-2=5$, 於是有 $L_7(a_1,a_2,a_3)=h_5(a_1,a_2,a_3)$。

注意到 $7-5=2=3-1$, 可以看出： $L$ 與 $h$ 的下標之差, 恰為變數個數減 1。

由於 $L$ 與 $h$ 的下標之差, 恰為變數個數減 1, 因此 $h-L$ 轉換公式, 也可寫成： \begin{eqnarray} L_k(a_1,a_2,\ldots,a_n)=h_{k-(n-1)}(a_1,a_2,\ldots,a_n), \quad \hbox{其中 $k\ge n-1$。} \label{1} \end{eqnarray}

例： $L_{11}(a,b,c,d)=h_{11-(4-1)}(a,b,c,d)=h_8(a,b,c,d)$。

例： $L_{n+3}(\alpha,\beta,\gamma)=h_{n+3-(3-1)}(\alpha,\beta,\gamma)=h_{n+1}(\alpha,\beta,\gamma)$。

5. 基本對稱多項式(Elementary Symmetric Polynomial)

定義： $e_k(a_1,a_2,\ldots,a_n)=\sum\limits_{\lambda_1+\lambda_2+\cdots+\lambda_n=k\atop 0\le \lambda_1,\lambda_2,\ldots,\lambda_n\le 1}(a_1^{\lambda_1}a_2^{\lambda_2}\cdots a_n^{\lambda_n})$, 稱為「變數 $a_1,a_2,\ldots,a_n$ 的 $k$ 次基本對稱多項式」。

例： $e_2(a_1,a_2,a_3)=\sum\limits_{\lambda_1+\lambda_2+\lambda_3=2\atop 0\le \lambda_1,\lambda_2,\lambda_3\le 1}(a_1^{\lambda_1}a_2^{\lambda_2} a_3^{\lambda_3})=a_1a_2+a_2a_3+a_3a_1$ 。

例： $e_0(a,b,c)=1,\quad e_1(a,b,c)=a+b+c,\quad e_2=ab+bc+ca,\quad e_3(a,b,c)=abc$ 。

例： $(x-a)(x-b)(x-c)=x^3-e_1(a,b,c)x^2+e_2(a,b,c)x-e_3(a,b,c)$ 。

6. 對稱多項式的「${e-h}$ 恆等式」 (參考資料 )

$$\sum_{k=0}^m (-1)^k e_k\cdot h_{n-k}=0,\quad\hbox{其中 $n\ge m$,}$$ 亦即 $h_n-e_1h_{n-1}+\cdots+(-1)^te_th_{n-t}+\cdots+(-1)^me_mh_{n-m}=0\,$。 (其中 $e_k=e_k(a_1,a_2,\ldots$, $a_m)$, $h_k=h_k(a_1,a_2,\ldots,a_m)$)

說明： 此式刻劃了基本對稱多項式與完全齊次對稱多項式的關聯性, 也說明了 $h_k(a_1, a_2,\ldots$, $a_m)$ 是 $m$ 階遞迴數列。

特別地, 當 $m=3$ 時, 有 $\sum\limits_{k=0}^3 (-1)^ke_k\cdot h_{n-k}=0$, 即

$h_n(a_1,a_2,a_3)-e_1 (a_1,a_2,a_3)h_{n-1}(a_1,a_2,a_3)+e_2(a_1,a_2,a_3)h_{n-2}(a_1,a_2,a_3)$
$-e_3(a_1,a_2,a_3)h_{n-3}(a_1,a_2,a_3)$ $=0$, 簡記為 $h_n-e_1\cdot h_{n-1}+e_2\cdot h_{n-2}-e_3\cdot h_{n-3}=0$。

二、主要工作：

(一)將三階遞迴數列的一般項 $a_n$ 表示 成完全齊次對稱多項式 $h_n(\alpha,\beta,\gamma)$ 的線性組合：

1. 設 $\langle a_n\rangle$ 為三階遞迴數列, 滿足遞迴關係 $a_{n+3}=pa_{n+2}+qa_{n+1}+r a_n$, 且設特徵方程式 $x^3-px^2-qx-r=0$ 有三相異根 $\alpha$、 $\beta$ 與 $\gamma$ 。 由「三階遞迴數列生成恆等式」, 有： \begin{eqnarray*} &&\hskip -20pt a_0x^{n+3}+(a_1-pa_0)x^{n+2}+(a_2-pa_1-qa_0)x^{n+1}\\ &=& {(x^3-px^2-qx-r)}(a_0x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-2}x^2+a_{n-1}x+a_n)\\ &&{ +(pa_n+qa_{n-1}+ra_{n-2})}x^2+(qa_n+ra_{n-1})x+ra_n\\ &=& {(x-\alpha)(x-\beta)(x-\gamma)}(a_0x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_{n-2}x^2+a_{n-1}x+a_n)\\ &&+{ a_{n+1}}x^2+(qa_n+ra_{n-1})x+ra_n,\quad \hbox{其中 $n\ge 2$。} \end{eqnarray*} 令 $f(x)=a_0x^{n+3}+(a_1-pa_0)x^{n+2}+(a_2-pa_1-qa_0)x^{n+1}=Ax^{n+3}+Bx^{n+2}+Cx^{n+1}$ 可將上式視為： $$\hbox{「$f(x)$ 除以 $(x-\alpha)(x-\beta)(x-\gamma)$ 的餘式為 $a_{n+1}x^2+(qa_n+ra_{n-1})x+ra_n$」。}$$ 可以看出, 三階遞迴數列的一般項 $a_{n+1}$, 正好是餘式 $a_{n+1}x^2+(qa_n+ra_{n-1})x+ra_n$ 的 $x^2$ 項的係數。
2. 由「拉格朗日插值多項式」, 可得 \begin{eqnarray*} &&\hskip -20pt \hbox{餘式}\ a_{n+1}x^2+(qa_n+ra_{n-1})x+ra_n\\ &=&f(\alpha)\cdot \frac{(x-\beta)(x-\gamma)}{(\alpha-\beta)(\alpha-\gamma)} +f(\beta)\cdot \frac{(x-\alpha)(x-\gamma)}{(\beta-\alpha)(\beta-\gamma)}+f(\gamma)\cdot \frac{(x-\alpha)(x-\beta)}{(\gamma-\alpha)(\gamma-\beta)} \end{eqnarray*} 比較 $x^2$ 的係數, 可得 \begin{eqnarray*} \hskip -20pt a_{n+1}&=&\frac{f(\alpha)}{(\alpha-\beta)(\alpha-\gamma)} +\frac{f(\beta)}{(\beta-\alpha)(\beta-\gamma)}+\frac{f(\gamma)}{(\gamma-\alpha)(\gamma-\beta)}\\ \!&\!=\!&\!\frac{A\alpha^{n+3}\!+\!B\alpha^{n+2}\!+\!C\alpha^{n+1}}{(\alpha\!-\!\beta)(\alpha\!-\!\gamma)} \!+\!\frac{A\beta^{n+3}\!+\!B\beta^{n+2}\!+\!C\beta^{n+1}}{(\beta\!-\!\alpha)(\beta\!-\!\gamma)}\!+\!\frac{A\gamma^{n+3}\!+\!B\gamma^{n+2}\!+\!C\gamma^{n+1}}{(\gamma\!-\!\alpha)(\gamma\!-\!\beta)}\\ \!&\!=\!&\!\frac{A\cdot\alpha^{n+3}}{(\alpha-\beta)(\alpha-\gamma)}+\frac{A\cdot\beta^{n+3}}{(\beta-\alpha)(\beta-\gamma)}+\frac{A\cdot\gamma^{n+3}}{(\gamma-\alpha)(\gamma-\beta)}\\ &&+\frac{B\cdot\alpha^{n+2}}{(\alpha-\beta)(\alpha-\gamma)}+\frac{B\cdot\beta^{n+2}}{(\beta-\alpha)(\beta-\gamma)}+\frac{B\cdot\gamma^{n+2}}{(\gamma-\alpha)(\gamma-\beta)}\\ &&+\frac{C\cdot\alpha^{n+1}}{(\alpha-\beta)(\alpha-\gamma)}+\frac{C\cdot\beta^{n+1}}{(\beta-\alpha)(\beta-\gamma)}+\frac{C\cdot\gamma^{n+1}}{(\gamma-\alpha)(\gamma-\beta)}\\ \!&\!=\!&\!A\cdot L_{n+3}(\alpha,\beta,\gamma)+B\cdot L_{n+2}(\alpha,\beta,\gamma)+C\cdot L_{n+1}(\alpha,\beta,\gamma) \end{eqnarray*}
3. 由 $h-L$ 轉換公式 (參見\eqref{1}), 可得 \begin{eqnarray*} &&\hskip -20pt A\cdot L_{n+3}(\alpha,\beta,\gamma)+B\cdot L_{n+2}(\alpha,\beta,\gamma)+C\cdot L_{n+1}(\alpha,\beta,\gamma)\\ &=&A\cdot h_{n+1}(\alpha,\beta,\gamma)+B\cdot h_n(\alpha,\beta,\gamma)+C\cdot h_{n-1}(\alpha,\beta,\gamma). \end{eqnarray*}
4. 由 1, 2, 3, 可得 \begin{eqnarray*} &&\hskip -10pt a_{n+1}=A\cdot h_{n+1}(\alpha,\beta,\gamma)+B\cdot h_n(\alpha,\beta,\gamma)+C\cdot h_{n-1}(\alpha,\beta,\gamma),\quad \hbox{其中 $n\ge 2$}\\ &\Rightarrow&a_n=A\cdot h_{n}(\alpha,\beta,\gamma)+B\cdot h_{n-1}(\alpha,\beta,\gamma)+C\cdot h_{n-2}(\alpha,\beta,\gamma),\quad \hbox{其中 $n\ge 3$},\\ &&\hbox{且 $A=a_0$, $B=a_1-pa_0$, $C=a_2-pa_1-qa_0$ 。} \end{eqnarray*} 至此, 已將三階遞迴數列的一般項 $a_n$ 表示成完全齊次對稱多項式 $h_n(\alpha,\beta,\gamma)$ 的線性組合。

(二) Padovan 數列的一般項

1. 在上述的推導過程中, 取 $a_0=a_1=a_2=1$ 與 $p=0$, $q=1$, $r=1$, 則數列 $\langle a_n\rangle$ 即為 Padovan 數列 $\langle P_n\rangle$。 設特徵方程式 $x^3-x-1=0$ 的三相異根為 $a,b,c$(註), 則有 $$P_n=A\cdot h_n(a,b,c)+B\cdot h_{n-1}(a,b,c)+C\cdot h_{n-2}(a,b,c),\quad \hbox{其中 $n\ge 3$,}$$ 此時 $A=a_0=1$, $B=a_1-pa_0=1-0\cdot 1=1$, $C=a_2-pa_1-qa_0=1-0\cdot 1-1\cdot 1=0$, 即得 $P_n=h_n(a,b,c)+h_{n-1}(a,b,c)$。
2. 更進一步地, 由「$e-h$ 恆等式」(參見\eqref{1}), 有 $h_n(a,b,c)-e_1(a,b,c)\cdot h_{n-1}(a,b,c)+e_2(a,b,c)\cdot h_{n-2}(a,b,c)-e_3(a,b,c)\cdot h_{n-3}(a,b,c)=0$, 其中 $n\ge 3$。
   又由 $x^3-x-1=(x-a)(x-b)(x-c)$, 可得 \begin{eqnarray*} &&\hskip -15pt e_1(a,b,c)=a+b+c=0,\ e_2(a,b,c)=ab+bc+ca=-1,\ e_3(a,b,c)=abc=1\\ &\Rightarrow&h_n(a,b,c)-0\cdot h_{n-1}(a,b,c)+(-1)\cdot h_{n-2}(a,b,c)-1\cdot h_{n-3}(a,b,c)=0\\ &\Rightarrow&h_n(a,b,c)=h_{n-2}(a,b,c)+h_{n-3}(a,b,c),\quad \hbox{其中 $n\ge 3$}\\ &\Rightarrow&h_{n+2}(a,b,c)=h_{n}(a,b,c)+h_{n-1}(a,b,c),\quad \hbox{其中 $n\ge 1$}. \end{eqnarray*}
3. 由 1, 2, 可得 $P_n= h_{n}(a,b,c)+h_{n-1}(a,b,c)=h_{n+2}(a,b,c)$, 其中 $n\ge 3$。 至此, 已將 Padovan 數列 $\langle P_n\rangle$ 的一般項表示為完全齊次對稱多項式 $h_{n+2}(a,b,c)$, 即 $P_n=h_{n+2}(a,b,c)$, 其中 $n\ge 3$, 且 $a,b,c$ 為 $\langle P_n\rangle$ 的特徵方程式 $x^3-x-1=0$ 的三根。 此一表達式, 也可寫成 $h_n(a,b,c)=P_{n-2}$, 其中 $n\ge 5$。

(三)延拓至所有整數下標

1. 對於 Padovan 數列 $\langle P_n\rangle:\left\{\begin{array}{l} P_0=P_1=P_2=1\\ P_n=P_{n-2}+P_{n-3}\end{array} \right.$, $P_n$ 的下標取值範圍可為所有整數。 由 $P_n=P_{n-2}+P_{n-3}\Rightarrow P_{n-3}=P_n-P_{n-2}$, 可由此定出 $P_{-1},P_{-2},P_{-3},\ldots$： \begin{eqnarray*} P_{-1}&=&P_2-P_0=1-1=0,\\ P_{-2}&=&P_1-P_{-1}=1-0=1,\\ P_{-3}&=&P_0-P_{-2}=1-1=0,\\ \vdots \end{eqnarray*}
2. 設 $a,b,c$ 為特徵方程式 $x^3-x-1=0$ 的三根, 由「$e-h$ 恆等式」, 有 $h_n(a,b,c)=h_{n-2}(a,b,c)+h_{n-3}(a,b,c)$, 其中 $n\ge 3$, 簡記為 $h_n=h_{n-2}+h_{n-3}$, 其中 $n\ge 3$, 此式說明了 $\langle h_n\rangle$ 也構成一個三階遞迴數列, 而數列的前 3 項分別為： $h_0(a,b,c)=1$, $h_1(a,b,c)=a+b+c=0$, $h_2(a,b,c)=(a+b+c)^2-(ab+bc+ca)=0-(-1)=1$, 所以有： $$\langle h_n\rangle:\left\{\begin{array}{l} h_0=1,\ h_1=0,\ h_2=1\\ h_n=h_{n-2}+h_{n-3}\end{array} \right.$$ 類似於 Padovan 數列, $h_n$ 的下標取值範圍也可為所有整數。 由 $h_n=h_{n-2}+h_{n-3}\Rightarrow h_{n-3}=h_n-h_{n-2}$, 可由此定出 $h_{-1},h_{-2},h_{-3},\ldots$： \begin{eqnarray*} h_{-1}&=&h_2-h_0=1-1=0,\\ h_{-2}&=&h_1-h_{-1}=0-0=0,\\ h_{-3}&=&h_0-h_{-2}=1-0=1,\\ \vdots \end{eqnarray*}
3. 注意到 $P_0=1=h_2$, $P_{-1}=0=h_1$ 與 $P_{-2}=1=h_0$, 即 $\langle P_n\rangle$ 與 $\langle h_n\rangle$ 有連續三項是相同的。 又 $\langle P_n\rangle$ 的遞迴關係式為 $P_n=P_{n-2}+P_{n-3}$, $\langle h_n\rangle$ 的遞迴關係式為 $h_n=h_{n-2}+h_{n-3}$, 形式完全相同, 所以可看出 $\langle P_n\rangle$ 與 $\langle h_n\rangle$ 兩數列中的項完全相同, 只有下標相差 2, 亦即 $P_n=h_{n+2}(a,b,c)$, 其中 $n$ 為任意整數。 舉例而言, 從 $P_0=1=h_2$, $P_{-1}=0=h_1$ 與 $P_{-2}=1=h_0$ 出發, 則 \begin{eqnarray*} P_{-3}&=&P_0-P_{-2}=h_2-h_0=h_{-1},\ P_{-4}=P_{-1}-P_{-3}=h_1-h_{-1}=h_{-2},\ldots;\\ P_{1}&=&P_{-1}+P_{-2}=h_1+h_0=h_3,\ P_2=P_0+P_{-1}=h_2+h_1=h_4,\\ P_3&=&P_1+P_0=h_3+h_2=h_5,\ldots, \end{eqnarray*} 可得 $P_n=h_{n+2}(a,b,c)$ 對所有整數下標皆成立。

註： 方程式 $x^3-x-1=0$ 有三相異根, 此一事實之證明置於附錄。

參、結語

回顧本文的工作, 第一階段, 先注意到三階遞迴數列一般項 $a_{n+1}$, 正好出現在多項式除法的餘式 $a_{n+1}x^2+(qa_n+ra_{n-1})x+ra_n$ 的 $x^2$ 項的係數； 接著用拉格朗日插值多項式寫出餘式, 求得餘式的 $x^2$ 項的係數為 $A\cdot L_{n+3}+B\cdot L_{n+2}+C\cdot L_{n+1}$； 再用 $h-L$ 轉換公式, 轉換成 $A\cdot h_{n+1}+B\cdot h_n+C\cdot h_{n-1}$。 用以上的方式, 將三階遞迴數列的一般項 $a_n$, 表示成完全齊次對稱多項式 $h_n(\alpha,\beta,\gamma)$ 的線性組合。

第二階段, 取 $a_0=a_1=a_2=1$ 與 $p=0$, $q=1$, $r=1$, 則數列 $\langle a_n\rangle$ 即為 Padovan 數列 $\langle P_n\rangle$, 得 $P_n=1\cdot h_n+1\cdot h_{n-1}+0\cdot h_{n-2}=h_n+h_{n-1}$； 再用 $e-h$ 恆等式, 得 $h_n+h_{n-1}=h_{n+2}$； 最後將下標延拓至所有整數, 得到 $P_n=h_{n+2}(a,b,c)$, 其中 $n$ 為任意整數, 且 $a,b,c$ 為特徵方程式 $x^3-x-1=0$ 的三根, 將 $\langle P_n\rangle$ 的一般項表示為完全齊次對稱多項式。

相較於將 Padovan 數列用一系列由小到大的正三角形邊長來呈現 (參考資料 ) 所展現的幾何面貌, 本篇文章揭示的是Padovan數列的「代數本質」, 亦即本質上,

Padovan 數列可視為完全齊次對稱多項式的一種特殊情形。 由此, 即有可能透過對完全齊次對稱多項式進行更一般的研究, 反過來得到 Padovan 數列的一些性質, 這是本文的目的所在。

附錄

方程式 $x^3-x-1=0$ 有三相異根。

證明：

1. 若 $x^3-x-1=(x-k)^3=x^3-3kx^2+3k^2x-k^3$ $$\Rightarrow\left\{\begin{array}{l} -3k=0\\ 3k^2=-1\\ -k^3=-1 \end{array}\right. ,\ \hbox{不合, 由此可知 $x^3-x-1=0$ 沒有三重根。}$$
2. 若 $x^3-x-1=(x-\alpha)^2(x-\beta)=x^3-(2\alpha+\beta)x^2+(\alpha^2+2\alpha\beta)x-\alpha^2\beta$, 其中 $\alpha\not=\beta \Rightarrow\left\{\begin{array}{l} -(2\alpha+\beta)=0\\ \alpha^2+2\alpha\beta=-1\\ -\alpha^2\beta=-1 \end{array} \right.$ 將 $\beta=-2\alpha$ 代入 $\alpha^2+2\alpha\beta=-1$ 與 $-\alpha^2\beta=-1$, 得 $3\alpha^2=1$ 與 $2\alpha^3=-1$ 將兩式相除, 得 $\alpha=-\dfrac 32\Rightarrow \beta=-2\alpha=3\Rightarrow \alpha^2\beta=\dfrac{27}{4}\not=1$, 不合, 由此可知 $x^3-x-1=0$ 沒有二重根。
3. 由 1, 2 可知, $x^3-x-1=0$ 有三相異根。

另證： 由一元三次方程式的公式解, 可直接解出 $x^3-x-1=0$ 的三根為 \begin{eqnarray*} &&\root 3\of {\frac 12+\sqrt{\frac{23}{108}}}+\root 3\of {\frac 12-\sqrt{\frac{23}{108}}},\ \root 3\of {\frac 12+\sqrt{\frac{23}{108}}}\cdot \omega +\root 3\of {\frac 12-\sqrt{\frac{23}{108}}}\cdot \omega^2\\ \hbox{與}\ &&\root 3\of {\frac 12+\sqrt{\frac{23}{108}}}\cdot \omega^2+\root 3\of {\frac 12-\sqrt{\frac{23}{108}}}\cdot \omega, \end{eqnarray*} 其中 $\omega=\dfrac{-1+\sqrt 3i}{2}$, 亦可看出此三根相異。

參考資料

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