1. 前言

Fibonacci 數 $F_n$ 和 Padovan 數 $P_n$ 分別滿足遞迴關係式 $F_{n+2}=F_{n+1}+F_n$ 及初始條件 $F_0=0$, $F_1=1$ 和遞迴式 $P_{n+3}=P_{n+1}+P_n$ 及初始條件 $P_0=P_1=P_2=1$ (見廖信傑)。

在「Fibonacci 與 Padovan 的對話(上)」 及「Fibonacci 與 Padovan 的對話(下): F-P 卷積恆等式」 與 中陳建燁先生證明了 $F_n$ 和 $P_n$ 可以表成變數取特別值的完全齊次對稱多項式 \begin{equation}\label{h_n} F_n=h_{n-1}(\alpha,\beta),~P_n=h_{n+2}(a,b,c), \end{equation} 其中 $\alpha,\beta$ 及 $a,b,c$ 分別為 $x^2-x-1=0$ 及 $x^3-x-1=0$ 的根。 並且利用 (\ref{h_n}) 及其稱作「自由分解重組恆等式」 之完全齊次對稱多項式 $h_n$ 的性質, 得到 Fibonacci 數和 Padovan 數有一個漂亮的卷積(convolution)公式: \begin{equation}\label{convol} \sum_{i=0}^{n}F_iP_{n-i}=F_{n+3}-P_{n+3}. \end{equation} 本文的目的是從生成函數(generating function)的角度來看 $F_n$ 和 $P_n$ 可以用完全齊次對稱多項式來表示這件事。 第二節我們先很概略的介紹兩類對稱多項式及之後會用到的性質, 接著利用生成函數的方法證明陳建燁先生 的兩個結果; 第三節, 我們利用生成函數得到更一般的 $k$ 階線性遞迴數列同樣也可以用完全對稱多項式來表示; 最後一節, 我們用生成函數方法證明卷積公式 (\ref{convol}), 並且也提供另一個有類似卷積公式的例子 : Fibonacci 數和 Tribonacci 數。

2. $F_n$, $P_n$用$h_n$表示

這一節我們會用生成函數方法證明 Fibonacci 數 $F_n$ 和 Padovan 數 $P_n$ 可完全齊次對稱多項式 $h_n$ 表示, 為此我們先回顧何謂完全齊次對稱多項式, 有關一些基本的生成函數操作讀者可以參考 Wilf 。

