壹、前言

在「Fibonacci 與 Padovan 的對話(上)」一文中, 有 $F_n=h_{n-1}(\alpha,\beta)$ 與 $P_n=h_{n+2}(a,b,c)$, 亦即可將 Fibonacci 數列和 Padovan 數列視為完全齊次對稱多項式的特殊情形, 於是有可能運用完全齊次對稱多項式的已知性質, 來得到 Fibonacci 數列和 Padovan 數列的性質。

兩數列 $\langle a_n\rangle$ 和 $\langle b_n\rangle $ 的「卷積」(convolution) 形如 $\sum\limits_{i=0}^n a_i\cdot b_{n-i}$, 亦即兩數列對應項相乘再相加, 保持下標總和為 $n\,$。 在「完全齊次對稱多項式(起)」(參考資料 )一文中, 有「自由分解重組恆等式」, 其中的 $$\sum_{k_1+k_2+\cdot+k_m=k\atop k_1,k_2,\ldots,k_m\ge 0}\hskip -15pt [h_{k_1}(a_1,a_2,\ldots,a_{i_1})\cdot h_{k_2}(a_{i_1+1},a_{i_1+2},\ldots,a_{i_2})\cdots h_{k_m} (a_{i_{m-1}+1},a_{i_{m-1}+2},\ldots,a_{i_m})]$$ 是卷積的一種推廣形式, 參考資料 證明了可將此式的變數合併, 「重組」成相對簡單的形式 $h_k(a_1,a_2,\ldots,a_n)$。

本文的目的在求出卷積 $\sum\limits_{i=0}^n F_i\cdot P_{n-i}$ 的表達式, 首先先將 $F_n$ 與 $P_n$ 改成完全齊次對稱多項式 $h_{n-1}(\alpha,\beta)$ 與 $h_{n+2}(a,b,c)$, 接著利用自由分解重組恆等式, 將 $F_n$ 與 $P_n$ 的卷積化成 $h_k(\alpha,\beta,a,b,c)$ 的型態, 運用代數變形, 得到初步結果： $$\sum_{k=0}^n F_{k+1}\cdot P_{n-k-2}=F_{n+3}-P_{n+2}.$$ 再經由下標的調整, 得到形式更為對稱的結果： $$\sum_{i=0}^n F_i\cdot P_{n-i}=F_{n+3}-P_{n+3}.$$ 。

貳、本文

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

1. 自由分解重組恆等式: (參考資料 )

\begin{eqnarray*} &&\hskip -10pt h_k(a_1,a_2,\ldots,a_n)\\ &=&\hskip -13pt \sum_{k_1+k_2+\cdot+k_m=k\atop k_1,k_2,\ldots,k_m\ge 0}\hskip -15pt [h_{k_1}(a_1,a_2,\ldots,a_{i_1})\!\cdot\! h_{k_2}(a_{i_1+1},a_{i_1+2},\ldots,a_{i_2})\!\cdots\! h_{k_m} (a_{i_{m-1}+1},a_{i_{m-1}+2},\ldots,a_{i_m})] \end{eqnarray*} 其中 $a_{i_m}=a_n\,$。 (其中將變數 $a_1,a_2,\ldots,a_n$ 分成 $m$ 組, 第一組為 $a_1,a_2,\ldots,a_{i_1}$, 第二組為 $a_{i_1+1},a_{i_1+2},\ldots,a_{i_2},\ \ldots$, 第 $m$ 組為 $a_{i_{m-1}+1},a_{i_{m-1}+2},\ldots,a_{i_m}$)

例： \begin{eqnarray*} \sum_{i+j=2\atop i,j\ge 0} h_i(a,b)\cdot h_j(c,d)&=& h_2(a,b)\cdot h_0(c,d)+h_1(a,b)\cdot h_1(c,d)+h_0(a,b)\cdot h_2(c,d)\\ &=&(a^2+ab+b^2)\cdot 1+(a+b)(c+d)+1\cdot(c^2+cd+d^2)\\ &=&a^2+b^2+c^2+d^2+ab+ac+ad+bc+bd+cd\\ &=&h_2(a,b,c,d) \end{eqnarray*}

說明： 此式將下標總和為 2 的各個完全齊次對稱多項式先相乘再相加, 所得的式子為 $h_2(a,b,c,d)$, 將變數 $a,b$ 與 $c,d$ 合併在一起。

