數學傳播

1. 引言

一個數列 $\{a_n\}_{n\geq 0}$ 滿足$$a_{n+2}=pa_{n+1}+qa_n$$ 其中 $a_0$, $a_1$, $p$, $q$ 為常數, $q\neq 0$, 且 $p$, $q$ 與 $n$ 無關, 被稱為 二階線性遞迴數列 (a number sequence of linear recurrence relation of order 2)。最常見的例子就是 Fibonacci 數列 $\{F_n\}_{n\geq 0}$ 滿足 $$F_{n+2}=F_{n+1}+F_{n}\mbox{，} F_0=1\mbox{，} F_1=1\mbox{。}$$ 長久以來數學家們已發現在 Fibonacci 數列上的諸多性質, 讀者可參考 Koshy 。 其中最令人感興趣的是 Fibonacci 數列與 Pascal 三角形 (或稱「楊輝三角形」, 「賈憲三角形」) 的關係 (請參考第 3 節)。 而 Pascal 三角形又和多項式 $(1+x)^n$ 展開式的係數有著密不可分的連結, 這份連結就自然而然地延伸到 Fibonacci 數列了。因此, 我們可以更廣泛地思考：對於一般的二階線性遞迴序列, 是否存在某種多項式, 能夠類似 Fibonacci 數列與 $(1+x)^n$ 有著不可分離的關係？答案是肯定的, 也是本文的主要目的之一。我們的目的有：

1. 我們將利用一般二階線性遞迴序列 (包含數列與多項式序列) 的生成函數 (請參考第 2 節) 與其一般表示式來定義序列的對應多項式, 且這樣的對應是一對一的。
2. 探討一般三階線性遞迴序列的對應多項式 (請參考第 3.3 節)。

2. 生成函數之基本性質與例子

數列 $\{a_n\}_{n\geq 0}$ 的生成函數 (the generating function) 定義為 $$A(t)=\sum_{n=0}^{\infty}a_n t^n\mbox{。}$$ $\star$注意, 這裡我們不考慮 $A(t)$ 的斂散性。

根據這個定義我們能夠知道, 如果有兩個數列的生成函數相同, 則這兩個數列的每一項都是相同的, 也就是說是相同的數列。對於生成函數, 我們會有如下的基本特性：

定理 1: 令 $\{a_n\}_{n\geq 0}$ 為一個二階線性遞迴數列滿足 $a_{n+2}=pa_{n+1}+qa_n$, 其中 $a_0$, $a_1$, $p$, $q$ 為常數, $q\neq 0$, 則其生成函數 $A(t)$ 為 \begin{equation}A(t)=\frac{a_0+(a_1-pa_0)t}{1-pt-qt^2}\label{eq1}\mbox{。}\end{equation}

證明: 我們考慮三個關係式 \begin{align*} A(t) &= a_0 + a_1 t +a_2 t^2\hskip 5pt +a_3 t^3 +\cdots\\ ptA(t) &= \quad\hspace{8pt} pa_0 t +pa_1 t^2 +pa_2 t^3 +\cdots\\ qt^2A(t) &= \qquad\qquad\hspace{8pt} qa_0 t^2 +qa_1 t^3 +\cdots \end{align*} 因為 $a_{n+2}=pa_{n+1}+qa_n$, 所以我們有 $$(1-pt-qt^2)A(t)=a_0 + (a_1-pa_0)t\mbox{。}$$ 將等號兩邊同除以 $(1-pt-qt^2)$, 可得到我們所要的 $A(t)$。

特別地, 當我們考慮二階線性遞迴多項式序列 $\{a_n(x)\}_{n\geq 0}$ 亦會有相同結果。

定理 2: 令 $\{a_n(x)\}_{n\geq 0}$ 為一個二階線性遞迴多項式序列滿足 $$a_{n+2}(x)=p(x)a_{n+1}(x)+q(x)a_n(x)\mbox{，}$$ 其中 $a_0(x)$, $a_1(x)$, $p(x)$, $q(x)$ 為變數 $x$ 的多項式， $q(x)\neq 0$, 則其生成函數 $\displaystyle A(t)=\sum_{n=0}^{\infty}a_n(x) t^n$ 可寫成 \begin{equation}A(t)=\frac{a_0(x)+(a_1(x)-p(x)a_0(x))t}{1-p(x)t-q(x)t^2}\mbox{。}\end{equation} 我們來看幾個例子, 以下是幾種有名的數列與多項式序列：

例子 1: 令 $\{F_n\}_{n\geq 0}$, $\{L_n\}_{n\geq 0}$ 與 $\{F_n(x)\}_{n\geq 0}$, $\{L_n(x)\}_{n\geq 0}$ 分別為 Fibonacci 和 Lucas 數列與 Fibonacci 和 Lucas 多項式序列 (請參考 Koshy ), 其中 $F_0=F_1=1$；$L_0=2$, $L_1=1$；$F_0(x)=1$, $F_1(x)=x$；$L_0(x)=2$, $L_1(x)=x$ 且滿足 \begin{align*}F_{n+2}&=F_{n+1}+F_n \hspace{6em} L_{n+2}=L_{n+1}+L_n \mbox{；}\\ F_{n+2}(x)&=xF_{n+1}(x)+F_n(x) \hspace{1.4em} L_{n+2}(x)=xL_{n+1}(x)+L_n(x)\mbox{。}\end{align*}

則根據定理 1 與 2 所求得的生成函數式子, 我們有

	$F_n$	$L_n$	$F_n(x)$	$L_n(x)$
生成函數	$\displaystyle\frac{1}{1-t-t^2}$	$\displaystyle\frac{2-t}{1-t-t^2}$	$\displaystyle\frac{1}{1-xt-t^2}$	$\displaystyle\frac{2-xt}{1-xt-t^2}$