給定正整數$n$, 一個$m$個變數的完全齊次多項式定義作 $$ h_n(x_1,x_2,\ldots,x_m)=\sum_{1\le i_1\le i_2\le\ldots\le i_n\le m}x_{i_1}x_{i_2}\ldots x_{i_n}, $$ 例如 $h_{2}(x_1,x_2,x_3)=x_1^2+x_2^2+x_3^2+x_1x_2+x_1x_3+x_2x_3$。 由 $h_n$ 的定義我們很容易可以得到其生成函數為 \begin{equation}\label{hgf} \sum_{n=0}^\infty h_n(x_1,\ldots,x_m)t^n=\frac{1}{(1-x_1t)(1-x_2t)\ldots(1-x_mt)}, \end{equation} 只要把等號右邊看成 $m$ 個級數 $\sum_{k=0}^\infty x_i^kt^k$ $(i=1,2,\ldots,m)$ 的乘積後比較等式兩邊 $t^n$ 係數就可以得到。 另一類很常出現的對稱多項式是基本對稱多項式(elementary symmetric polynomial) $e_n$, 定義為 $$ e_n(x_1,x_2,\ldots,x_m)=\sum_{1\le i_1\lt i_2\lt \ldots\lt i_n\le m}x_{i_1}x_{i_2}\ldots x_{i_n}, $$ 例如 $e_1(x_1,x_2,x_3)=x_1+x_2+x_3, e_2(x_1,x_2,x_3)=x_1x_2+x_1x_3+x_2x_3$, 注意到當 $n\gt m$ 時 $e_n(x_1,\ldots,x_m)=0$。 並且其生成函數為 \begin{equation}\label{egf} \sum_{n=0}^\infty e_n(x_1,\ldots,x_m)t^n=(1+x_1t)(1+x_2t)\ldots(1+x_nt), \end{equation} 類似地只要比較等號兩邊 $t^n$ 係數馬上可以得到。 在對稱函數的理論中 $e_n$ 和 $h_n$ 是關係較密切的兩類, 這某種程度也反映在他們的生成函數上, 觀察 (\ref{hgf}) 和 (\ref{egf}) 注意到若將 (\ref{egf}) 中 $t$ 用 $-t$ 代換後與 (\ref{hgf}) 相乘可得 \begin{align*} 1&=\prod_{i=1}^m(1-x_it)\prod_{i=1}^m\frac{1}{1-x_it}=\left(\sum_{n=0}^\infty (-1)^ne_nt^n\right)\left(\sum_{n=0}^\infty h_nt^n\right)\\ &=1+\sum_{n=1}^\infty\left(\sum_{k=0}^n(-1)^{n-k}h_{k}e_{n-k}\right)t^n \end{align*} 比較等號兩邊 $t^n$ 係數後得到對任意 $n\ge 1$ 都有 \begin{equation}\label{alterEH} \sum_{k=0}^n(-1)^{k}e_{k}h_{n-k}=0\qquad \mbox{ 或等價地 }\qquad h_n=\sum_{i=1}^n(-1)^{k-1}e_kh_{n-k} \end{equation} 這個公式讓我們利用遞迴的方式得到 $e_n$ 和 $h_n$ 之間的轉換, 以上是本文關於對稱多項式具備的知識, 實際上以上內容並沒有觸及對稱函數真正有趣的部份, 對這方面內容有興趣的讀者可以參考 Macdonald 或 Stanley 與 Fomin 的第七章。 有了這些預備知識後, 現在回到我們關心的 Fibonacci 數和 Padovan 數上, 我們已經知道 $\{F_n\}$ 和 $\{P_n\}$ 的遞迴式, 對這類遞迴式一般大學數學系離散數學或組合數學課程中有一套標準的方法可以讓我們得到 $\{F_n\}$ 和 $\{P_n\}$ 的生成函數 $$ \sum_{n\ge 0}F_n t^n=\frac{t}{1-t-t^2},~\qquad \sum_{n\ge 0}P_n t^n=\frac{1+t}{1-t^2-t^3}. $$

定理2.1 設 $\alpha_1,\alpha_2$ 為 $\{F_n\}$ 之遞迴式 $F_{n+2}=F_{n+1}+F_n$ 特徵多項式的兩根, 則對正整數 $n\ge 1$ 有 $$ F_n=h_n(\alpha_1,\alpha_2). $$

證明： 假設 $\alpha_1,\alpha_2$ 為 $\{F_n\}$ 的特徵方程 $t^2-t-1=0$ 之兩根, 觀察 $\{F_n\}$ 的生成函數注意到分母可改寫 $1-t-t^2=t^2(\frac{1}{t^2}-\frac{1}{t}-1)=(1-\alpha_1t)(1-\alpha_2t)$, 將其與 $h_n$ 的生成函數 (\ref{hgf}) 比較 $$ \sum_{n\ge 0}F_n t^n=\frac{t}{(1-\alpha_1t)(1-\alpha_2t)}=t\sum_{n=0}^\infty h_n(\alpha_1,\alpha_2)t^n=\sum_{n\ge 0} h_n(\alpha_1,\alpha_2)t^{n+1}, $$ 可以得到當 $n\ge 1$ 時有 $F_n=h_{n-1}(\alpha_1,\alpha_2)$。 $\Box$ 定理2.2. 設 $\beta_1,\beta_2,\beta_3$ 為 $\{P_n\}$ 之遞迴式 $P_{n+3}=P_{n+1}+P_n$ 特徵多項式的三根, 則對正整數 $n\ge 1$ 有 $$ P_n=h_{n+2}(\beta_1,\beta_2,\beta_3). $$

