一、前言

在國立新竹高中 101 學年度第二學期「竹籤算籌數學有獎徵答」活動中(請參考 ), 高一組第一次徵答第二題是個關於遞迴數列的問題, 問題如下：

第二題： 設 $c$ 為非零整數, 定義數列 $a_1,a_2,a_3,\ldots$ 為 $a_1=2$ 且

\begin{equation} a_{n+1}=ca_n+\sqrt{(c^2-1)({a_n}^2-4)},\qquad n=1,2,3,\ldots\label{1} \end{equation}

試證： $a_{2000}$ 是整數。 (提示 ： 先列出 $a_1,a_2,a_3,\ldots$, 再觀察其關係)

首先, 由 \eqref{1} 式可知

$$a_{n+1}-ca_n=\sqrt{(c^2-1)({a_n}^2-4)},$$

等號兩側取平方得

$${a_{n+1}}^2-2ca_{n+1} a_n+c^2 {a_n}^2=c^2 {a_n}^2-4c^2-{a_n}^2+4,$$

因此

\begin{equation} {a_{n+1}}^2-2ca_{n+1} a_n+{a_n}^2=4(1-c^2 ).\label{2} \end{equation}

同理有

\begin{equation} {a_{n+2}}^2-2c{a_{n+2}} a_{n+1}+{a_{n+1}}^2=4(1-c^2 ).\label{3} \end{equation}

計算 \eqref{3}$-$\eqref{2} 得

$${a_{n+2}}^2-{a_n}^2-2ca_{n+1} ({a_{n+2}}-a_n )=0,$$

或者寫成

\begin{equation} ({a_{n+2}}-a_n )({a_{n+2}}-2ca_{n+1}+a_n )=0.\label{4} \end{equation}

由上式可知對任意正整數 $n$, 底下兩個遞迴式至少有一式須成立：

\begin{eqnarray} {a_{n+2}}&=&a_n,\label{5}\\ {a_{n+2}}&=&2ca_{n+1}-a_n.\label{6} \end{eqnarray}

筆者研究過後, 發現在不同的 $c$ 值之下滿足遞迴式 \eqref{1} 之解 $a_n$ 所對應的數列 $\langle a_n\rangle$ (底下簡稱遞迴式的解數列 $\langle a_n\rangle$), 其連續三項 $a_n,a_{n+1}$, ${a_{n+2}}$, 有可能對任意正整數 $n$ 恰滿足 \eqref{5}, \eqref{6} 兩式其中之一, 也有可能兩者皆滿足； 此外, 還有可能對某些正整數 $n$ 恰滿足 \eqref{5} 式, 對另外一些正整數 $n$ 恰滿足 \eqref{6} 式。

為了清楚探討, 底下兩節我們就分別以 \eqref{5}, \eqref{6} 兩遞迴式為標題, 而筆者將在不同 $c$ 值之下, 由遞迴式 \eqref{1} 求出數列 $\langle a_n\rangle$ 的表達式或討論其特性, 並說明數列 $\langle a_n\rangle$ 是否滿足該節標題的遞迴式。 探討過程中, 也會順便完成原問題的證明。

二、遞迴式 ${a_{n+2}}=a_n$

本節中, 存在正整數 $n$ 使 \eqref{1} 式的解數列 $\langle a_n\rangle$ 之相鄰三項 $a_n,a_{n+1},a_{n+2}$ 滿足標題之遞迴式 (即 \eqref{5} 式) 的 $c$ 值, 共有 $c=1$, $c=-1$ 與 $c\le -2$ 三種情形。 其中, 當 $c=\pm 1$ 時, 對於任意正整數 $n$, \eqref{5} 式均成立； 而 $c\le -2$ 時, 僅對於滿足 $n\ge 2$ 的正整數 $n$, \eqref{5} 式成立。 其詳細探討過程如下：

(a) 當 $c=1$ 時, 遞迴式 \eqref{1} 化為

$$a_{n+1}=a_n,$$

因此 $\langle a_n\rangle$ 為常數列, 滿足

$$a_n=a_{n-1}=\cdots=a_1=2,$$