例子 2: 令 $\{T^{(k)}_n(x)\}_{n\geq 0}$ 為第 $k$ 類 Chebyshev 多項式序列, $k=1$, $2$, $3$ 或 $4$ (請參考 Chen 和 Louck })。對任意的 $k$ 皆滿足 $T^{(k)}_0(x)=1$ 且 $$T^{(k)}_{n+2}(x)=2x\cdot T^{(k)}_{n+1}(x)-T^{(k)}_n(x)$$其中 $T^{(1)}_1(x)=x$， $T^{(2)}_1(x)=2x$， $T^{(3)}_1(x)=2x-1$ 和 $T^{(4)}_1(x)=2x+1$。 利用定理 2 的式子, 我們有生成函數分別為

$T^{(k)}_n(x)$	$T^{(1)}_n(x)$	$T^{(2)}_n(x)$	$T^{(3)}_n(x)$	$T^{(4)}_n(x)$
生成函數	$\displaystyle\frac{1-xt}{1-2xt+t^2}$	$\displaystyle\frac{1}{1-2xt+t^2}$	$\displaystyle\frac{1-t}{1-2xt+t^2}$	$\displaystyle\frac{1+t}{1-2xt+t^2}$

例子 3: 令 $\{D_n^{(1)}(x,a)\}_{n\geq 0}$ 與 $\{D_n^{(2)}(x,a)\}_{n\geq 0}$ 分別為第1類與第2類的 Dickson 多項式序列, $a\in\mathbb{R}$ (請參考 Lidl, Mullen 和 Turnwald )。二者皆滿足遞迴關係 $$D_{n+2}^{(i)}(x,a)=xD_{n+1}^{(i)}(x,a)-aD_n^{(i)}(x,a)\mbox{, }i=1\mbox{, }2$$ 其中 $D_0^{(1)}(x,a)=2$, $D_1^{(1)}(x,a)=x$ 和 $D_0^{(2)}(x,a)=1$, $D_1^{(2)}(x,a)=x$。 因此根據定理 2 所求得的式子, 我們有生成函數

$D^{(i)}_n(t)$	$D^{(1)}_n(t)$	$D^{(2)}_n(t)$
生成函數	$\displaystyle\frac{2-xt}{1-xt+at^2}$	$\displaystyle\frac{1}{1-xt+at^2}$

3. 對應多項式

現在考慮 Fibonacci 多項式 $\{F_n(x)\}_{n\geq 0}$。Bicknell 在 中指出, 當我們把 $F_n(x)$ 列出來 (見表 4)。 再把係數按照次序排好 (見表 5), 不考慮係數為 0 的數, 則會發現, 若將所有斜率為 1 的對角線順時針旋轉 $45^\circ$, 會形成 Pascal 三角形 (表 5 粗體部分與表 6)。

而 Pascal 三角形其實就與 $(x+1)^n$ 的各項係數是一樣的, 我們將 $(x+1)^n$ 展開並降冪排好 (見表 7), 一樣考慮所有斜率為 1 的對角線, 每條對角線左端點都剛好對應到一個 $n$, 將該對角線的所有元素累加恰好就是 $F_n(x)$, 例如表 7 中, $n=4$ 對應到右邊的粗體部分即為 $F_4(x)$。 事實上, 我們可以從 中所給的式子$$F_n(x)=\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n-i}{i} x^{n-2i}$$ 來看出這件事。 其中 $\binom{n-i}{i} x^{n-2i}$ 剛好是 $(x+1)^{n-i}$ 的某一項。

表4: $F_0(x)=1$ $F_1(x)=x$ $F_2(x)=x^2+1$ $F_3(x)=x^3+2x$ $F_4(x)=x^4+3x^2+1$ $F_5(x)=x^5+4x^3+3x$ $F_6(x)=x^6+5x^4+6x^2+1$ $\,\vdots$	表5: $n$ $x^0$$x^1$$x^2$$x^3$$x^4$$x^5$$x^6$ 0 1 2 3 4 5 6 $\vdots$ 1 0  1 1  0  1 0  2  0  1 1  0  3  0  1 0  3  0  4  0  1 1  0  6  0  5  0  1         $\vdots$
表6: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 $\vdots$	表7: $n$ $(x+1)^n$ 0 1 2 3 4 $\vdots$ 1 $x$   $x^2$  $2x$     $\boldsymbol{1}$ $x^3$  $\boldsymbol{3x^2}$  $3x$    1 $\boldsymbol{x^4}$  $4x^3$  $6x^2$  $4x$  $1$            $\vdots$

但是這種多項式序列 $\{F_n(x)\}_{n\geq 0}$ 與多項式 $(x+1)^n$ 之間的對應關係並不是足夠好的, 舉例來說： 考慮 Jacobsthal 多項式序列 $\{J_n(x)\}_{n\geq 0}$ (請參考 ), 其中 $J_0(x)=J_1(x)=1$， 並滿足 $$J_{n+2}(x)=J_{n+1}(x)+xJ_n(x)\mbox{。}$$ 則我們觀察 $\{J_n(x)\}_{n\geq 0}$ 與多項式 $(1+x)^n$ 展開後升冪排列之關係, 如下

表8: $J_0(x)=1$ $J_1(x)=1$ $J_2(x)=1+x$ $J_3(x)=1+2x$ $\boldsymbol{J_4(x)}\boldsymbol{=1+3x+x^2}$ $\,\,\,\vdots$