證明： 類似的方法可將 $\{P_n\}$ 的生成函數改寫並與 (\ref{hgf}) 比較得 \begin{align*} \sum_{n\ge 0}P_n t^n &=\frac{1+t}{(1-\beta_1t)(1-\beta_2t)(1-\beta_3t)} =(1+t)\sum_{n\ge 0}h_n(\beta_1,\beta_2,\beta_3)t^n\\ &=\sum_{n\ge 0}h_nt^n+\sum_{n\ge 0}h_n t^{n+1}, \end{align*} 故當 $n\ge 1$ 時有 $P_n=h_n(\beta_1,\beta_2,\beta_3)+h_{n-1}(\beta_1,\beta_2,\beta_3)$, 接下來同 中的做法利用 (\ref{alterEH}) 式可進一步化簡, 當 $n\ge 1$ 時有 $P_n=h_{n+2}(\beta_1,\beta_2,\beta_3)$。 $\Box$

3. 一般的 $k$ 階線性遞迴數列用 $h_n$ 表示

有了前一節的 $F_n$ 和 $P_n$ 的兩個例子, 現在我們來看更一般的情況。 給定初始值 $b_0,b_1,\ldots$, $b_{k-1}$, 考慮數列 $\{b_n\}$ 滿足 $k$ 階線性遞迴方程式 $$ b_n+a_1b_{n-1}+\cdots+a_{k-1}b_{n-k+1}+a_kb_{n-k}=0 ~(a_k\neq 0). $$ 用一般我們求數列生成函數的方法可以得到 $\{b_n\}$ 的生成函數為 $\sum_{n\ge 0}b_n t^n=\dfrac{p(t)}{q(t)}$, 其中 $$ q(t)=1+a_1t+\cdots+a_kt^k, $$ $$ p(t)=b_0+(b_1+a_1b_0)t+(b_2+a_1b_1+a_2b_0)t^2+\cdots+\left(b_{k-1}+\sum_{i=1}^{k-1}a_ib_{k-1-i}\right)t^{k-1}. $$ 同時 $\{b_n\}$ 之特徵多項式為 $$ r(t)=t^k+a_1t^{k-1}+\cdots+a_{k-1}t+a_k, $$ 可以發現 $q(t)$ 和 $r(t)$ 之間滿足 $q(t)=t^kr(\frac{1}{t})$, 我們稱 $q(t)$ 為 $r(t)$之reflected polynomial。 假設 $\alpha_1,\alpha_2,\ldots,\alpha_k$ 為 $r(t)$ 之 $k$ 個根, 這邊 $\alpha_i$ 不一定要相異, 則特徵多項式可分解為 $$ r(t)=(t-\alpha_1)(t-\alpha_2)\ldots(t-\alpha_k). $$ 由 $q(t)=t^kr(\frac{1}{t})$ 可知 $$ q(t)=(1-\alpha_1t)(1-\alpha_2t)\ldots(1-\alpha_kt), $$ 從而可以得到 \begin{align*} \sum_{n\ge 0}b_n t^n &=\frac{b_0\!+\!(b_1\!+\!a_1b_0)t\!+\!(b_2\!+\!a_1b_1\!+\!a_2b_0)t^2\!+\!\cdots+\left(b_{k-1}+\sum_{i=1}^{k-1}a_ib_{k-1-i}\right)t^{k-1}}{(1-\alpha_1t)(1-\alpha_2t)\ldots(1-\alpha_kt)}\\ &=\left[b_0\!+\!(b_1\!+\!a_1b_0)t\!+\!\cdots\!+\!\left(b_{k-1}\!+\!\sum_{i=1}^{k-1}a_ib_{k-1-i}\right)t^{k-1}\right]\sum_{n\ge 0}h_n(\alpha_1,\ldots,\alpha_k)t^n, \end{align*} 比較等號兩邊 $t^n$ 係數可知, 當 $n\ge k-1$ 時有 \begin{eqnarray*} b_n&=&b_0h_n(\alpha_1,\ldots,\alpha_k)+(b_1+a_1b_0)h_{n-1}(\alpha_1,\ldots,\alpha_k)+\cdots\\ &&+\left(b_{k-1}+\sum_{i=1}^{k-1}a_ib_{k-1-i}\right)h_{n-k+1}(\alpha_1,\ldots,\alpha_k). \end{eqnarray*} 將上面的結果整理後我們有以下定理