例： $$\sum\limits_{i+j=n\atop i,j\ge 0} h_i(a_1,a_2)\cdot h_j(a_3,a_4,a_5)=h_n(a_1,a_2,a_3,a_4,a_5)$$ 取 $a_1=\alpha$, $a_2=\beta$, $a_3=a$, $a_4=b$, $a_5=c$, 得 $$h_n(\alpha,\beta,a,b,c)=\sum\limits_{i+j=n\atop i,j\ge 0} h_i(\alpha,\beta)\cdot h_j(a,b,c)=\sum_{i=0}^n h_i(\alpha,\beta)\cdot h_{n-i}(a,b,c).$$

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

例： 當 $n=5$ 時, 得 $h_k(a_1,a_2,a_3,a_4,a_5)=L_{k+4}(a_1,a_2,a_3,a_4,a_5)$,

取 $a_1=\alpha$, $a_2=\beta$, $a_3=a$, $a_4=b$, $a_5=c$, 得 $h_k(\alpha,\beta,a,b,c)=L_{k+4}(\alpha,\beta,a,b,c)\,$ 。

二、主要工作

(一) F$-$P卷積恆等式： $\sum\limits_{k=0}^n F_{k+1}\cdot P_{n-k-2}=F_{n+3}-P_{n+2}$

設 $x^2-x-1=0$ 的兩根為 $\alpha$ 與 $\beta$, 且 $x^3-x-1=0$ 的三根為 $a,b,c\,$。

1. \begin{eqnarray*} \sum_{k=0}^n F_{k+1}\cdot P_{n-k-2}&=&\sum_{k=0}^n h_k(\alpha,\beta)\cdot h_{n-k}(a,b,c)=h_n(\alpha,\beta,a,b,c)\hskip 3cm~\\ &&\hskip -30pt \hbox{(自由分解重組恆等式, 參見本篇文章第 67 頁)} \end{eqnarray*}
2. $h_n(\alpha,\beta,a,b,c)$ \begin{eqnarray*} &=&L_{n+4}(\alpha,\beta,a,b,c) \quad \hbox{(由 $h-L$ 轉換公式, 參見本篇文章第 67 頁)}\\ &=&\frac{\alpha^{n+4}}{(\alpha-\beta)(\alpha-a)(\alpha-b)(\alpha-c)}+\frac{\beta^{n+4}}{(\beta-\alpha)(\beta-a)(\beta-b)(\beta-c)}\\ &&+\frac{a^{n+4}}{(a-\alpha)(a-\beta)(a-b)(a-c)} +\frac{b^{n+4}}{(b-\alpha)(b-\beta)(b-a)(b-c)}\hskip 4cm~\\ &&+\frac{c^{n+4}}{(c-\alpha)(c-\beta)(c-a)(c-b)} \end{eqnarray*}
3. $L_{n+4}(\alpha,\beta,a,b,c)$ 的前兩項之和： \begin{eqnarray*} &=&\frac{\alpha^{n+4}}{(\alpha-\beta){\color{red} {(\alpha-a)(\alpha-b)(\alpha-c)}}}+\frac{\beta^{n+4}}{(\beta-\alpha){\color{blue} {(\beta-a)(\beta-b)(\beta-c)}}}\hskip3cm~\\ &=&\frac{\alpha^{n+4}}{(\alpha-\beta)({\color{red} {\alpha^3-\alpha-1}})}+\frac{\beta^{n+4}}{(\beta-\alpha)({\color{blue} {\beta^3-\beta-1}})}\quad \hbox{(註1)}\\ &=&\frac{\alpha^{n+4}}{(\alpha-\beta)\cdot \alpha}+\frac{\beta^{n+4}}{(\beta-\alpha)\cdot \beta}\hskip 3.75cm \hbox{(註2)}\\ &=&\frac{\alpha^{n+3}}{\alpha-\beta}+\frac{\beta^{n+3}}{\beta-\alpha}\\ &=&\frac{\alpha^{n+3}-\beta^{n+3}}{\alpha-\beta}\\ &=&F_{n+3} \end{eqnarray*}

   註1： $\because$ $x^3-x-1=(x-a)(x-b)(x-c)\Rightarrow (\alpha-a)(\alpha-b)(\alpha-c)=\alpha^3-\alpha-1\,$。

   同理, 有 $(\beta-a)(\beta-b)(\beta-c)=\beta^3-\beta-1\,$。

   註2： $\because$ $x^2-x-1=(x-\alpha)(x-\beta)\Rightarrow \alpha^2-\alpha-1=0\Rightarrow \alpha^2=\alpha+1\Rightarrow \\ \alpha^3=\alpha^2+\alpha=(\alpha+1)+\alpha=2\alpha+1 \Rightarrow \alpha^3-\alpha-1=(2\alpha+1)-\alpha-1=\alpha\,$。