表9: $n$ $(1+x)^n$ 0 1 2 3 4 $\vdots$ 1 1  $x$ 1  $2x$  $\boldsymbol{x^2}$ 1  $\boldsymbol{3x}$  $3x^2$    $x^3$ $\boldsymbol{1}$  $4x$  $6x^2$   $4x^3$   $x^4$            $\vdots$

事實上, $$J_n(x)=\sum_{i=0}^{\lfloor\frac{n}{2}\rfloor}\binom{n-i}{i}x^i\mbox{。}$$ 因此, $\{F_n(x)\}_{n\geq 0}$ 與 $\{J_n(x)\}_{n\geq 0}$ 對應至同一個多項式。 也就是說在這樣的對應之下, 若給定一個與序列 $\{a_n(x)\}_{n\geq 0}$ 對應的多項式 $\mathcal{P}_n(x)$, 則我們無法判斷原先序列 $\{a_n(x)\}_{n\geq 0}$ 的樣子為何。因此我們接下來的目的就是要改善這樣的情形, 我們將利用二階線性遞迴的一般項表示式, 來定義一個可以與序列一一對應的多項式, 也就是說不同的序列會對應至不同的多項式。

3.1. 二階線性遞迴的一般項表示式

定理 3: 令 $\{a_n\}_{n\geq 0}$ 為一個二階線性遞迴數列, 且 $a_0$, $a_1$, $p$, $q$ 為已知, $q\neq 0$, 滿足 $a_{n+2}=pa_{n+1}+qa_n$。 則 \begin{align*} a_n=a_0 \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n-k}{k} {p}^{n-2k} {q}^{k} + \left(a_1-pa_0\right) \sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor} \binom{n-1-k}{k} {p}^{n-1-2k} {q}^{k}\mbox{, }n\geq 1\mbox{。} \end{align*}

證明: 首先令 $$f(t)=\frac{1}{1-pt-qt^2}\mbox{，}$$ 則我們有 \begin{align*} f(t)=\frac{1}{1-pt-qt^2}&=\frac{1}{1-\left(pt+qt^2\right)}\\ &=\sum_{n=0}^{\infty}\left(pt+qt^2\right)^n =\sum_{n=0}^{\infty}\left(\sum_{k=0}^n \binom{n}{k}\left(pt\right)^{n-k} \left(qt^2\right)^k\right)\\ &=\sum_{n=0}^{\infty}\left(\sum_{k=0}^n \binom{n}{k}{p}^{n-k} {q}^k t^{n+k}\right)\mbox{，} \end{align*} 我們改變足標即可得到 \begin{equation} f(t)=\sum_{n=0}^{\infty}\left(\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n-k}{k}{p}^{n-2k} {q}^k\right) t^{n}\mbox{。} \label{subsec1lem1pf} \end{equation} 現在, 令 $A(t)$ 為 $\{a_n\}_{n\geq 0}$ 的生成函數。利用定理 1 與式子 (\ref{subsec1lem1pf}), 則 \begin{align*}A(t)&=\frac{a_0+(a_1-pa_0)t}{1-pt-qt^2}\\ &=a_0f(t)+(a_1-pa_0)tf(t)\\&=a_0\sum_{n=0}^{\infty}\left(\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n\!-\!k}{k}{p}^{n-2k} {q}^k\right) t^{n}\!+\!(a_1\!-\!pa_0)\sum_{n=0}^{\infty}\left(\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n\!-\!k}{k}{p}^{n-2k} {q}^k\right) t^{n+1}\mbox{。}\end{align*} $t^n$ 的係數即是我們所要的 $a_n$, 所以 $$a_n=a_0 \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n-k}{k} {p}^{n-2k} {q}^{k} + \left(a_1-pa_0\right) \sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor} \binom{n-1-k}{k} {p}^{n-1-2k} {q}^{k}\mbox{, }n\geq 1\mbox{。}$$

同樣地, 利用相同的證明, 對於二階線性遞迴多項式序列我們也會有相似的結果。 ^{1 1} $^1$$a_n$ 的一般表示式並不唯一, 一個強而有力的方法是利用二次方程式 $X^2-pX-q=0$ 之根式解, 進而得到另一個一階線性遞迴關係式以求得 $a_n$ (請參考 )。

定理 4: 令 $\{a_n(x)\}_{n\geq 0}$ 為一個二階線性遞迴多項式序列, 且 $a_0(x)$, $a_1(x)$, $p(x)$, $q(x)$ 為已知, $q(x)\neq 0$, 滿足 $a_{n+2}(x)=p(x)a_{n+1}(x)+q(x)a_n(x)$。 則 \begin{align*} a_n(x)&=a_0(x) \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n-k}{k} {p(x)}^{n-2k} {q(x)}^{k} \\&\quad + \left(a_1(x)-p(x)a_0(x)\right) \sum_{k=0}^{\lfloor\frac{n-1}{2}\rfloor} \binom{n-1-k}{k} {p(x)}^{n-1-2k} {q(x)}^{k}\mbox{, }n\geq 1\mbox{。} \end{align*}

觀察定理 3 的式子中之 $\displaystyle\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n-k}{k} {p}^{n-2k} {q}^{k}$, 其實是將 $(p+q)^n$ 展開後斜率為 1 之加總, 即

表10: $n=0\mbox{：} 1$ $n=1\mbox{：} p$ $n=2\mbox{：} p^2+q$ $n=3\mbox{：} \boldsymbol{p^3+2pq}$ $\,\,\,\,\vdots$

表11: $n$ $(p+q)^n$ 0 1 2 3 $\vdots$ 1 $p$  $\,\,\,\,\,q$ $p^2$  $\boldsymbol{2pq}$ $\boldsymbol{p^3}$  $\cdots$ $\,\,\,\,\,\,\vdots$