定理3.1. 令 $\{b_n\}$ 為一數列滿足 $k$ 階線性遞迴式 $$ b_n+a_1b_{n-1}+\cdots+a_{k-1}b_{n-k+1}+a_kb_{n-k}=0 ~(a_k\neq 0) $$ 並且給定 $b_0,b_1,\ldots,b_{k-1}$, 則其生成函數為 $$ \sum_{n\ge 0}b_n t^n\!=\!\frac{b_0+(b_1\!+\!a_1b_0)t\!+\!(b_2\!+\!a_1b_1\!+\!a_2b_0)t^2\!+\!\ldots+\left(b_{k-1} \!+\!\sum_{i=1}^{k-1}a_ib_{k-1-i}\right)t^{k-1}}{(1-\alpha_1t)(1-\alpha_2t)\ldots(1-\alpha_kt)}, $$ 其中 $\alpha_1,\ldots,\alpha_k$ 為 $t^k+a_1t^{k-1}+\cdots+a_{k-1}t+a_{k}=0$ 的 $k$ 個根, 並且當 $n\ge k-1$ 時有 \begin{eqnarray*} b_n&=&b_0h_n(\alpha_1,\ldots,\alpha_k)+(b_1+a_1b_0)h_{n-1}(\alpha_1,\ldots,\alpha_k)+\cdots\\ &&+\left(b_{k-1}+\sum_{i=1}^{k-1}a_ib_{k-1-i}\right)h_{n-k+1}(\alpha_1,\ldots,\alpha_k). \end{eqnarray*} 所以當 $k=2$ 時, 二階線性遞迴數列與完全齊次對稱多項式有以下關係 推論3.2. 令 $\{a_n\}$ 滿足二階線性遞迴式 $a_{n+2}=b a_{n+1}+ca_n$ 並給定初始值 $a_0$, $a_1$, 則其生成函數為 $$ \sum_{n\ge 0}a_n t^n=\frac{a_0+(a_1-ba_0)t}{(1-\alpha t)(1-\beta t)} $$ 其中 $\alpha,\beta$ 為 $t^2-bt-c=0$ 之兩根, 並且對 $n\ge 1$ 之 $a_n$ 有 $$ a_n=a_0h_n(\alpha,\beta)+(a_1-ba_0)h_{n-1}(\alpha,\beta). $$

類似地, 若滿足遞迴式的是多項式數列則有 推論3.3. 令多項式數列 $\{a_n(x)\}$ 滿足二階線性遞迴式 $a_{n+2}(x)=b(x)a_{n+1}(x)+c(x)a_n(x)$ 並給定初始值 $a_0(x)$, $a_1(x)$, 則其生成函數為 $$ \sum_{n\ge 0}a_n(x) t^n=\frac{a_0(x)+(a_1(x)-b(x)a_0(x))t}{(1-\alpha(x) t)(1-\beta(x) t)} $$ 其中 $\alpha(x),\beta(x)$ 為 $t^2-b(x)t-c(x)=0$ 之兩根, 並且對 $n\ge 1$ 有 $$ a_n(x)=a_0(x)h_n(\alpha(x),\beta(x))+(a_1(x)-b(x)a_0(x))h_{n-1}(\alpha(x),\beta(x)). $$

在 $k=3$ 時則有

