全文 |
壹、前言
各位讀者, 你知道 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)$ 的線性組合:
- 設 $\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$ 項的係數。
- 由「拉格朗日插值多項式」, 可得
\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*}
- 由 $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*}
- 由 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 數列的一般項
- 在上述的推導過程中, 取 $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)$。
- 更進一步地, 由「$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*}
- 由 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$。
(三)延拓至所有整數下標
- 對於 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*}
- 設 $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*}
- 注意到 $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$ 有三相異根。
證明:
- 若 $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$ 沒有三重根。}$$
- 若 $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$ 沒有二重根。
- 由 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}$, 亦可看出此三根相異。
參考資料
陳建燁。 推導費氏數列性質三部曲(中):用根與係數關係。 高中數學學科中心電子報第109期 , p.1, 2016年4月。
廖信傑。 用矩陣方法探討三階遞迴數列。 數學傳播, 38(1), 36-50, 2005。
陳建燁。 用「拉格朗日插值多項式」求三階遞迴數列的一般項(三相異根)。 高中數學學科中心電子報第115期, 1-2, 2016年10月。
陳建燁。 推廣的 Vandermonde 行列式(最右行升次型)。 高中數學學科中心電子報第114期, p.6, 11, 12, 14, 2016年9月。
I. G. Macdonald, Symmetric Functions and Hall Polynomials, 12-14.
本文作者任教台北市立第一女子高級中學---
|