因此， $a_n$ 會與 $$a_0(p+q)^n+(a_1-pa_0)(p+q)^{n-1}=(p+q)^{n-1}(a_1+qa_0)$$ 有類似的關係。根據這個觀察, 我們就可以定義出對應的規則。

3.2. 二階線性遞迴之對應多項式

定義 5: 沿用定理 3 的二階線性遞迴數列 $\{a_n\}_{n\geq 0}$。我們定義 $\mathcal{CP}_m\left(X,\{a_n\}_{n\geq 0}\right)$, $m\geq 0$, 為 $\{a_n\}_{n\geq 0}$ 的對應多項式 (corresponding polynomial) 滿足：

1. $\mathcal{CP}_0\left(X,\{a_n\}_{n\geq 0}\right)=a_0$；
2. $\mathcal{CP}_m\left(X,\{a_n\}_{n\geq 0}\right)=(p+qX)^{m-1}(a_1+qa_0X)$, 當 $m\geq 1$。

若 $\{a_n\}_{n\geq 0}$ 為已知, 則我們將對應多項式簡記為 $\mathcal{CP}_m(X)$。並且以符號 $$\{a_n\}_{n\geq 0}\rightarrow \mathcal{CP}_m(X)$$ 表示其對應。我們也會用 $$\{a_n\}_{n\geq 0}\rightarrow \mathcal{CP}_m(X),\mathcal{CP}_0(X)$$ 來特別表示 $m=0$ 的情形。

特別地, 若 $\{a_n\}_{n\geq N}$, $N\in\mathbb{N}$, 則 $m\geq N$, 且 $\mathcal{CP}_N\left(X\right)=a_N$ 和
$\mathcal{CP}_m\left(X\right)=(p+qX)^{m-1-N}(a_1+qa_0X)$, 當 $m\geq N+1$。

接下來的引理代表其「對應」的意義：

引理 6: 令 $\{a_n\}_{n\geq 0}\rightarrow \mathcal{CP}_m(X)$, 則 $$a_n=\sum_{k\geq0} [X^k]\left(\mathcal{CP}_{n-k}(X)\right)\mbox{, }n\geq 0 \mbox{, }$$ 其中 $[X^k]\left(\mathcal{CP}_{n-k}(X)\right)$ 是指在 $\mathcal{CP}_{n-k}\left(X\right)$ 中 $X^k$ 項的係數。

證明: 已知 $a_0=[X^0]\left(a_0\right)=[X^0]\left(\mathcal{CP}_{0}\left(X\right)\right)$。當 $n\geq 1$, \begin{align*} \mathcal{CP}_n\left(X\right)&=(p+qX)^{n-1}(a_1+qa_0X)\\ &=a_0(p+qX)^n+(a_1-pa_0)(p+qX)^{n-1}\\ &=a_0 \sum_{l=0}^{n} \binom{n}{l} {p}^{n-l} {q}^{l}X^l + \left(a_1-pa_0\right) \sum_{l=0}^{n-1} \binom{n-1}{l} {p}^{n-1-l} {q}^{l}X^l\mbox{。} \end{align*} 所以 $$[X^k]\left(\mathcal{CP}_{n-k}(X)\right)=a_0\binom{n-k}{k} {p}^{n-2k} {q}^{k}+(a_1-pa_0)\binom{n-k-1}{k} {p}^{n-2k-1} {q}^{k}\mbox{。}$$ 因此 \begin{align*} \sum_{k\geq0} [X^k]\left(\mathcal{CP}_{n-k}(X)\right)&=\sum_{k\geq0} \left(a_0\binom{n-k}{k} {p}^{n-2k} {q}^{k}+(a_1-pa_0)\binom{n-k-1}{k} {p}^{n-2k-1} {q}^{k}\right)\\ &=a_0 \sum_{k=0}^{\lfloor\frac{n}{2}\rfloor} \binom{n\!-\!k}{k} {p}^{n-2k} {q}^{k} \!+\! \left(a_1\!-\!pa_0\right) \sum_{k=0}^{\lfloor\frac{n\!-\!1}{2}\rfloor} \binom{n\!-\!k\!-\!1}{k} {p}^{n-2k-1} {q}^{k}\mbox{。} \end{align*} 從定理 3 我們可以得到 $$a_n=\sum_{k\geq0} [X^k]\left(\mathcal{CP}_{n-k}(X)\right)\mbox{。}$$

因此, 在定義 5 中, 我們所謂「對應」的意思即為：$a_n$ 就相當於以 $\mathcal{CP}_n(X)$ 為首, 將斜率為 $1$ 之各項係數累加， 例如 $a_3=[X^0]\left(\mathcal{CP}_{3}(X)\right)+[X^1]\left(\mathcal{CP}_{2}(X)\right)=p^2a_1+(pqa_0+qa_1)$ (見表12 與13 粗體字部分)。

表12: $a_0=a_0$ $a_1=a_1$ $a_2=pa_1+qa_0$ $\boldsymbol{a_3}\boldsymbol{=p^2a_1+(pqa_0+qa_1)}$ $\,\,\,\,\,\,\vdots$

表13: $m$ $\,\,\,\,X^0$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,X^1$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,X^2$$\,\,\,\,\cdots$ $\mathcal{CP}_0(X)$ $\mathcal{CP}_1(X)$ $\mathcal{CP}_2(X)$ $\boldsymbol{\mathcal{CP}_3(X)}$ $\vdots$ $\,\,a_0$ $\,\,a_1$$\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,qa_0$ $\,\,pa_1$$\,\,\,\,\,\,\boldsymbol{pqa_0+qa_1}$$\,\,\,\,q^2a_0$ $\,\,\boldsymbol{p^2a_1}$$\,\,\,\,\,\,\,\,\,\cdots$ $\,\,\,\,\,\,\,\vdots$