推論3.4. 令 $\{a_n\}$ 滿足三階線性遞迴式 $a_{n+3}=b a_{n+2}+ca_{n+1}+da_n$ 並給定初始值 $a_0$, $a_1$, $a_2$, 則其生成函數為 $$ \sum_{n\ge 0}a_n t^n=\frac{a_0+(a_1-ba_0)t+(a_2-ba_1-ca_0)t^2}{(1-\alpha t)(1-\beta t)(1-\gamma t)} $$ 其中 $\alpha,\beta,\gamma$ 為 $t^3-bt^2-ct-d=0$ 之三根, 並且對 $n\ge 1$ 之 $a_n$ 有 $$ a_n=a_0h_n(\alpha,\beta,\gamma)+(a_1-ba_0)h_{n-1}(\alpha,\beta,\gamma)+(a_2-ba_1-ca_0)h_{n-2}(\alpha,\beta,\gamma). $$

若滿足遞迴式的是多項式則有 推論3.5. 令 $\{a_n(x)\}$ 滿足三階線性遞迴式 $a_{n+3}(x)=b(x)a_{n+2}(x)+c(x)a_{n+1}(x)+d(x)a_n(x)$ 並給定初始值 $a_0(x)$, $a_1(x)$, $a_2(x)$, 則其生成函數為 $$ \sum_{n\ge 0}a_n(x) t^n=\frac{a_0(x)+(a_1(x)-b(x)a_0(x))t+(a_2(x)-b(x)a_1(x)-c(x)a_0(x))t^2}{(1-\alpha(x) t)(1-\beta(x) t)(1-\gamma(x) t)}, $$ 其中 $\alpha(x),\beta(x),\gamma(x)$ 為 $t^3\!-\!b(x)t^2\!-\!c(x)t\!-\!d(x)\!=\!0$ 之三根, 並且對 $n\!\ge\! 2$ 之 $a_n(x)$ 有 \begin{eqnarray*} a_n(x)&=&a_0(x)h_n(\alpha,\beta,\gamma)+(a_1(x)-b(x)a_0(x))h_{n-1}(\alpha,\beta,\gamma)\\ &&+(a_2(x)-b(x)a_1(x)-c(x)a_0(x))h_{n-2}(\alpha,\beta,\gamma). \end{eqnarray*}

4. 生成函數方法證明卷積公式

這一節我們會利用生成函數的方法重新證明 (\ref{convol})。 已知 $\{F_n\}$ 和 $\{P_n\}$ 的遞迴式, 對這類遞迴式一般大學數學系離散數學或組合數學課程中有一套標準的方法可以讓我們得到 $\{F_n\}$ 和 $\{P_n\}$ 的生成函數 $$ \sum_{n\ge 0}F_n x^n=\frac{x}{1-x-x^2},~\qquad \sum_{n\ge 0}P_n x^n=\frac{1+x}{1-x^2-x^3}. $$ 並且我們所求卷積的數列 $\left\{\sum_{i=0}^n F_iP_{n-i}\right\}_{n\ge 0}$ 其對應生成函數為兩個原生成函數的乘積 \begin{equation}\label{gfconvol1} \sum_{n\ge 0}\left(\sum_{i=0}^n P_iF_{n-i}\right)x^n=\frac{x}{1-x-x^2}\cdot\frac{1+x}{1-x^2-x^3}. \end{equation} 假設 (\ref{gfconvol1}) 式等號右邊可以部份分式如下 $$ \frac{x}{1-x-x^2}\cdot\frac{1+x}{1-x^2-x^3}=\frac{Ax+B}{1-x-x^2}+\frac{ax^2+bx+c}{1-x^2-x^3}, $$ 於是等號兩邊同乘 $(1-x-x^2)(1-x^2-x^3)$ 後可得 $$ x(1+x)=(Ax+B)(1-x^2-x^3)+(ax^2+bx+c)(1-x-x^2) $$ 比較等號兩邊係數後我們知道 $a=-1$, $b=c=-2$, $A=1$, $B=2$。 因此(\ref{gfconvol1})式成為 \begin{equation}\label{gfconvol2} \sum_{n\ge 0}\left(\sum_{i=0}^n P_iF_{n-i}\right)x^n=\frac{2+x}{1-x-x^2}-\frac{2+2x+x^2}{1-x^2-x^3}. \end{equation} 觀察(\ref{gfconvol2})式等號右邊第一式可改寫為 $\dfrac{x}{1-x-x^2}+\dfrac{2}{1-x-x^2}$, 注意到 $\dfrac{1}{1-x-x^2}$ 為 $\{F_{n+1}\}_{n\ge 0}$ 之生成函數因為 $$ \frac{1}{1-x-x^2}=\frac{1}{x}\cdot\left(\frac{x}{1-x-x^2}-F_0\right)=\sum_{n\ge 0}F_{n+1}x^n, $$ 因此 $\dfrac{2+x}{1-x-x^2}$ 為 $\{F_n+2F_{n+1}=F_{n+2}+F_{n+1}=F_{n+3}\}_{n\ge 0}$ 之生成函數。

