壹、前言

在「Fibonacci 與 Padovan的對話 (上)(下)」兩篇文章 , 中, 首先將三階遞迴數列的一般項 $a_n$, 表示成完全齊次對稱多項式 $h_n(\alpha,\beta,\gamma)$ 的線性組合, 接著將巴都萬數列 $\langle P_n\rangle$ 的一般項表示為完全齊次對稱多項式, 最後利用「自由分解重組恆等式」, 將 $F_n$ 與 $P_n$ 的卷積化成 $h_n(\alpha,\beta,a,b,c)$ 的型態, 運用代數變形, 得到結果： $$\sum_{i=0}^n F_i\cdot P_{n-i}=F_{n+3}-P_{n+3}.$$ 將此式稱為「F-P卷積恆等式」。

本文的目的, 在於使用盡可能少的預備知識, 以及盡可能精簡的算式, 給出F-P卷積恆等式的另一個證明。

貳、記號

1. Fibonacci數列 $\langle F_n\rangle$： $\left\{\begin{array}{l} F_0=0,F_1=1\\[3pt] F_{n+2}=F_{n+1}+F_n\end{array}\right.$。 已知其一般項為 $F_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}$, 其中 $\alpha$ 與 $\beta$ 為 $x^2-x-1=0$ 的兩根。
2. Padovan 數列 $\langle P_n\rangle$: $\left\{\begin{array}{l} P_0=P_1=P_2=1\\[3pt] P_n=P_{n-2}+P_{n-3}\end{array}\right.$。 數列的前幾項為 1, 1, 1, 2, 2, 3, 4, 5, 7, $\ldots$。 根據參考資料 的說法, 此三階遞迴數列, 是在 1996 年, 由 Ian Stewart 在科學人雜誌提出。

註： 可將 $\langle P_n\rangle$ 延拓至所有整數下標：

由 $P_n=P_{n-2}+P_{n-3}\Rightarrow P_{n-3}=P_n-P_{n-2}$, 可由此定出 $P_{-1},P_{-2},P_{-3},\ldots$： $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$, $\ldots$。

參、本文

命題： $\sum\limits_{i=0}^n P_i\cdot F_{n-i}=F_{n+3}-P_{n+3}$.

證明： 注意到 $$x^n\!=\!(x^3-x-1)\!\cdot\!(P_{-2}x^{n-3}+P_{-1}x^{n-4}\!+\!P_0x^{n-5}\!+\!\cdots\!+\!P_{n-6}x\!+\!P_{n-5})\!+\!P_{n-4}x^2\!+\!P_{n-3}x\!+\!P_{n-5}. {\hbox{(註1)}}$$ 設 $x^2-x-1=0$ 的兩根為 $\alpha$ 與 $\beta$ \begin{eqnarray*} \Rightarrow \alpha^n&=&(\alpha^3-\alpha-1)\cdot\Big(\sum_{i=-2}^{n-5} P_i\cdot \alpha^{n-5-i}\Big)+P_{n-4}\alpha^2+P_{n-3}\alpha+P_{n-5}\\ &=&\alpha\cdot\Big(\sum_{i=-2}^{n-5} P_i\cdot \alpha^{n-5-i}\Big)+P_{n-4}\alpha^2+P_{n-3}\alpha+P_{n-5},\hskip 4cm \hbox{(註2)} \end{eqnarray*} 等號兩邊同除以 $\alpha$, 得 \begin{equation} \alpha^{n-1}=\sum_{i=-2}^{n-5} P_i\cdot \alpha^{n-5-i}+P_{n-4}\alpha\!+\!P_{n-3}\!-\!P_{n-5}\beta.\label{1} \end{equation} 同理可得 \begin{equation} \beta^{n-1}=\sum_{i=-2}^{n-5} P_i\cdot \beta^{n-5-i}+P_{n-4}\beta\!+\!P_{n-3}\!-\!P_{n-5}\alpha.\label{2} \end{equation}

將 \eqref{1}$-$\eqref{2} 之後, 等號兩邊再同除以 $\alpha-\beta$, 由 Binet 公式, 可得： (註3) \begin{eqnarray*} F_{n-1}&=&\sum_{i=-2}^{n-5} P_i\cdot F_{n-5-i}+P_{n-4}+P_{n-5}\\ &=&P_{-2}\cdot F_{n-3}+P_{-1}\cdot F_{n-4}+\sum_{i=0}^{n-5} P_i\cdot F_{n-5-i}+P_{n-2}\\ &&\hskip -40pt \Rightarrow\ \sum_{i=0}^{n-5} P_i\cdot F_{n-5-i}=F_{n-1}-F_{n-3}-P_{n-2}=F_{n-2}-P_{n-2}. \end{eqnarray*} 將上式中的 $n$ 用 $n+5$ 代入, 得 $\sum\limits_{i=0}^n P_i\cdot F_{n-i}=F_{n+3}-P_{n+3}$, 即為所欲證之等式。

註1： 乘開 $(x^3-x-1)\cdot(P_{-2}x^{n-3}+P_{-1}x^{n-4}+P_0x^{n-5}+\cdots+P_{n-6}x\!+\!P_{n-5})$ \begin{eqnarray*} &=&P_{-2}x^{n}+P_{-1}x^{n-1}+(P_0\!-\!P_{-2})x^{n-2}+(P_1\!-\!P_{-1}\!-\!P_{-2})x^{n-3}+(P_2\!-\!P_{0}\!-\!P_{-1})x^{n-4}\\ &&+\cdots\!+\!(P_{n-5}-P_{n-7}-P_{n-8})x^3+(-P_{n-6}-P_{n-7})x^2+(-P_{n-5}-P_{n-6})x-P_{n-5}\\ &=&x^n\!+\!0x^{n-1}\!+\!0x^{n-2}\!+\!0x^{n-3}\!+\!0x^{n-4}\!+\!\cdots\!+\!0x^3\!-\!P_{n-4}x^2\!-\!P_{n-3}x\!-\!P_{n-5},\ \hbox{移項即可得。} \end{eqnarray*}

註2： $\alpha^2-\alpha-1=0\Rightarrow \alpha^2=\alpha+1\Rightarrow \alpha^3=\alpha^2+\alpha=2\alpha+1$
$\Rightarrow \alpha^3-\alpha-1=(2\alpha+1)-(\alpha+1)=\alpha\,$。 又 $\alpha\beta=-1\Rightarrow 1/\alpha=-\beta$.

註3： 費氏數列的 Binet 公式： $F_n=\dfrac{\alpha^n-\beta^n}{\alpha-\beta}$, 其中 $n\ge 0$。

肆、結語

將 , 與本篇文章作一對比：

, 的手法是先處理一般性的三階遞迴數列, 以及引用完全齊次對稱多項式的公式, 再將之運用到一個特殊的三階遞迴數列 --- Padovan 數列, 其目的不只是要推導 F-P 卷積恆等式, 而是要呈現 Padovan 數列的背景, 以及其內在的架構。

相對地, 本文完全針對 Fibonacci 與 Padovan 數列的特性發揮, 先運用Padovan數列的遞迴關係, 建立所謂的「Padovan 數列生成多項式」： $$x^n\!=\!(x^3-x-1)\cdot(P_{-2}x^{n-3}+P_{-1}x^{n-4}\!+\!P_0x^{n-5}\!+\!\cdots\!+\!P_{n-6}x\!+\!P_{n-5})\!+\!P_{n-4}x^2\!+\!P_{n-3}x\!+\!P_{n-5}, $$ 以此式為骨幹, 將費氏數列特徵方程式 $x^2-x-1=0$ 的兩根 $\alpha$ 與 $\beta$ 代入, 相減再除以 $\alpha-\beta$ 之後, 由費氏數列的 Binet 公式, 將變數 $x^n$ 轉換成了數列 $F_n$, 進而整理得到所謂的「F-P卷積恆等式」： $\sum\limits_{i=0}^n P_i\cdot F_{n-i}=F_{n+3}-P_{n+3}$。 數學世界, 多彩多姿, 運用之妙, 存乎一心, 尚請讀者諸君不吝批評指教。

參考資料

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