根據對應多項式的定義我們可以知道任何的二階線性遞迴數列皆可找到其對應多項式。接著我們要說明, 從對應多項式可以對應回唯一的一個二階線性遞迴數列, 也就是說這樣的對應是一個好的對應。

引理 7: 令 $\{a_n\}_{n\geq 0}$ 與 $\{b_n\}_{n\geq 0}$ 為兩個二階線性遞迴數列滿足 $$a_{n+2}=pa_{n+1}+qa_n\mbox{與}b_{n+2}=p'b_{n+1}+q'b_n\mbox{，}$$ 其中 $a_0$, $a_1$, $p$, $q$, $b_0$, $b_1$, $p'$, $q'$ 已知, $q\neq 0$, $q'\neq 0$。 令 $$\{a_n\}_{n\geq 0}\rightarrow \mathcal{CP}_m\left(X,\{a_n\}_{n\geq 0}\right)\mbox{與}\{b_n\}_{n\geq 0}\rightarrow \mathcal{CP}_m\left(X,\{b_n\}_{n\geq 0}\right)\mbox{。}$$ 如果對所有 $m\geq 0$ 我們都有 $\mathcal{CP}_m\left(X,\{a_n\}_{n\geq 0}\right)=\mathcal{CP}_m\left(X,\{b_n\}_{n\geq 0}\right)$, 則 $a_n=b_n$, 對所有 $n\geq 0$, 也就是說兩數列相同。

證明: 因為對所有 $m\geq 0$, $\mathcal{CP}_m\left(X,\{a_n\}_{n\geq 0}\right)=\mathcal{CP}_m\left(X,\{b_n\}_{n\geq 0}\right)$, 根據引理 6 我們可以得到 $$a_n=\sum_{k\geq0} [X^k]\left(\mathcal{CP}_{n-k}(X),\{a_n\}_{n\geq 0}\right)=\sum_{k\geq0} [X^k]\left(\mathcal{CP}_{n-k}(X),\{b_n\}_{n\geq 0}\right)=b_n\mbox{。}$$

引理 7 說明了數列與對應多項式可以一一對應, 所以我們可以將對應符號改寫為 $$\{a_n\}_{n\geq 0}\leftrightarrow \mathcal{CP}_m(X)$$ 表示其對應。我們來看一個與 Pascal 三角形相關的例子：

例子 4: 令 $a_0=1\mbox{，} a_1=p$， 且 $a_{n+2}=pa_{n+1}+qa_n$ 則從定義 5 我們有 $$\{a_n\}_{n\geq 0}\leftrightarrow (p+qX)^m\mbox{。}$$

表14: $a_0=1$ $a_1=p$ $a_2=p^2+q$ $\boldsymbol{a_3}\boldsymbol{=p^3+2pq}$ $\,\,\,\,\,\,\vdots$

表15: $m$ $X^0$$\,\,X^1$$\,\,X^2$$\,\,\cdots$ $(p+qX)^0$ $(p+qX)^1$ $(p+qX)^2$ $\boldsymbol{(p+qX)^3}$ $\vdots$ 1 $p$$\,\,\,\,\,\,\,\,q$ $p^2$$\,\,\boldsymbol{2pq}$$\,\,q^2$ $\boldsymbol{p^3}$$\,\,\cdots$ $\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\vdots$

我們將表15 的對應改寫成三角形的樣子 $$\begin{array}{ccccccccc} &&&& 1 &&&&\\ &&&\swarrow & & \searrow&&&\\ &&p & & & & q&&\\ &\swarrow& &\searrow& & \swarrow & &\searrow&\\ p^2 &&&& 2pq &&&&q^2\\ \end{array}$$ 往左邊的方向是乘以一個 $p$ 往下累加， 往右邊則是乘以一個 $q$ 。 當 $p=q=1$ 時, 即為 Fibonacci 數列與 Pascal 三角形的對應關係， 而 $a_n$ 就恰好為 $F_n$。

事實上, 依相同的方法我們亦可定義出一般二次線性遞迴多項式序列的對應多項式：

定義 8: 沿用定理 4

1. $\mathcal{CP}_0\left(X,\{a_n(x)\}_{n\geq 0}\right)=a_0(x)$；
2. $\mathcal{CP}_m\left(X,\{a_n(x)\}_{n\geq 0}\right)=(p(x)+q(x)X)^{m-1}(a_1(x)+q(x)a_0(x)X)$, 當 $m\geq 1$。

我們可以利用對應多項式做個簡單的應用： 例子

5: 考慮多項式序列 $\{w_n(x,y)=\frac{x^{n+1}-y^{n+1}}{x-y}\}_{n\geq 0}$, 不難驗證 $\{w_n(x,y)\}$ 為一個二階線性遞迴滿足 $$w_{n+2}(x,y)=(x+y)w_{n+1}(x,y)-xyw_n(x,y)$$ 且 $w_0(x,y)=1$， $w_1(x,y)=x+y$， 則根據定義 8 我們可以得到 $$w_n(x,y)\leftrightarrow ((x+y)-xyX)^m\mbox{。}$$ 令 $x+y=1$， $-xy=1$, 則可解得 $x=\frac{1+\sqrt{5}}{2}$， $y=\frac{1-\sqrt{5}}{2}$, 所以得到 $$w_n\left(\frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}\right)\leftrightarrow (1+X)^m\mbox{。}$$ 注意到 $\{F_n\}_{n\geq 0}\leftrightarrow (1+X)^m$ (請參考例子 6), 因此根據對應多項式的唯一性我們就會有 $w_n\left(\frac{1+\sqrt{5}}{2},\frac{1-\sqrt{5}}{2}\right)=F_n$, 也就是說 $$F_n=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{n+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{n+1}\right)\mbox{。}$$