現在觀察 (\ref{gfconvol2}) 式等號右邊第二項, 注意到 $\{P_{n+1}\}_{n\ge 0}$ 之生成函數為 $$ \sum_{n\ge 0}P_{n+1}x^n=\frac{1}{x}\cdot\left(\frac{1+x}{1-x^2-x^3}-P_0\right)=\frac{1+x+x^2}{1-x^2-x^3}, $$ 所以 $\dfrac{2+2x+x^2}{1-x^2-x^3}$ 可改寫為 $\dfrac{1+x}{1-x^2-x^3}+\dfrac{1+x+x^2}{1-x^2-x^3}$ 即為 $\{P_n+P_{n+1}=P_{n+3}\}_{n\ge 0}$ 之生成函數。 因此我們得到 $$ \sum_{i=0}^nF_iP_{n-i}=F_{n+3}-P_{n+3}. $$ 以下我們給出另一個例子具有和$F_n$及$P_n$類似的卷積公式。 首先我們定義 Tribonacci 數 $T_n$ 滿足下列遞迴多項式 $$ T_{n+3}=T_{n+2}+T_{n+1}+T_n $$ 及初始條件 $T_0=0$, $T_1=T_2=1$, 容易可以得到 $\{T_n\}_{n\ge 0}$ 的生成函數為 $$ \sum_{n\ge 0}T_n x^n=\frac{x}{1-x-x^2-x^3}. $$ 考慮 $\{F_n\}_{n\ge 0}$ 和 $\{T_n\}_{n\ge 0}$ 的卷積 $\left\{\sum_{i=0}^nF_iT_{n-i}\right\}_{n\ge 0}$ 對應的生成函數, 一樣利用部分分式法有 $$ \frac{x}{1-x-x^2}\cdot\frac{x}{1-x-x^2-x^3}=-\frac{1+x}{1-x-x^2}+\frac{1+x+x^2}{1-x-x^2-x^3} $$ 其中由之前的討論知道 $\dfrac{1+x}{1-x-x^2}=\dfrac{1}{1-x-x^2}+\dfrac{x}{1-x-x^2}$ 為 $\{F_n+F_{n+1}=F_{n+2}\}_{n\ge 0}$ 之生成函數; 另一方面注意到 $$ \frac{1+x+x^2}{1-x-x^2-x^3}=\frac{1}{x^2}\left(\frac{x}{1-x-x^2-x^3}-T_0-T_1x\right)=\sum_{n\ge 0}T_{n+2}x^n, $$ 所以 $\dfrac{1+x+x^2}{1-x-x^2-x^3}$ 為 $\{T_{n+2}\}_{n\ge 0}$ 之生成函數,於是由這兩個結果我們得到 $$ \sum_{i=0}^n F_iT_{n-i}=T_{n+2}-F_{n+2}. $$

參考文獻

---本文作者廖信傑投稿時為美國 University of Miami 博士生,
薛昭雄任教於美國 University of Nevada, Las Vegas---