由此結果可知 $a_{2000}=2$ 為一整數。

進一步看, 因為此時也有

$${a_{n+2}}=a_{n+1}=a_n,$$

可知本情形之下, 對任意正整數 $n$, 遞迴式 \eqref{5} 均成立。

(b) 當 $c=-1$ 時, 遞迴式 \eqref{1} 化為

$$a_{n+1}=-a_n,$$

因此 $\langle a_n\rangle$ 為正負交錯數列, 滿足

$$a_n=-a_{n-1}=\cdots=(-1)^{n-1} a_1=2\times(-1)^{n-1},$$

由此結果可知 $a_{2000}=-2$ 為一整數。

進一步看, 因為此時也有

$${a_{n+2}}=-a_{n+1}=a_n,$$

可知本情形之下, 對任意正整數 $n$, 遞迴式 \eqref{5} 均成立。

(c) 當 $c\le -2$ 時, 將已知條件 $a_1=2$ 代入遞迴式 \eqref{1}, 得 $a_2=2c$, 再將 $a_2=2c$ 代入 \eqref{1} 式, 可得 $a_3=4c^2-2$。 接著, 將 $a_3=4c^2-2$ 代入 \eqref{1} 式後, 在化簡 \eqref{1} 右式的根式時, 因為 $|c|=-c$, 可得

$$a_4=4c^3-2c+4|c|(c^2-1)=2c.$$

因為有

$$a_2=2c,\quad a_3=4c^2-2,\quad a_4=2c,$$

可知接下來 $a_5$ 之值將於 $a_3$ 相同, 即 $a_5=4c^2-2$, 且接著由 $a_6$ 開始的各項之值將繼續以 $2c$ 與 $4c^2-2$ 交替出現(註 1), 因此可知 $a_{2000}=2c$ 為一整數。

由上述結果, 可看出當 $n\ge 2$ 時, 遞迴式 \eqref{5} 成立。 但請注意, 當 $n=1$ 時, 由於 $c\le -2$, 可知 $c^2\ge 4$, 因此有

$$a_3=4c^2-2\ge 14\gt2=a_1,$$

故 $n=1$ 時遞迴式 \eqref{5} 不成立。

(d) 當 $c\ge 2$ 時, 我們可證明在此情形下, 對任意正整數 $n$, 遞迴式 \eqref{5} 均不成立。 在證明這件事之前, 我們先證明在遞迴式 \eqref{1} 的條件下, 對任意正整數 $n$ 均有 $a_n\ge 2$, 證明如下：

證明： 已知 $c\ge 2$, 使用數學歸納法討論如下：

(1) 當 $n=1$ 時, 因 $a_1=2$, 可知 $a_1\ge 2$；

(2) 當 $n=k$ 時, 設 $a_k\ge 2$, 其中 $k\ge 1$, 則 ${a_k}^2-4\ge 0$, 又 $c^2-1\gt0$, 因此當 $n=k+1$ 時, 由遞迴式 \eqref{1} 可知

$$a_{k+1}=ca_k+\sqrt{(c^2-1)({a_k}^2-4)}\ge ca_k\ge 2c\ge 4\ge 2.$$

由數學歸納法原理, 可知對任意正整數 $n$, $a_n\ge 2$ 均成立, 證畢。

利用上述結果, 可證明 $c\ge 2$ 時對任意正整數 $n$ 遞迴式 \eqref{5} 均不成立, 證明如下：

證明： 當 $c\ge 2$ 時, 因為對任意正整數 $n$ 均有 $a_n\ge 2$, 故

$$(c^2-1)({a_k}^2-4)\ge 0.$$

因此由 \eqref{1} 式可知

$$a_{n+1}=ca_n+\sqrt{(c^2-1)({a_k}^2-4)}\ge ca_n\ge 2a_n \gt a_n,$$

故數列 $\langle a_n\rangle$ 嚴格遞增, 從而對任意正整數 $n$, 我們有

$${a_{n+2}} \gt a_{n+1} \gt a_n.$$