我們在以下列出一些常見的數列與多項式序列所的對應多項式。

例子 6: 令 $\{a_n\}_{n\geq 0}$ 為數列或多項式序列滿足 $a_{n+2}=pa_{n+1}+qa_n$。 從例子 1, 2, 3 和 Jacobsthal 多項式我們可以得到

表16: \begin{eqnarray*} \{a_n\}_{n\geq 0} & (a_0,a_1,p,q) & \leftrightarrow & \mathcal{CP}_m(X),\mathcal{CP}_0(X) \\\hline \{F_n\}_{n\geq 0} & (1,1,1,1) & \leftrightarrow & (1+X)^m,1\\ \{L_n\}_{n\geq 0} & (2,1,1,1) & \leftrightarrow & (1+X)^{m-1}(1+2X),2\\ \{P_n\}_{n\geq 0} & (0,1,2,1) & \leftrightarrow & (2+X)^{m-1},0\\ \{F_n(x)\}_{n\geq 0} & (1,x,x,1) & \leftrightarrow & (x+X)^m,1\\ \{L_n(x)\}_{n\geq 0} & (2,x,x,1) & \leftrightarrow & (x+X)^{m-1}(x+2X)),2\\ \{J_n(x)\}_{n\geq 0} & (1,1,1,x) & \leftrightarrow & (1+xX)^{m},1\\ \{T^{(1)}_n(x)\}_{n\geq 0} & (1,x,2x,-1) & \leftrightarrow & (2x-X)^{m-1}(x-X),1\\ \{T^{(2)}_n(x)\}_{n\geq 0} & (1,2x,2x,-1) & \leftrightarrow & (2x-X)^{m},1\\ \{T^{(3)}_n(x)\}_{n\geq 0} & (1,2x-1,2x,-1) & \leftrightarrow & (2x-X)^{m-1}(2x-1-X),1\\ \{T^{(4)}_n(x)\}_{n\geq 0} & (1,2x+1,2x,-1) & \leftrightarrow & (2x-X)^{m-1}(2x+1-X),1\\ \{D^{(1)}_n(x,a)\}_{n\geq 0} & (2,x,x,-a) & \leftrightarrow & (x-aX)^{m-1}(x-2aX),2\\ \{D^{(2)}_n(x,a)\}_{n\geq 0} & (1,x,x,-a) & \leftrightarrow & (x-aX)^{m},1\\ \{\mathcal{B}_n(x,r)\}_{n\geq 0} & (1,x+r+1,x+2,-1) & \leftrightarrow & \left((x+2)-X\right)^{m-1}\left((x+r+1)-X\right),1\\ \{B_n(x)\}_{n\geq 0} & (1,x+2,x+2,-1) & \leftrightarrow & \left((x+2)-X\right)^{m},1\\ \{b_n(x)\}_{n\geq 0} & (1,x+1,x+2,-1) & \leftrightarrow & \left((x+2)-X\right)^{m-1}\left((x+1)-X\right),1\\ \{W_n(x,y)\}_{n\geq 0} & (2,x+y,x+y,-xy) & \leftrightarrow & \left((x+y)-xyX\right)^{m-1}((x+y-2xyX),2\\ \{w_n(x,y)\}_{n\geq 0} & (1,x+y,x+y,-xy) & \leftrightarrow & \left((x+y)-xyX\right)^{m},1\\ \end{eqnarray*} 其中

• $\{P_n\}_{n\geq 0}$ 為 Pell 數列 (請參考 )。
• $\{\mathcal{B}_n(x,r)\}_{n\geq 0}$ 為廣義的 Morgan-Voyce 多項式序列, $r\in\mathbb{R}$ (請參考 André-Jeannin ), $\{B_n(x)=\mathcal{B}_n(x,1)\}_{n\geq 0}$ 與 $\{b_n(x)=\mathcal{B}_n(x,0)\}_{n\geq 0}$ 為古典的 Morgan-Voyce 多項式序列。
• $W_n(x,y)=x^n+y^n$ 和 $w_n(x,y)=\frac{x^{n+1}-y^{n+1}}{x-y}$， 不難驗證兩者滿足遞迴關係 \begin{align*}W_{n+2}(x,y)&=(x+y)W_{n+1}(x,y)-xyW_n(x,y);\\ w_{n+2}(x,y)&=(x+y)w_{n+1}(x,y)-xyw_n(x,y)\mbox{。}\end{align*} 事實上, 定理 4 與定義 8 皆可應用至多變數多項式函數, 而不改其性質。因此我們可以仿照定理 4 的一般項表示來求得 \begin{align*}x^n+y^n&=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}(-1)^k\frac{n}{n-k}\binom{n-k}{k}(x+y)^{n-2k}(xy)^k;\\ \frac{x^{n+1}-y^{n+1}}{x-y}&=\sum_{k=0}^{\lfloor\frac{n}{2}\rfloor}(-1)^k\binom{n-k}{k}(x+y)^{n-2k}(xy)^k\mbox{。}\end{align*} 這就是著名的 Girard-Waring 公式 (請參考 )。

3.3. 三階線性遞迴之對應多項式

現在, 我們將利用先前的概念來定義一般三階線性遞迴的對應多項式。