4. \begin{eqnarray*} \frac{a^{n+4}}{{\color{red} {(a-\alpha)(a-\beta)}}(a-b)(a-c)}&=&\frac{a^{n+4}}{{\color{red} {(a^2-a-1)}}(a-b)(a-c)}\quad \hskip 15pt\hbox{(註1)}\\[8pt] &=&\frac{a^{n+4}}{{\color{red} {a^2(1-a)}}(a-b)(a-c)}\quad \hskip 30pt \hbox{(註2)}\\[8pt] &=&\frac{a^{n+2}}{(1-a)(a-b)(a-c)}\\[8pt] &=& {\color{blue}{ -\frac{1}{a-1}}}\cdot \frac{a^{n+2}}{(a-b)(a-c)}\\[8pt] &=& {\color{blue}{ -(a+1+\frac 1a)}}\cdot\frac{a^{n+2}}{(a-b)(a-c)}\quad \hbox{(註3)}\\[8pt] &=&-\frac{a^{n+3}+a^{n+2}+a^{n+1}}{(a-b)(a-c)}\\[8pt] &&\hskip -180pt \hbox{同理可證}\ \frac{b^{n+4}}{(b-\alpha)(b-\beta)(b-a)(b-c)}=-\frac{b^{n+3}+b^{n+2}+b^{n+1}}{(b-a)(b-c)}\\[8pt] &&\hskip -180pt \hbox{與}\quad\hskip 25pt \frac{c^{n+4}}{(c-\alpha)(c-\beta)(c-a)(c-b)}=-\frac{c^{n+3}+c^{n+2}+c^{n+1}}{(c-a)(c-b)} \end{eqnarray*}

   註1： $\because\ x^2-x-1=(x-\alpha)(x-\beta)\Rightarrow (a-\alpha)(a-\beta)=a^2-a-1$.

   註2： $\because\ x^3-x-1=(x-a)(x-b)(x-c)$ \begin{eqnarray*} &\Rightarrow& a^3-a-1=0\\ &\Rightarrow& -a-1=-a^3\\ &\Rightarrow& a^2-a-1=a^2-a^3=a^2(1-a). \end{eqnarray*}

   註3： $\because\ x^3-x-1=(x-a)(x-b)(x-c)$ \begin{eqnarray*} &\Rightarrow& a^3-a-1=0\\ &\Rightarrow& a^3-1=a\\ &\Rightarrow& (a-1)(a^2+a+1)=a\\ &\Rightarrow& \dfrac{1}{a-1}=\dfrac{a^2+a+1}{a}=a+1+\dfrac 1a. \end{eqnarray*}

