5.1 數列、遞推與級數

數列到底是甚麼

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

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

由規律尋找通項

有限列表只能提示規律；通項要描述第 n 項，而不是只描述頭幾項。

遞推定義

有些數列較適合用「如何由前面的項得到下一項」來定義。

例如

$$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.$$

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

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

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$ 上的一階遞推。

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

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

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

首先，

$$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$。

等差數列與求和

若 $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).$$

這來自首尾配對：第一項配最後一項，第二項配倒數第二項，每一對的和都相同。

等比數列與求和

若 $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}.$$

證明的核心是相減：

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

若 $r=1$，則和只是 bn。

等差等比混合求和

來源章節最後一題把等差因子與等比因子混合。設

$$x_k=(a+kd)br^k,\qquad k\in\mathbb N,$$

其中 $r\ne0$ 且 $r\ne1$，並定義

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

這不是全新的公式技巧，而是同一個相減方法；只是這次係數會隨索引每次增加 d。比較 $S_n$ 與 $rS_n$：

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

中間部分仍然是等比和。除以 $1-r$ 並整理後，可得到來源公式

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

應用遞推：按揭公式

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

• $P$ 為初始貸款本金；
• $R$ 為固定年利率；
• $N$ 為月份數；
• x 為每月供款；
• $L_n$ 為第 n 個月供款後的欠款。

則

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

令 q=1+R/12，反覆代入可得

$$L_n=Pq^n-x(q^{n-1}+q^{n-2}+\cdots+q+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}.$$

這不是另一個孤立公式，而是把等比級數公式用於「先乘利息因子、再扣供款」 的遞推式。

快速檢查

練習

1. 為 $1,0,1,0,\ldots$ 寫出通項。
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。

2. 把 (2n)! 分成偶因子與奇因子。偶因子乘積是 $2\cdot4\cdots(2n)=2^n n!$，所以奇因子乘積是 (2n)!/(2^n n!)。

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}.$$

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