定義 9: 令 $\{a_n\}_{n\geq 0}$ 為三階線性遞迴數列滿足 $$a_{n+3}=pa_{n+2}+qa_{n+1}+ra_{n}$$ 其中 $a_0$, $a_1$, $a_2$, $p$, $q$, $r$ 為已知, $r\neq 0$。 定義 $\{a_n\}_{n\geq 0}$ 的對應多項式 $\mathcal{CP}_m(X)$ (或 $\mathcal{CP}_m(X,\{a_n\}_{n\geq 0})$) 滿足：

1. $\mathcal{CP}_0(X)=a_0\mbox{；}$
2. $\mathcal{CP}_1(X)=a_1+qa_0X+ra_0X^2\mbox{；}$
3. $\mathcal{CP}_m(X)=a_0(p+qX+rX^2)^m+(a_1-pa_0)(p+qX+rX^2)^{m-1}\\ +(a_2-pa_1-qa_0)(p+qX+rX^2)^{m-2}, m\geq 2\mbox{。}$

記為 $\{a_n\}_{n\geq 0}\rightarrow \mathcal{CP}_m(X)$ 。

接著我們要說明兩者的對應關係, 相當於要證明 $$a_n=\sum_{k\geq 0} [X^k]\left(\mathcal{CP}_{n-k}(X)\right),\forall n\geq 0\mbox{。}$$ 在證明這件事之前, 我們需要引用多項式定理 (multinomial theorem) 與 $a_n$ 的一般表示式。

定理 10:[多項式定理 ] 對於任意的正整數 $m$ 與非負整數 $n$, 我們皆有 $$(x_1+x_2+\cdots +x_m)^n=\sum_{\substack{k_1+k_2+\cdots +k_m=n \\ k_1,\ldots ,k_m \geq 0}}\binom{n}{k_1,k_2,\ldots ,k_{m}}{x_1}^{k_1}{x_2}^{k_2}\cdots {x_m}^{k_m}$$ 其中 $\binom{n}{k_1,k_2,\ldots ,k_{m}}=\frac{n!}{k_1!k_2!\cdots k_{m}!}$ 。

引理 11:[Chou, Hsu 和 Shiue ] 令 $\{a_n\}_{n\geq 0}$ 滿足定義 9 的遞迴關係式且令 $c_0=a_0$， $c_1=(a_1-pa_0)$， $c_2=(a_2-pa_1-qa_0)$, 則可以得到 \begin{equation}a_n=\sum_{i=0}^{2}c_i\sum_{\substack{k_1+2k_2+3k_3=n-i\\ k_1+k_2 +k_{3}=k\\ k_1,k_2 ,k_{3}\geq 0}}\binom{k}{k_1,k_2 ,k_{3}}p^{k_1}q^{k_2}r^{k_{3}}\mbox{, 對所有可能的} k\mbox{。}\label{sec2sub3eq2}\end{equation} 當 $n-i\lt 0$ 時, 右邊的和定義為 $0$。

注意到在引理 11 裡, $k_1+k_2 +k_{3}$ 的上界為 $n-i$, 也就是說 $0\leq k\leq n-i$, 所以我們能夠將 $k\rightarrow n-i-k$ 以得到 $k_1+k_2 +k_{3}=n-i-k$ 而不改變 $k$ 值的所有可能性, 因此 $a_n$ 的一般表示式 (\ref{sec2sub3eq2}) 可改寫為 \begin{equation}a_n=\sum_{i=0}^{2}c_i\sum_{\substack{k_1+2k_2+3k_3=n-i\\ k_1+k_2 +k_{3}=n-i-k\\ k_1,k_2 ,k_{3}\geq 0}}\binom{n-i-k}{k_1,k_2 ,k_{3}}p^{k_1}q^{k_2}r^{k_{3}}\mbox{, 對所有可能的} k\mbox{。}\label{sec2sub3eq1}\end{equation}

接著我們就會有最重要的對應關係式：

引理 12: 令 $\{a_n\}_{n\geq 0}$ 滿足定義 9 的遞迴關係式， 則 $$a_n=\sum_{k\geq 0} [X^k]\left(\mathcal{CP}_{n-k}(X)\right),\forall n\geq 0\mbox{。}$$

證明: 當 $0\leq n\lt 2$ 時, 從定義 9 我們可以得到 \begin{align*} a_0&=[X^0]\left(a_0\right)=[X^0]\left(\mathcal{CP}_{0}\left(X\right)\right) \mbox{和} \\ a_1&=[X^0](a_1+qa_0X+ra_0X^2)+[X^1](a_0)=[X^0]\left(\mathcal{CP}_1(X)\right)+[X^1]\left(\mathcal{CP}_0(X)\right)\mbox{。}\end{align*} 當 $n\geq 2$ 時， 令 $c_0=a_0$， $c_1=(a_1-pa_0)$， $c_2=(a_2-pa_1-qa_0)$， 則從定義 9 和多項式定理我們有 \begin{align*} &\mathcal{CP}_{n-k}(X)\\ &=c_0(p+qX+rX^2)^{n-k}+c_1(p+qX+rX^2)^{n-k-1} +c_2(p+qX+rX^2)^{n-k-2}\\ &=\sum_{i=0}^2 c_i (p+qX+rX^2)^{n-k-i}\\ &=\sum_{i=0}^2 c_i\sum_{\substack{k_1+k_2 +k_{3}=n-k-i \\ k_1,k_2 ,k_{3} \geq 0}}\binom{n-k-i}{k_1,k_2 ,k_{3}}{p}^{k_1}{q}^{k_2}{r}^{k_{3}}X^{k_2+2k_3}\mbox{。} \end{align*} 因此 \begin{align*} &\sum_{k\geq 0}[X^k]\left(\mathcal{CP}_{n-k}(X)\right)\\ &=\sum_{k\geq 0}\sum_{i=0}^{2}c_i\sum_{\substack{k_1+k_2 +k_{3}=n-k-i \\ k_2+2k_3=k \\ k_1,k_2 ,k_{3} \geq 0}}\binom{n-k-i}{k_1,k_2 ,k_{3}}{p}^{k_1}{q}^{k_2} {r}^{k_{3}}\\ &=\sum_{i=0}^{2}c_i\sum_{\substack{k_1+2k_2+3k_3=n-i \\k_1+k_2 +k_{3}=n-k-i \\ k_1,k_2 ,k_{3} \geq 0}}\binom{n-k-i}{k_1,k_2 ,k_{3}}{p}^{k_1}{q}^{k_2} {r}^{k_{3}}\mbox{, 對所有可能的} k\mbox{。} \end{align*} 所以從式子 (\ref{sec2sub3eq1}) 我們就有 $$a_n=\sum_{k\geq 0} [X^k]\left(\mathcal{CP}_{n-k}(X)\right),\forall n\geq 0\mbox{。}$$

