5.1 數列、遞推與級數

數列到底是甚麼

數列不只是用逗號排列的一串數。嚴格地說，數列是一個函數：輸入是正整數， 輸出是實數。輸入指出項的位置，輸出就是該位置上的數值。

定義

實數數列

實數數列是一個函數

$$a:\mathbb Z^+\to \mathbb R.$$

我們通常不寫 $a(n)$，而寫 $a_n$；整個數列記作 $\{a_n\}$。這裏起始指標為 $n=1$，定義中的通項公式適用於所有整數 $n ≥ 1$。

這個定義很重要。它解釋了為何同一批數若次序不同，就成為不同數列；也解釋 了為何一個通項公式必須說明每個正整數 $n$ 對應哪一個值。

例題

讀通項

若 $a_n=(-1)^n$，則

$$a_1=-1,\quad a_2=1,\quad a_3=-1,\quad a_4=1.$$

若 $b_n=2^{n-1}$，則

$$b_1=1,\quad b_2=2,\quad b_3=4,\quad b_4=8.$$

兩者都是數列，因為每個正整數 $n$ 都決定唯一一個實數。

思考檢查

本章中，數列形式上是由哪個集合映到哪個集合的函數？

使用定義。

解答 · 答案

它是函數 $a:\mathbb Z^+\to\mathbb R$，即每個正整數索引對應一個實數項。

由規律尋找通項

有限列表只能提示規律；通項要描述第 $n$ 項，而不是只描述頭幾項。如果沒有指定規則，有限個初始值永遠不能唯一確定無限數列：保持列出的各項不變，仍可改變後面某一項。在尋找規律的題目中，必須把所採用的延續方式明確寫成規則。

例題

交替出現的 1 與 0

數列

$$1,0,1,0,\ldots$$

在 $n$ 為奇數時等於 $1$，在 $n$ 為偶數時等於 $0$。一個簡潔公式是

$$a_n=\frac{1+(-1)^{n-1}}2.$$

例題

偶因子與奇因子的乘積

乘積

$$2\cdot4\cdot6\cdots(2n)$$

的第 $k$ 個因子是 $2k$，所以

$$2\cdot4\cdots(2n) =\prod_{k=1}^n 2k =2^n n!.$$

同理，

$$1\cdot3\cdot5\cdots(2n-1) =\frac{(2n)!}{2^n n!}.$$

原因是 $(2n)!$ 包含由 $1$ 到 $2n$ 的所有因子；除去偶因子部分 $2\cdot4\cdots(2n)=2^n n!$ 後，餘下的就是奇因子部分。

例題

由反覆求導得到的數列

章節亦用 $f(x)=\sin x$ 說明：數列不一定先來自普通的數字列表。定義 $a_n=f^{(n)}(0)$，其中 $f^{(n)}$ 表示第 $n$ 次導數。導數會循環：

$$\sin x,\quad \cos x,\quad -\sin x,\quad -\cos x,\quad \sin x,\ldots$$

所以

$$a_1=1,\quad a_2=0,\quad a_3=-1,\quad a_4=0,$$

並且同一個四項模式不斷重複。一個簡潔通項是

$$a_n=\cos\left(\frac{(n-1)\pi}{2}\right).$$

這個例子重要之處，是把「數列」與「簡單代數規律」分開。數列仍然是索引 $n$ 的函數；只是它的值先由微積分操作產生，再在 $0$ 代入。

常見錯誤

未固定索引時，規律還不是定義

當指標從 $n=1$ 開始時，$a_n=2^n$ 給出 $2,4,8,...$，而 $a_n=2^{n-1}$ 給出 $1,2,4,...$。它們是不同數列，不能當作同一個列表的兩種寫法。把起始指標代入公式，是檢查數列是否錯位的直接方法。

遞推定義

有些數列較適合用「如何由前面的項得到下一項」來定義。顯式定義直接由指標計算該項，遞推定義則說明已知的項如何決定後面的項。一階規則需要一個起始值，使用前兩項的規則一般需要兩個起始值；規則本身並沒有選定這些數值。只要初始資料足夠，遞推式就可以完整定義數列，不必先找到方便的封閉公式。

定義

遞推數列

遞推數列是指某些項由一個或多個前項定義，同時給出足夠初始值讓過程開始。

例如

$$a_1=4,\qquad a_{n+1}=2a_n+1$$

給出

$$a_2=9,\quad a_3=19,\quad a_4=39.$$