上式的結果告訴我們當 $c\ge 2$ 時, 對任意正整數 $n$ 遞迴式 \eqref{5} 均不成立, 證畢。

三、遞迴式 ${a_{n+2}}=2ca_{n+1}-a_n$

本節中, 存在正整數 $n$ 使 \eqref{1} 式的解數列 $\langle a_n\rangle$ 之相鄰三項 $a_n,a_{n+1},a_{n+2}$ 滿足標題之遞迴式 (即 \eqref{6} 式)的 $c$ 值, 共有 $c=1$, $c=-1$, $c\le -2$ 與 $c\ge 2$ 四種情形。 其中, 當 $c=\pm 1$ 時, 對於任意正整數 $n$, \eqref{6} 式均成立； 而 $c\le -2$ 時, 僅 $n=1$ 使 \eqref{6} 式成立; 最後當 $c\ge 2$ 時, 對於任意正整數 $n$, \eqref{6} 式均成立。 底下的內容, 將仿照上節列出四個項目的方式進行詳細討論。

注意底下各項目中, 相關的討論與 $a_{2000}$ 為整數的證明若在上一節中已介紹過, 則此處將會省略之, 請讀者自行參閱上一節中的相關內容。 討論如下：

(a) 當 $c=1$ 時, 遞迴式 \eqref{1} 化為

$$a_{n+1}=a_n,$$

因此 $\langle a_n\rangle$ 為常數列, 此時對任意正整數 $n$, 我們有

$${a_{n+2}}=a_{n+1},\qquad a_{n+1}-a_n=0.$$

利用上述兩式, 我們可寫下

$$ {a_{n+2}}=a_{n+1}+0=a_{n+1}+(a_{n+1}-a_n)=2a_{n+1}-a_n. $$

注意上式之頭尾恰好是對遞迴式 \eqref{6} 取 $c=1$ 的結果, 因此可知在本情形下, 對任意正整數 $n$, 遞迴式 \eqref{6} 均成立。

(b) 當 $c=-1$ 時, 遞迴式 \eqref{1} 化為

$$a_{n+1}=-a_n,$$

此時對任意正整數 $n$, 我們有

$${a_{n+2}}=-a_{n+1},\quad a_{n+1}+a_n=0.$$

利用上述兩式, 同理可寫下

$$ {a_{n+2}}=-a_{n+1}-0=-a_{n+1}-(a_{n+1}+a_n )=-2a_{n+1}-a_n. $$

注意上式之頭尾恰好是對遞迴式 \eqref{6} 取 $c=-1$ 的結果, 因此可知在本情形下, 對任意正整數 $n$, 遞迴式 \eqref{6} 均成立。

(c) 當 $c\le -2$ 時, 由上一節 (c) 項目的討論內容, 我們知道 $a_1=2$, 且當 $m\ge 1$ 時有

$$a_{2m}=2c,\qquad a_{2m+1}=4c^2-2,$$

其中 $m$ 為正整數。 因此數列 $\langle a_n\rangle$ 的前三項為

$$a_1=2,\qquad a_2=2c,\qquad a_3=4c^2-2,$$

檢查過後可知滿足

$$a_3=2ca_2-a_1.$$

因此, 本情形下當 $n=1$ 時, 遞迴式 \eqref{6} 成立。

而當 $n\ge 2$ 時, 若 $n$ 為偶數, 因為 $c\le -2$ 且 $c^2\ge 4$, 可發現有

$${a_{n+2}}-2ca_{n+1}+a_n=2c-2c\times(4c^2-2)+2c=8c(1-c^2 )\gt0;$$

而若 $n$ 為奇數, 也可發現

$${a_{n+2}}-2ca_{n+1}+a_n=(4c^2-2)-2c\times 2c+(4c^2-2)=4(c^2-1)\gt0.$$

因此對滿足 $n\ge 2$ 的正整數 $n$, 遞迴式 \eqref{6} 均不成立。