5. 由 4, $L_{n+4}$ 的後三項之和： \begin{eqnarray*} &&\hskip -15pt \frac{a^{n+4}}{(a-\alpha)(a-\beta)(a-b)(a-c)}+\frac{b^{n+4}}{(b-\alpha)(b-\beta)(b-a)(b-c)}\\ &&+\frac{c^{n+4}}{(c-\alpha)(c-\beta)(c-a)(c-b)}\\ &=& -\frac{a^{n+3}+a^{n+2}+a^{n+1}}{(a-b)(a-c)}-\frac{b^{n+3}+b^{n+2}+b^{n+1}}{(b-a)(b-c)}-\frac{c^{n+3}+c^{n+2}+c^{n+1}}{(c-a)(c-b)}\\ &=& -\left[\frac{a^{n+3}}{(a-b)(a-c)}+\frac{b^{n+3}}{(b-a)(b-c)}+\frac{c^{n+3}}{(c-a)(c-b)}\right]\\ &&-\left[\frac{a^{n+2}}{(a-b)(a-c)}+\frac{b^{n+2}}{(b-a)(b-c)}+\frac{c^{n+2}}{(c-a)(c-b)}\right]\\ &&-\left[\frac{a^{n+1}}{(a-b)(a-c)}+\frac{b^{n+1}}{(b-a)(b-c)}+\frac{c^{n+1}}{(c-a)(c-b)}\right]\\ &=& -L_{n+3}(a,b,c)-L_{n+2}(a,b,c)-L_{n+1}(a,b,c)\\ &=& -h_{n+1}(a,b,c)-h_{n}(a,b,c)-h_{n-1}(a,b,c)\qquad \hbox{(用 $h-L$ 轉換公式)}\\ &=& -(P_{n-1}+{\color{red}{ P_{n-2}+P_{n-3}}})\\ &=& -({\color{red} {P_n}}+P_{n-1})\\ &=& -P_{n+2} \end{eqnarray*}
6. 由 1, 2, 3, 4, 5, 可得 \begin{eqnarray*} &&\hskip -20pt \sum_{k=0}^n F_{k+1}\cdot P_{n-k-2}=h_n(\alpha,\beta,a,b,c)\\ &=& {\color{red} {\frac{\alpha^{n+4}}{(\alpha-\beta)(\alpha-a)(\alpha-b)(\alpha-c)}+\frac{\beta^{n+4}}{(\beta-\alpha)(\beta-a)(\beta-b)(\beta-c)}}}\\ &&{\color{blue} {+\frac{a^{n+4}}{(a-\alpha)(a-\beta)(a-b)(a-c)} +\frac{b^{n+4}}{(b-\alpha)(b-\beta)(b-a)(b-c)}}}\hskip 4cm~\\ &&{\color{blue} {+\frac{c^{n+4}}{(c-\alpha)(c-\beta)(c-a)(c-b)}}}\\ &=&{\color{red} {F_{n+3}}}-{\color{blue} {P_{n+2}}} \end{eqnarray*} 所以有 \begin{equation} \sum_{k=0}^n F_{k+1}\cdot P_{n-k-2}=F_{n+3}-P_{n+2} \end{equation}

至此, 已將 Fibonacci 數列與 Padovan 數列的卷積, 用兩數列相減來表示。

(二)更進一步的結果： $\sum\limits_{i=0}^n F_i\cdot P_{n-i}=F_{n+3}-P_{n+3}$

就 $\sum\limits_{k=0}^n F_{k+1}\cdot P_{n-k-2}=F_{n+3}-P_{n+2}$ 而言, 形式已算簡潔, 但仍有可以改進的空間： \begin{eqnarray*} \sum\limits_{k=0}^n F_{k+1}\cdot P_{n-k-2}&=&\sum\limits_{k+1=1}^{n+1} F_{k+1}\cdot P_{n-1-(k+1)}\\ &=&\sum\limits_{k+1={\color{red} {0}}}^{n+1} F_{k+1}\cdot P_{n-1-(k+1)}\qquad (\because\ F_0=F_2-F_1=1-1=0)\\ &=&\sum_{i=0}^{n+1}F_i\cdot P_{n-1-i}\hskip 2.5cm (\hbox{令}\ k+1=i)\\ &=&\sum_{i=0}^{n-1} F_i\cdot P_{(n-1)-i}+F_n\cdot P_{(n-1)-n}+F_{n+1}\cdot P_{(n-1)-(n+1)}\\ &=&\sum_{i=0}^{n-1}F_i\cdot P_{(n-1)-i}+F_n\cdot P_{-1}+F_{n+1}\cdot P_{-2}\\ &=&\sum_{i=0}^{n-1}F_i\cdot P_{(n-1)-i}+F_{n+1}\qquad (\because\ P_{-1}=0\ \hbox{且}\ P_{-2}=1)\\ {\hbox{由}} &&\sum_{k=0}^n F_{k+1}\cdot P_{n-k-2}=F_{n+3}-P_{n+2}\\ &\Rightarrow&\sum_{i=0}^{n-1}F_i\cdot P_{(n-1)-i}+F_{n+1}=F_{n+3}-P_{n+2}\\ &\Rightarrow&\sum_{i=0}^{n-1}F_i\cdot P_{n-1-i}=F_{n+3}-P_{n+2}-F_{n+1}=F_{n+2}-P_{n+2}\\ \end{eqnarray*} 將 $n$ 代換成 $n+1$, 得 \begin{equation} \sum_{i=0}^{(n+1)-1}F_i\cdot P_{(n+1)-1-i}=F_{(n+1)+2}-P_{(n+1)+2}\Rightarrow \sum_{i=0}^n F_i\cdot P_{n-i}=F_{n+3}-P_{n+3}\label{2} \end{equation} 至此, 得到一個形式更對稱美觀的 $F-P$ 卷積恆等式。