這條遞推式只有在前一項已知時，才可決定下一項。

對這條特定遞推式，也可以求出封閉公式。兩邊加 $1$，並設 $b_n=a_n+1$。 則

$$b_{n+1}=a_{n+1}+1=2a_n+2=2(a_n+1)=2b_n.$$

由於 $b_1=a_1+1=5$，轉換後的數列是等比數列：

$$b_n=5\cdot2^{n-1}.$$

因此

$$a_n=b_n-1=5\cdot2^{n-1}-1.$$

重點不是每條遞推式都會變成等比數列，而是遇到仿射遞推時，可嘗試用變量轉換 消去常數項。

概念視角算法

同一個數列，求項的兩種方式

顯式公式 $a_n=5\cdot2^{n-1}-1$ 以正整數 $n$ 為輸入。要求 $a_4$，直接代入 $n=4$，便得到 $39$。遞推描述則從 $a_1=4$ 開始，反覆應用 $x\mapsto2x+1$，依次生成 $4,9,19,39$。它說明如何由當前值產生下一個值； 初始值也是這個描述的一部分。

這是同一個數列的兩種描述，並非兩種不同的數。上面的推導把逐步生成的過程 與顯式公式聯繫起來，對每個整數 $n\ge1$ 都成立。僅僅驗證前四項相同， 不足以建立這種聯繫。要求指定指標處的一項時，可用顯式觀點；要追蹤連續 變化時，可用遞推觀點。存在生成規則，本身並不意味著已經得到封閉公式。

定理

Recursion Theorem

設 $X$ 是集合，$b\in X$，且 $f:X\to X$ 是函數。則存在唯一函數 $a:\mathbb Z^+\to X$ 滿足

$$a(1)=b,\qquad a(n+1)=f(a(n))$$

對所有 $n\in\mathbb Z^+$ 成立。

這個定理說明為何「第一項加上一條下一項規則」確實定義一個數列。因為 $f$ 把 $X$ 映回 $X$，過程不會離開指定集合；唯一性則保證不會有另一個不同 數列同時滿足相同起點與相同遞推規則。

存在性表示逐步構造會在每個正整數指標處產生一個值。唯一性可以逐步理解：兩個候選數列在第一項相同；只要某一項相同，對它們應用同一個函數，下一項就必須相同。要求 $f:X\to X$ 很重要，因為每一步的輸出必須仍是下一步可以使用的輸入，過程才能持續進行。

例題

把遞推式翻譯成定理資料

對

$$a_1=1,\qquad a_{n+1}=a_n^2+1,$$

可取 $X=\mathbb R$、$b=1$、$f(x)=x^2+1$。Recursion Theorem 保證存在唯一 實數數列滿足此規則。前幾項為

$$1,\quad 2,\quad 5,\quad 26,\ldots$$

即使未必有簡單封閉公式，數列仍然已被完整定義。

Fibonacci 數列與有序對

Fibonacci 數列由兩個起始值和一條使用前兩項的規則定義：

$$F_1=F_2=1,\qquad F_{n+2}=F_{n+1}+F_n.$$

若要配合 Recursion Theorem，可把相鄰兩項包裝成一個有序對：

$$a(n)=(F_n,F_{n+1}).$$

下一個有序對由函數

$$f(x,y)=(y,x+y)$$

給出。因此二階遞推也可看成在 $\mathbb R^2$ 上的一階遞推。

完整的定理資料是 $X=\mathbb R^2$、$b=(1,1)$ 與 $f(x,y)=(y,x+y)$。這個函數總是輸出實數有序對，第二坐標保存下一步所需的資訊。從 $(1,1)$ 出發，依次得到 $(1,2)$、$(2,3)$。因此定理先保證有序對數列的唯一性，進而保證 Fibonacci 各項的唯一性。

定理

Fibonacci 數的 Binet 公式

令

$$\phi=\frac{1+\sqrt5}{2}, \qquad \psi=\frac{1-\sqrt5}{2}.$$

則對每個正整數 $n$，

$$F_n=\frac{\phi^n-\psi^n}{\phi-\psi}.$$

通常證明方法是檢查右邊有相同的首兩項，並滿足相同遞推式。關鍵恆等式是 $\phi^2=\phi+1$ 與 $\psi^2=\psi+1$。

把這個檢查寫成一般遞推題可重用的形式。定義

$$B_n=\frac{\phi^n-\psi^n}{\phi-\psi}.$$