(d) 當 $c\ge 2$ 時, 在上一節 (d) 項目的討論中, 我們已證明在此情形下對任意正整數 $n$ 遞迴式 \eqref{5} 均不成立。 然而在第一節當中, 我們已證明對任意正整數 $n$ 而言 \eqref{5}, \eqref{6} 兩遞迴式至少有一式須成立, 這表示對任意正整數 $n$, 遞迴式 \eqref{6} 必須成立。

在遞迴式 \eqref{6} 對任意正整數 $n$ 成立的條件下, 先由原問題初始條件 $a_1=2$ 與 \eqref{1} 式求出 $a_2=2c$, 接著我們可透過數學歸納法證明 $a_n$ 恆為整數, 證明如下：

證明： (1) 當 $n=1,2$ 時, 已知 $a_1=2$, $a_2=2c$, 故 $a_1,a_2$ 為整數；

(2) 當 $n=k,k+1$ 時, 若 $a_k,a_{k+1}$ 均為整數, 其中 $k\ge 1$, 則當 $n=k+2$ 時, 由於

$$a_{k+2}=2ca_{k+1}-a_k,$$

因此知 $a_{k+2}$ 亦為整數。

由數學歸納法原理, 知 $a_n$ 恆為整數, 證明完畢。

由以上證明結果, 我們也知道原問題關心的 $a_{2000}$ 為整數。

回顧與整理:

本節最後, 若回顧上一節與本節各個項目的討論結果, 觀察在不同的 $c$ 值下遞迴式 \eqref{1} 的解數列 $\langle a_n\rangle$, 則其相鄰三項 $a_n,a_{n+1},a_{n+2}$ 滿足 \eqref{5} 式或 \eqref{6} 式的各種情形可整理如下表：

四、延伸探討

回顧前兩節兩個 (d) 項目的討論內容, 可發現當 $c\ge 2$ 時我們並未求出 $a_n$ 的表達式。 因此, 不妨利用本節計算當 $c\ge 2$ 時 $a_n$ 一般項的表達式。

當 $c\ge 2$ 時, 遞迴式 \eqref{1} 的解 $a_n$ 滿足二階遞迴式 \eqref{6} (可參考上一節末所列之表 1), 而初始條件為 $a_1=2$, $a_2=2c$。 將遞迴式 \eqref{6} 改寫為

\begin{equation} {a_{n+2}}-2ca_{n+1}+a_n=0,\label{9} \end{equation}

此為常係數二階線性遞迴式, 其特徵方程式 $\lambda^2-2c\lambda +1=0$ 的兩根如下：

$$\lambda =c\pm \sqrt{c^2-1}.$$

為求簡化符號, 我們令上述兩根為

\begin{eqnarray} \alpha&=&c+\sqrt{c^2-1},\label{10}\\ \beta &=&c-\sqrt{c^2-1},\label{11} \end{eqnarray}

則有 $\alpha\beta =1$, 且由 $c\ge 2$ 的條件可知 $\alpha\gt\beta \gt0$。

由求解線性遞迴式的相關理論(可參考 第 7.2 節), 知滿足 \eqref{9} 式的解可假設為

\begin{equation} a_n=k_1 \alpha^n+k_2 \beta ^n,\label{12} \end{equation}

其中 $k_1,k_2$ 為常數。 將 $n=1,2$ 代入上式後搭配 $a_1=2$, $a_2=2c$ 的條件, 可得方程組