同樣地, 我們也會有對應多項式對應至數列的唯一性：

引理 13: 令 $\{a_n\}_{n\geq 0}$ 與 $\{b_n\}_{n\geq 0}$ 為兩個三階線性遞迴數列滿足 \begin{align*}a_{n+3}&=pa_{n+2}+qa_{n+1}+ra_{n}\mbox{和}\\ b_{n+3}&=p'b_{n+2}+q'b_{n+1}+r'b_{n}\end{align*} 且令 $$\{a_n\}_{n\geq 0}\rightarrow \mathcal{CP}_m\left(X,\{a_n\}_{n\geq 0}\right)~\mbox{與}~\{b_n\}_{n\geq 0}\rightarrow \mathcal{CP}_m\left(X,\{b_n\}_{n\geq 0}\right)\mbox{。}$$ 如果對所有 $m\geq 0$ 我們都有 $\mathcal{CP}_m\left(X,\{a_n\}_{n\geq 0}\right)=\mathcal{CP}_m\left(X,\{b_n\}_{n\geq 0}\right)$, 則 $a_n=b_n$, 對所有 $n\geq 0$, 也就是說兩序列相同。

證明: 同引理 7 的證明。

實際上我們可效仿定義 8, 將定義 9 推廣至一般三階線性遞迴的多項式序列 $\{a_n(x)\}_{n\geq 0}$。最後, 我們列出一些常見的三階遞迴關係之對應多項式。

例子 7: 令 $\{a_n\}_{n\geq 0}$ 為一般三階線性遞迴數列或多項式序列, 滿足 $a_{n+3}=pa_{n+2}+qa_{n+1}ra_n$。則從定義 9 有 表17: \begin{eqnarray*} \{a_n\}_{n\geq 0} & (a_0,a_1,a_2,p,q,r) & \leftrightarrow & \mathcal{CP}_m(X),\mathcal{CP}_0(X),\mathcal{CP}_1(X) \\\hline \{T_n\}_{n\geq 0} & (0,1,1,1,1,1) & \leftrightarrow & (1\!+\!X\!+\!X^2)^{m\!-\!1},0,1\\ \{(Pa)_n\}_{n\geq 0} & (1,1,1,0,1,1) & \leftrightarrow & (X\!+\!X^2)^{m\!-\!1}(1\!+\!X\!+\!X^2),1,(1\!+\!X\!+\!X^2)\\ \{(Pe)_n\}_{n\geq 0} & (3,0,2,0,1,1) & \leftrightarrow & (X\!+\!X^2)^{m\!-\!2}(\!-\!1\!+\!3X^2\!+\!6X^3\!+\!3X^4),3,(3X\!+\!3X^2)\\ \{F_nF_{n\!+\!1}\}_{n\geq 0} & (1,2,6,2,2,\!-\!1) & \leftrightarrow & (2\!+\!2X\!-\!X^2)^{m},1,(2\!+\!2X\!-\!X^2)\\ \{T_n(x)\}_{n\geq 0} & (0,1,x^2,x^2,x,1) & \leftrightarrow & (x^2\!+\!xX\!+\!X^2)^{m-1},0,1 \end{eqnarray*} 其中

• $\{T_n\}_{n\geq 0}$ 與 $\{T_n(x)\}_{n\geq 0}$ 為 tribonacci 數列與多項式序列 (請參考 )。
• $\{(Pa)_n\}_{n\geq 0}$ 為 Padovan 數列 (請參考 和 )。
• $\{(Pe)_n\}_{n\geq 0}$ 為 Perrin 數列 (請參考 )。
• $\{F_n\}_{n\geq 0}$ 為 Fibonacci 數列。 更一般來說, 若二階線性遞迴數列 $\{a_n\}_{n\geq 0}$ 滿足 $a_{n+2}=pa_{n+1}+qa_n$, 則 $\{b_n=a_na_{n+1}\}_{n\geq 0}$ 會形成一個三階線性遞迴數列, 滿足 $$b_{n+3}=(p^2+q)b_{n+2}+(p^2q+q^2)b_{n+1}-q^3b_n\mbox{。}$$

備註: 四階以上的線性遞迴關係式亦有其相同性質, 可定義對應多項式。但較為繁瑣與複雜, 我們將以另文討論。

致謝

本文是參加中央研究院數學研究所的暑期研習課程「組合數學與圖論專題」時撰寫的, 由衷地感謝美國內華達大學數學系薛昭雄教授的親自指導, 老師除了訓練我們做研究與找資料的能力之外, 更不厭其煩地幫我們修改文章中的錯誤與提供建議, 使本文得以順利完成。非常感謝。

參考資料

---本文作者2012年畢業於國立成功大學應用數學所碩士班---