分母 $\phi-\psi=\sqrt5\ne0$，所以每個正整數指標都對應一個有定義的實數。僅僅驗證遞推式，還不能認定這就是 Fibonacci 數列；還必須核對兩個初始值。

首先，

$$B_1=1,\qquad B_2=\frac{\phi^2-\psi^2}{\phi-\psi}=\phi+\psi=1.$$

其次，因為 $\phi$ 與 $\psi$ 都滿足 $t^2=t+1$，所以

$$\phi^{n+2}=\phi^{n+1}+\phi^n, \qquad \psi^{n+2}=\psi^{n+1}+\psi^n.$$

把第二條式從第一條式相減，再除以 $\phi-\psi$，得到

$$B_{n+2}=B_{n+1}+B_n.$$

因此 $\{B_n\}$ 與 Fibonacci 數列有相同首兩項與相同遞推規則。由遞推定義的 唯一性，對每個正整數 $n$ 都有 $B_n=F_n$。

等差數列與求和

定義

等差數列

若存在常數 $d$ 使得

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

對所有 $n\in\mathbb Z^+$ 成立，則 $\{a_n\}$ 是等差數列。$d$ 稱為公差。

從首項到第 $n$ 項，經過了 $n-1$ 次增量，每次都等於 $d$。把這些相鄰差相加，得到 $a_n-a_1=(n-1)d$。因此，若 $a=a_1$，則

$$a_n=a+(n-1)d.$$

前 $n$ 項和為

$$s_n=\sum_{k=1}^n a_k =\frac n2\left[2a+(n-1)d\right] =\frac n2(a_1+a_n).$$

為了同時解釋奇數項與偶數項的配對，把同一個和正向、反向各寫一次，再逐列相加：

$$\begin{aligned} s_n&=a_1+a_2+\cdots+a_n,\\ s_n&=a_n+a_{n-1}+\cdots+a_1,\\ 2s_n&=n(a_1+a_n). \end{aligned}$$

每列的兩個指標之和為 $n+1$，所以每列的項之和都是 $a_1+a_n$。若 $n$ 為偶數，原來各項可以組成不同的首尾對；若 $n$ 為奇數，中間項等於 $a_1+a_n$ 的一半，在兩個副本相加時恰好與自身配對。無論奇偶，始終都有 $n$ 列，因此最後除以二是合理的。

例題

由總和反推等差數列

假設公差 $d=3/2$，且前 $15$ 項和為 $240$。則

$$240=\frac{15}{2}\left[2a+14\cdot\frac32\right],$$

解得 $a=5.5$。

若前 $k$ 項和為 $361$，則

$$\frac{k}{2}\left[2(5.5)+(k-1)\frac32\right]=361,$$

化簡為

$$3k^2+19k-1444=0.$$

正整數解為 $k=19$；另一根不合題意，因為項數不能為負。

思考檢查

首項為 $a$、公差為 $d$ 的等差數列，前 $n$ 項和是甚麼？

使用首尾配對。

解答 · 答案

$$s_n=\frac n2\left[2a+(n-1)d\right].$$

等比數列與求和

定義

等比數列

若非零數列 $\{b_n\}$ 存在非零常數 $r$ 使得

$$\frac{b_{n+1}}{b_n}=r$$

對所有 $n\in\mathbb Z^+$ 成立，則 $\{b_n\}$ 是等比數列。$r$ 稱為公比。

若 $b=b_1$，則

$$b_n=br^{n-1}.$$

當 $r\ne 1$ 時，有限等比和為

$$\sum_{k=1}^n br^{k-1} =b\sum_{k=0}^{n-1}r^k =b\frac{1-r^n}{1-r} =b\frac{r^n-1}{r-1}.$$

令 $G_n=1+r+\cdots+r^{n-1}$。乘以 $r$ 會把所有指數提高一，得到 $rG_n=r+r^2+\cdots+r^n$。相減時，從 $r$ 到 $r^{n-1}$ 的各項全部抵消，只剩第一行的首項與第二行的末項，所以

$$(1-r)(1+r+\cdots+r^{n-1})=1-r^n.$$

若 $r=1$，每項都是 $b$，所以和是 $bn$，不能除以 $1-r$。這裏討論的都是正整數 $n$ 對應的有限和，抵消過程不需要任何關於無限收斂的假設。

思考檢查

為何等比和公式在 $r=1$ 時要另作處理？

留意分母。

解答 · 答案