$$\left\{\begin{array}{rcl} k_1 \alpha+k_2 \beta &=&2\\[4pt] k_1 \alpha^2+k_2 \beta ^2&=&2c\end{array}\right..$$

解上述方程組, 可得 $k_1=1/\alpha$, $k_2=1/\beta $, 將此兩結果代入 \eqref{12} 式可知

\begin{equation} a_n=\alpha^{n-1}+\beta ^{n-1},\label{13} \end{equation}

也就是有

\begin{equation} a_n=(c+\sqrt{c^2-1})^{n-1}+(c-\sqrt{c^2-1})^{n-1}.\label{14} \end{equation}

上式就是當 $c\ge 2$ 時, 在初始條件 $a_1=2$, $a_2=2c$ 下滿足遞迴式 \eqref{6} 的解 $a_n$ 之表達式, 同時也是在初始條件 $a_1=2$ 下滿足遞迴式 \eqref{1} 的解 $a_n$ 之表達式。

注意因 $\alpha\gt\beta \gt0$, 可知對任意正整數 $n$ 有 $\alpha^{n-1}\ge\beta^{n-1}$, 或者寫成

\begin{equation} \alpha^{n-1}-\beta ^{n-1}\ge 0.\label{15} \end{equation}

利用 \eqref{13} 式與 $\alpha\beta =1$ 的條件, 可知

\begin{equation} {a_n}^2-4=(\alpha^{n-1}+\beta ^{n-1})^2-4\alpha^{n-1}\beta ^{n-1}=(\alpha^{n-1}-\beta^{n-1})^2\ge 0.\label{16} \end{equation}

對 \eqref{16} 式中等式部份的兩端加上根號後, 利用 \eqref{15} 式可得

\begin{equation} \sqrt{{a_n}^2-4}=|\alpha^{n-1}-\beta^{n-1} |=\alpha^{n-1}-\beta^{n-1}.\label{17} \end{equation}

此時回頭觀察 \eqref{10}, \eqref{11} 兩式, 可知

\begin{equation} \alpha-c=c-\beta=\sqrt{c^2-1}, \label{18} \end{equation}

再利用 \eqref{13} 式的結果, 配合 \eqref{17}, \eqref{18} 兩式可知

\begin{eqnarray*} a_{n+1}-ca_n&=&(\alpha^n+\beta ^n )-c(\alpha^{n-1}+\beta^{n-1})=(\alpha-c) \alpha^{n-1}-(c-\beta) \beta ^{n-1}\\ &=&\sqrt{c^2-1}\times(\alpha^{n-1}-\beta^{n-1})=\sqrt{c^2-1}\times \sqrt{{a_n}^2-4}. \end{eqnarray*}

上式所得的結果, 移項後即得

\begin{equation} a_{n+1}=ca_n+\sqrt{(c^2-1)({a_n}^2-4)}, \label{19} \end{equation}

而這應該就是第一節原問題中遞迴式 \eqref{1} 的由來。

不過, 原問題是將本節設定的條件 「$c$ 為不小於 2 之整數」 放寬為「$c$ 為非零整數」後再看 \eqref{19} 式, 也因此才有第三節末之表 1 所列, 在不同的 $c$ 值範圍下所得的不同結果。

五、可能之推廣

接下來, 我們不妨把遞迴式 \eqref{9} 推廣為更一般的

\begin{equation} {a_{n+2}}-2pa_{n+1}+qa_n=0,\label{20} \end{equation}

其中 $p,q$ 為正實數且滿足 $p\gt1$, $p^2-q\gt0$, 並取初始條件 $a_1=2$, $a_2=2p$。 此時, \eqref{9} 式只是對 \eqref{20} 式取 $p=c$, $q=1$ 且 $c$ 為大於 1 之整數的特例。 遞迴式 \eqref{20} 的特徵方程式為

$$\lambda ^2-2p\lambda +q=0,$$

它有兩相異實根 $p\pm \sqrt{p^2-q}$。 我們令

\begin{eqnarray} \alpha=p+\sqrt{p^2-q},\label{21}\\ \beta =p-\sqrt{p^2-q},\label{22} \end{eqnarray}

則同樣有 $\alpha\gt\beta \gt0$, 且有

\begin{equation} \alpha-p=p-\beta =\sqrt{p^2-q}.\label{23} \end{equation}

回顧 \eqref{12} 式的由來, 同理可知 \eqref{20} 式的解可假設為 \begin{equation} a_n=k_1 \alpha^n+k_2\beta^n,\label{24} \end{equation} 其中 $k_1,k_2$ 為常數。 將 $n=1,2$ 代入上式後搭配 $a_1=2$, $a_2=2p$ 的條件, 可得方程組

$$\left\{\begin{array}{rcl} k_1 \alpha+k_2 \beta &=&2\\[4pt] k_1 \alpha^2+k_2 \beta ^2&=&2p\end{array}\right..$$

解上述方程組, 可得 $k_1=1/\alpha$, $k_2=1/\beta $, 將此兩結果代入 \eqref{24} 式可知 \begin{equation} a_n=\alpha^{n-1}+\beta ^{n-1},\label{25} \end{equation} 也就是有

$$ a_n=(p+\sqrt{p^2-q})^{n-1}+(p-\sqrt{p^2-q})^{n-1}. $$

由於 $\alpha\beta =q$, 此時若仿照寫下 \eqref{16} 式時的想法, 改考慮 ${a_n}^2-4q^{n-1}$, 可得

\begin{align} {a_n}^2-4q^{n-1}=(\alpha^{n-1}+\beta ^{n-1} )^2-4\alpha^{n-1} \beta ^{n-1} =(\alpha^{n-1}-\beta ^{n-1} )^2\ge 0.\label{27} \end{align}

注意因 $\alpha\gt\beta \gt0$, 可知對任意正整數 $n$, 我們有

\begin{equation} \alpha^{n-1}-\beta ^{n-1}\ge 0,\label{28} \end{equation}

仿照 \eqref{17} 式的推導方式, 利用 \eqref{27}, \eqref{28} 兩式可得

\begin{equation} \sqrt{{a_n}^2-4q^{n-1}}=|\alpha^{n-1}-\beta ^{n-1} |=\alpha^{n-1}-\beta ^{n-1}.\label{29} \end{equation}

接著, 依序利用 \eqref{25}, \eqref{23}, \eqref{29} 三式的結果, 可知

\begin{eqnarray*} a_{n+1}-pa_n&=&(\alpha^n+\beta ^n)-p(\alpha^{n-1}+\beta ^{n-1})=(\alpha-p) \alpha^{n-1}-(p-\beta ) \beta ^{n-1}\\ &=&\sqrt{p^2-q}\times(\alpha^{n-1}-\beta ^{n-1})=\sqrt{p^2-q}\times \sqrt{{a_n}^2-4q^{n-1}}, \end{eqnarray*}

因此得到

\begin{equation} a_{n+1}=pa_n+\sqrt{(p^2-q)({a_n}^2-4q^{n-1})}.\label{30} \end{equation}

當然, 遞迴式 \eqref{19} 就是對上式取 $p=c$, $q=1$ 且 $c$ 為大於 1 之整數的結果。 注意取 $q=1$ 可使 \eqref{30} 式中的 $4q^{n-1}$ 變成與 $n$ 無關的常數 4, 從而得到較 \eqref{30} 式簡潔許多的 \eqref{19} 式。

六、結語

本文前三節的內容, 是先由非線性一階遞迴式 \eqref{1} 求出 \eqref{5} 與 \eqref{6} 這兩個線性二階遞迴式, 接著再對不同的 $c$ 值範圍, 探討遞迴式 \eqref{1} 的解數列 $\langle a_n\rangle$ 之相鄰三項 $a_n,a_{n+1},a_{n+2}$ 對於哪些 $n$ 值會滿足遞迴式 \eqref{5} 或 \eqref{6}。 第四節的 \eqref{14} 式是在 $c\ge 2$ 之條件下遞迴式 \eqref{6} 的解, 它是本文想強調的一個重點, 而藉由第四節後半的探討, 我們也大約知道遞迴式 \eqref{1} 的由來應與 \eqref{14} 式有關。

本文投稿後歷經兩次主要的修正, 感謝審稿者提供了許多有益的修正建言, 使本文得以更臻完善。 其中, 在第一節由遞迴式 \eqref{1} 推得 \eqref{4} 式的手法與第二、 第三節分開探討 \eqref{5}, \eqref{6} 兩式的寫法均出自其建議, 前者完全取代了筆者原本 推得 \eqref{4} 式時所用的方法, 而後者則使本文原有的研究結果得以清楚呈現, 再次感謝。

註 1： 在 $c\le -2$ 的條件下不難證明 $2c$ 與 $4c^2-2$ 兩數不相等, 讀者不妨試著證明看看。

參考文獻

本文作者投稿時任職群緯環保