三、相關文獻比較

在探索工作告一段落之後, 作相關文獻搜尋, 得知 Capponi, A., Farina, A., Pilotto, C. 在 Expressing stochastic filters via number sequences 一文 (參考資料 ) 中, 有如下的性質： $$\hbox{令}\ \gamma_n=d_{n-3}+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1\}} f_{i-3}\cdot d_j,\ \hbox{其中 $d_n$ 代表 Padovan 數列, 則有 $\gamma_n=f_n\,$。}$$

以本文的記號而言, 此結果相當於 \begin{equation} F_n=P_{n-3}+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1\}} F_{i-3}\cdot P_j\label{3} \end{equation} 也呈現了 F$-$P 卷積的一種表達式。

那麼, 式子 \eqref{3} 和本文所得的式子 \eqref{2} 的關係為何？

筆者對 \eqref{3} 式研究如下： \begin{eqnarray*} &&\hskip -15pt \hbox{由}\quad F_n=P_{n-3}+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1\}} F_{i-3}\cdot P_j\\ &\Rightarrow&F_n=P_n-P_{n-2}+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1\}} F_{i-3}\cdot P_j \quad (\because\ P_n=P_{n-2}+P_{n-3})\\ &\Rightarrow&F_n=P_n-P_{n-2}+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1,2\}} F_{i-3}\cdot P_j +F_{-1}\cdot P_{n-2}\quad (\hbox{最右項為}\ i=2,j=n-2)\\ &\Rightarrow&F_n=P_n+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1,2\}} F_{i-3}\cdot P_j \quad (\because\ F_{-1}=F_1-F_0=1-0=1)\\ &\Rightarrow&F_n-P_n=\sum_{(i-3)+j=n-3\atop i-3\ge -3,j\ge 0,i-3\not=\{-3,-2,-1\}} F_{i-3}\cdot P_j \\ &\Rightarrow&F_n-P_n=\sum_{k+j=n-3\atop k\ge -3,j\ge 0,k\not=\{-3,-2,-1\}} F_{k}\cdot P_j =\sum_{k+j=n-3\atop k\ge 0,j\ge 0} F_{k}\cdot P_j \quad (\hbox{令}\ i-3=k)\\ {\hbox{將 $n$ 用 $n+3$ 代入, 得}} &&F_{n+3}-P_{n+3}=\sum_{k+j=n\atop k\ge 0,j\ge 0} F_k\cdot P_j=\sum_{k=0}^n F_k\cdot P_{n-k} \end{eqnarray*} 至此, 證明了 \eqref{3} 式其實和 \eqref{2} 式是等價的, 但就形式而言, \eqref{2} 式更為對稱。

參、結語

文章題為「Fibonacci 與 Padovan 的對話」, 對話所用的「語言」是「完全齊次對稱多項式」, 所得的結果為 $\sum\limits_{i=0}^n F_i\cdot P_{n-i}=F_{n+3}-P_{n+3}\,$。 相對地, 參考資料 所用的語言為「生成函數」, 所得的性質為 $$F_n=P_{n-3}+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1\}} F_{i-3}\cdot P_j.$$

在「Fibonacci 與 Padovan的對話(上)(下)」這兩篇文章中, 筆者提出並證明了「F$-$P卷積恆等式」： $\sum\limits_{i=0}^n F_i\cdot P_{n-i}=F_{n+3}-P_{n+3}$； 而在相關文獻比較中, 筆者證明了參考資料 的 $$F_n=P_{n-3}+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1\}} F_{i-3}\cdot P_j.$$ 可改寫為本文的 $$\sum\limits_{i=0}^n F_i\cdot P_{n-i}=F_{n+3}-P_{n+3}.$$ 注意到 $$F_n=P_{n-3}+\sum_{i+j=n\atop i,j\ge 0,i\not=\{0,1\}} F_{i-3}\cdot P_j$$ 之中的 $i\not=\{0,1\}$ 以及數列下標的 $i-3$, 在式子的形式與結構上, 都有可以改進之處, 筆者將之推進了一步。

最後, 就筆者的認知, $$\sum\limits_{i=0}^n F_i\cdot P_{n-i}=F_{n+3}-P_{n+3}$$ 此一恆等式的提出, 以及用「完全齊次對稱多項式」加以證明的手法, 皆為本人的原創性結果, 尚祈讀者諸君不吝予以批評指教。

參考資料

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