公式 $b(1-r^n)/(1-r)$ 會除以 $1-r$，當 $r=1$ 時分母為零。此時每項都是 $b$，所以和是 $bn$。

等差等比混合求和

一個有用的總結練習把等差因子與等比因子混合。設

$$x_k=(a+kd)br^k,\qquad k=0,1,2,\ldots,$$

其中 $r\ne0$ 且 $r\ne1$。對整數 $n ≥ 1$，定義

$$S_n=\sum_{k=0}^{n-1}x_k =\sum_{k=0}^{n-1}(a+kd)br^k.$$

仍然使用相減法，但須仔細追蹤變化的係數。先分出邊界項，再把內部的同次冪對齊：

$$\begin{aligned} S_n&=ab+\sum_{k=1}^{n-1}(a+kd)br^k,\\ rS_n&=\sum_{k=1}^{n-1}(a+(k-1)d)br^k +(a+(n-1)d)br^n. \end{aligned}$$

對每個內部的 $r^k$，係數之差為 $(a+kd)-(a+(k-1)d)=d$。常數項只出現在第一行，$r^n$ 項只出現在第二行。因此

$$(1-r)S_n =ab+db\sum_{k=1}^{n-1}r^k-(a+(n-1)d)br^n.$$

為使中間的等比和使用最終公式中的同一個端點 $r^n$，先求 $r+r^2+\cdots+r^n$，再減去末項：

$$\sum_{k=1}^{n-1}r^k =\frac{r(1-r^n)}{1-r}-r^n.$$

代回後會額外產生 $-dbr^n$。把它與原來的邊界項合併，$a+(n-1)d$ 就變成 $a+nd$。最後除以 $1-r$，得到

$$S_n= \frac{ab-(a+nd)br^n}{1-r} +\frac{dbr(1-r^n)}{(1-r)^2}.$$

當 $n=1$ 時，內部求和是空和，其值為零，原式只剩 $S_1=ab$。上面兩個分式中涉及 $d$ 的額外部分也會抵消，結果同樣是 $ab$。另一方面，令 $d=0$，會恢復普通等比和 $S_n=ab(1-r^n)/(1-r)$。這兩個檢查同時留意了起點與終點，有助於發現指標錯誤。

常見錯誤

留意平移後的邊界項

最容易出錯的是邊界項。$rS_n$ 的最後一項是 $(a+(n-1)d)br^n$，但與有限等比 和合併整理後，等價的最終公式可寫成含有 $(a+nd)br^n$ 的形式。

思考檢查

在等差等比混合求和中，為何 $S_n-rS_n$ 有用？

留意乘上 $r$ 後，係數 $a+kd$ 如何與下一個冪次對齊。

解答 · 答案

大部分項會對齊到同一個 $r$ 的冪次，而相鄰係數只差 $d$。因此只剩兩個邊界項 和一個等比和 $db(r+\cdots+r^{n-1})$，再用普通等比和公式即可化簡。

應用遞推：按揭公式

章節中的按揭例子展示了遞推式如何進入實際計算。設：

• $P\gt 0$ 為初始貸款本金；
• $R$ 為用小數表示的固定名義年利率；
• $N$ 為按月供款的總次數，是正整數；
• $x$ 為每個月末支付的固定供款額；
• $L_n$ 為第 $n$ 次供款剛結束時的欠款。

模型採用月利率 $R/12$：先對上月結餘計息，再扣除本月供款。例如年利率 $3\%$ 對應 $R=0.03$，而不是 $R=3$。第零個月記錄尚未計息或供款的初始本金。對整數月份 $n ≥ 1$，

$$L_0=P,\qquad L_n=L_{n-1}\left(1+\frac{R}{12}\right)-x.$$

令 $q=1+R/12$，先寫出兩步，明確計息和供款的先後：

$$L_1=Pq-x,\qquad L_2=(Pq-x)q-x=Pq^2-xq-x.$$

第一次供款在第二個月計息前已扣除，因此也減少了該月應計的利息；第二次供款則剛剛發生。反覆代入得到

$$L_n=Pq^n-x(q^{n-1}+q^{n-2}+\cdots+q+1).$$

當 $R\gt 0$ 時，$q\gt 1$，所以等比和的分式有定義，得到

$$L_n=Pq^n-x\frac{q^n-1}{q-1}.$$

若希望 $N$ 個月後還清貸款，就令 $L_N=0$，得到

$$x=P\frac{(R/12)(1+R/12)^N}{(1+R/12)^N-1}.$$

各次供款的加權貢獻構成有限等比和：第 $j$ 次供款，對第 $n$ 次供款後結餘的減少量貢獻 $xq^{n-j}$。這解釋了為甚麼最新供款的權重是一，最早供款的權重是 $q^{n-1}$。所得公式對應的正是這個固定利率、每月末供款的模型。

當 $R=0$ 時，直接使用遞推式，不套用分式：此時 $q=1$，$L_n=P-nx$，令 $L_N=0$ 得到 $x=P/N$。因為沒有利息，只需把本金平均分到各次供款中。

練習

1. 設 $a_n$ 為數列 $1,0,1,0,\ldots$，並令 $b_n=a_{n+1}$。求兩個通項，驗證 $a_n+b_n=1$，並說明把起始指標平移後公式如何改變。
2. 用歸納法證明 $1\cdot3\cdot5\cdots(2n-1)=(2n)!/(2^n n!)$。比較所猜通項相鄰兩項的比與乘積中新添的因子。
3. 設 $a_1=3$ 且 $a_{n+1}=a_n+4$。求 $a_n$ 與 $s_n$。
4. 設 $b_1=5$ 且 $b_{n+1}=3b_n$。求 $b_n$ 與前 $n$ 項和。
5. 設 $B_n=(\phi^n-\psi^n)/(\phi-\psi)$，其中 $\phi=(1+\sqrt5)/2$ 且 $\psi=(1-\sqrt5)/2$。驗證 $B_1=B_2=1$ 以及 $B_{n+2}=B_{n+1}+B_n$。
6. 設 $L_0=2000$ 且 $L_n=1.02L_{n-1}-150$。用有限等比和寫出 $L_n$。
7. 設 $x_k=(2+3k)5(1/2)^k$，且 $S_n=\sum_{k=0}^{n-1}x_k$。用等差等比混合 公式寫出 $S_n$。

引導解答

解答 · 參考解答 1

奇數指標對應 $1$，偶數指標對應 $0$，故 $a_n=(1+(-1)^{n-1})/2$。平移一個指標得到 $b_n=(1+(-1)^n)/2=1-a_n$；交替符號改變，所以兩個數列在每個指標上的和均為 $1$。

解答 · 參考解答 2

在 $n=1$ 時，兩邊均為 $1$。若等式在 $n=k$ 成立，乘積下一步添上因子 $2k+1$；右側表達式的相鄰比恰好也是

$$\frac{(2k+2)!}{2^{k+1}(k+1)!}\bigg/\frac{(2k)!}{2^k k!}=\frac{(2k+2)(2k+1)}{2(k+1)}=2k+1.$$

因此歸納步驟成立。這是由遞推關係證明通項，與把階乘分成奇偶因子的論證互相補充。

解答 · 參考解答 3

這是首項 $3$、公差 $4$ 的等差數列，因此 $a_n=3+4(n-1)=4n-1$，且 $s_n=n[2\cdot3+(n-1)4]/2=n(2n+1)$。

解答 · 參考解答 4

這是首項 $5$、公比 $3$ 的等比數列，所以 $b_n=5\cdot3^{n-1}$，且 $s_n=5(3^n-1)/(3-1)=5(3^n-1)/2$。

解答 · 參考解答 5

因為 $\phi^2=\phi+1$ 且 $\psi^2=\psi+1$，乘上 $\phi^n$ 或 $\psi^n$ 後可得 $\phi^{n+2}=\phi^{n+1}+\phi^n$ 與 $\psi^{n+2}=\psi^{n+1}+\psi^n$。兩式相減並除以 $\phi-\psi$，得到 $B_{n+2}=B_{n+1}+B_n$。另外 $B_1=1$，且 $B_2=(\phi^2-\psi^2)/(\phi-\psi)=\phi+\psi=1$。所以 $\{B_n\}$ 與 Fibonacci 數列有相同初始值與遞推式。

解答 · 參考解答 6

反覆代入得 $L_n=2000(1.02)^n-150[(1.02)^{n-1}+\cdots+1]$，所以 $L_n=2000(1.02)^n-150((1.02)^n-1)/0.02$。

解答 · 參考解答 7

這裏 $a=2$、$d=3$、$b=5$、$r=1/2$，所以

$$S_n= \frac{10-(2+3n)5(1/2)^n}{1-1/2} +\frac{15(1/2)(1-(1/2)^n)}{(1-1/2)^2}.$$

這仍可繼續化簡，但重點是正確代入一般有限和公式。