許介彥《數學悠哉遊》，第11單元，〈線性遞迴的求解〉，練習題3，詳解

==問題== 

集合$\{1, 2, 3\}$總共有$2^3 = 8$個部分集合，其中有些部分集合所含的元素中沒有任何兩個元素的大小之差為1，這樣的部分集合有$\varnothing, \{1\}, \{2\}, \{3\}, \{1, 3\}$等五個。對任意正整數$n$，假設$a_n$代表集合$\{1, 2, \cdots, n\}$的所有部分集合中，不含大小之差為1的兩個元素的部分集合個數；我們已知$a_3 = 5$，試用遞迴的方式定義數列$a_1, a_2, a_3, \cdots$，然後利用本篇的方法求出$a_n$的一般式。

==解答==

$n$時，將集合$\{1, 2, \cdots, n\}$滿足題目所求的部分集合所構成的集合記為$D_n$。

下面列出前幾個$D_n$。

$$\begin{eqnarray*} D_1 &=& \left\{ \varnothing, \{1\} \right\}, \\ D_2 &=& \left\{ \varnothing, \{1\}, \{2\} \right\},  \\ D_3 &=& \left\{ \varnothing, \{1\}, \{2\}, \{3\}, \{1, 3\} \right\}, \\ D_4 &=& \left\{ \varnothing, \{1\}, \{2\}, \{3\}, \{4\}, \{1, 3\}, \{1, 4\}, \{2, 4\} \right\}, \\ D_5 &=& \left\{ \varnothing, \{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{2, 4\}, \{2, 5\}, \{3, 5\}, \{1, 3, 5\} \right\}. \end{eqnarray*}$$

於是可知

$$a_1 = 2, a_2 = 3, a_3 = 5, a_4 = 8, a_5 = 13.$$

猜測$\{ a_n \}$為Fibonacci數列。

下面來證明$\{ a_n \}$確實為Fibonacci數列。

首先觀察$n=5$的情形，在$D_5$中，$\varnothing, \{1\}, \{2\}, \{3\}, \{4\}, \{1, 3\}, \{1, 4\}, \{2, 4\}$都恰好是$D_4$的所有元素，而剩下的$\{5\}, \{1, 5\}, \{2, 5\}, \{3, 5\}, \{1, 3, 5\}$，如果把$\bf 5$刪去，變成$\varnothing, \{1\}, \{2\}, \{3\}, \{1, 3\}$，恰好就是$D_3$的所有元素。所以自然有

$$a_5 = a_4 + a_3.$$

從而$a_{n+2} = a_{n+1} + a_n$應該會成立。

對於充分大的$n$，在$D_{n+2}$中，依據「是否包含元素$n+2$」可分為兩大類，我們將含有元素$n+2$的子集合所構成的集合記為$A_{n+2}$，而不含元素$n+2$的子集合所構成的集合記為$B_{n+2}$。所以顯然有

$$D_{n+2} = A_{n+2} \cup B_{n+2}, {\text{且}} A_{n+2} \cap B_{n+2} = \varnothing.$$

在$A_{n+2}$中，每個成員集合都含有元素$n+2$，而第二大的元素要嘛不存在，要嘛不超過$n$，因此如果將所有成員集合中的元素$n+2$刪除，於是這些集合就都會變成$D_n$的元素。

另外，在$D_n$中，由於每個成員集合中所包含的數最大不超過$n$，因此如果在每個成員集合中的尾巴添上$n+2$，那麼這些新構造出來的集合都會是$D_{n+2}$的元素。

以上我們構造出$A_{n+2}$與$D_n$之間的一個雙射（bijection），故$\left| A_{n+2} \right| = \left| D_n \right| = a_n$。

接著來討論$B_{n + 2}$

由於其中每個成員集合皆不包含$n + 2$，所以要不是空集合，要不所含的數最大不超過$n + 1$，同時因為$B_{n+2}$要滿足條件「部分集合所含的元素中沒有任何兩個元素的大小之差為1」，於是可斷定$B_{n+2}$根本就是$D_{n+1}$，從而$\left| B_{n+2} \right| = \left| D_{n+1} \right| = a_{n+1}$。

綜上所述，我們確實得到

$$a_{n+2} = a_{n+1} + a_n, (n \ge 1).$$

此為Fibonacci數列關係式，其一般式的解法可見課文第149頁，在此不加贅述。

（解答終了）

行列式的餘因子遞迴定義：從2階行列式與Cramer法則談起

​ 南京大學數學系的朱富海教授在其文章〈问题引导的代数学: 行列式的多样性〉中討論了行列式的諸多定義方式，非常值得一讀。特別是其中

问题 2 三元一次线性方程组

$$\left\{ \begin{eqnarray*} a_{11} x_1 +a_{12} x_2 + a_{13} x_3 &=&b_1 \\ a_{21} x_1 +a_{22} x_2 + a_{23} x_3 &=&b_2 \\ a_{31} x_1 +a_{32} x_2 + a_{33} x_3 &=&b_3 \end{eqnarray*} \right.$$

有唯一解, 求解的表达式.这个问题稍微复杂了一点, 可以利用消元法化为二元一次方程组, 不过我更喜欢利用二元情形的结论: 把$x_1$看作已知的, 利用后两个方程求出$x_2, x_3$ (用二阶行列式来表达), 再代入第一个方程解出$x_1$. $x_1$的表达式是一个分式, 分子分母有共性, 引入三阶行列式就更能看出整齐性, 甚至猜出了三元情形的 Cramer 法则.

這真是個精闢的看法！觀點恰好與典型的解線性方程組的順序相反。一般慣用的Gauss消去法是由上而下，依序對$x_1, x_2, \cdots, x_n$消元，然後再代回求解。 朱教授此處所言，卻是先考慮排除掉$x_1$，以Cramer公式處理$n-1$元線性方程組後，再代回解出$x_1$，非常的有遞迴的味道！

​ 實際上正是這樣的處理手法，可以自然的導出行列式的餘因子降階定義法！

​ 有名的炸漢堡(Friedberg)線性代數，介紹n階行列式時，就是用餘因子降階法來定義。但是一個問題是，完全不說明這個定義怎麼來的，就是從天而降，讓人摸不著腦袋。我實在很反感這種教學方式。

約定：以下解方程組的過程中，一概考慮非奇異的情況。

1. 2階行列式與Cramer法則 

​ 考慮2元線性方程組$\left\{ \begin{eqnarray*} a_{11}x_1 + a_{12}x_2 &=& b_1 \\ a_{21}x_1 + a_{22}x_2 &=& b_2 \end{eqnarray*} \right.$，對其中的第2式$a_{21}x_1 + a_{22}x_2 = b_2$，以$x_1$表示出$x_2$解得$x_2 = \frac{1}{a_{22}} \left( b_2 - a_{21}x_1 \right)$，代回原方程組中的第1式，得
$$\begin{eqnarray*}a_{11} x_1 + a_{12} \cdot \frac{1}{a_{22}} \left( b_2 - a_{21}x_1 \right) &=& b_1, \\ a_{11} a_{22} x_1 + a_{12} \left( b_2 - a_{21}x_1 \right) &=& a_{22} b_1, \\ \left( a_{11} a_{22} - a_{12} a_{21} \right)x_1 &=& b_1 a_{22} - b_2 a_{12}, \end{eqnarray*}$$
當$a_{11} a_{22} - a_{12} a_{21} \ne 0$時，可解得
$$x_1 = \frac{b_1 a_{22} - b_2 a_{12}}{a_{11} a_{22} - a_{12} a_{21}}.$$
仔細觀察分子與分母的結構，非常的類似。定義2階行列式 (determinant of order 2)為
$$\left| \begin{array}{cc} a & b \\ c  & d \end{array} \right| = ad - bc.$$
於是$x_1$可改寫為
$$x_1 = \frac{\left| \begin{array}{cc} b_1 & a_{12} \\ b_2  & a_{22} \end{array} \right|}{\left| \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right|}.$$
為了解出$x_2$，如果將$x_1$的式子代回原方程組，會遭遇複雜的運算。我們可以換個思路。由於加法具有交換律，我們可以考慮將原來的方程組變形為
$$\left\{ \begin{eqnarray*} a_{12}x_2 + a_{11}x_1 &=& b_1 \\ a_{22}x_2 + a_{21}x_1 &=& b_2 \end{eqnarray*} \right. .$$
這個方程組當然與原本的方程組是同解的！接著依樣畫葫蘆，可以求得
$$x_2 = \frac{\left| \begin{array}{cc} b_1 & a_{11} \\ b_2  & a_{21} \end{array} \right|}{\left| \begin{array}{cc} a_{12} & a_{11} \\ a_{22} & a_{21} \end{array} \right|}.$$
儘管$x_1, x_2$乍看有點不同，但其實他們有相同的分母。在此我們要先插記一個2階行列式的性質：

性質  2階行列式中，對調column後，新行列式值為原行列式值添上一負號。

[證]. $\left| \begin{array}{cc} b & a \\ d & c \end{array} \right| = bc - ad = -(ad - bc) = -\left| \begin{array}{cc} a & b \\ c & d \end{array} \right|.$

(證明終了)

有了這個性質後，我們就可以重新計算$x_2$如下：
$$x_2 = \frac{\left| \begin{array}{cc} b_1 & a_{11} \\ b_2  & a_{21} \end{array} \right|}{\left| \begin{array}{cc} a_{12} & a_{11} \\ a_{22} & a_{21} \end{array} \right|} = \frac{ - \left| \begin{array}{cc} a_{11} & b_1 \\ a_{21}  & b_2 \end{array} \right|}{ - \left| \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right|} = \frac{\left| \begin{array}{cc} a_{11} & b_1 \\ a_{21}  & b_2 \end{array} \right|}{\left| \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right|}.$$
因此我們稱2階行列式$\left| \begin{array}{cc} a_{11} & a_{12} \\ a_{21} & a_{22} \end{array} \right|$為線性方程組$\left\{ \begin{eqnarray*} a_{11}x_1 + a_{12}x_2 &=& b_1 \\ a_{21}x_1 + a_{22}x_2 &=& b_2 \end{eqnarray*} \right.$的係數行列式，記為$D^{(2)}$。而行列式$\left| \begin{array}{cc} b_1 & a_{12} \\ b_2  & a_{22} \end{array} \right|$與$\left| \begin{array}{cc} a_{11} & b_1 \\ a_{21}  & b_2 \end{array} \right|$則分別記為$D^{(2)}_1$與$D^{(2)}_2$，從而得到2階線性方程組的Cramer公式：
$$x_1 = \frac{D^{(2)}_1}{D^{(2)}}, x_2 = \frac{D^{(2)}_2}{D^{(2)}}.$$
此處再提醒，行列式$D^{(2)}_1$是用常數項$\begin{eqnarray*} b_1 \\ b_2 \end{eqnarray*}$替換掉係數行列式$D^{(2)}$的column 1而得到，$D^{(2)}_2$則是用常數項$\begin{eqnarray*} b_1 \\ b_2 \end{eqnarray*}$替換掉係數行列式$D^{(2)}$的column 2而得。

G. Cramer (1704-1752)

Cramer法則首次的公開是在此書的附錄

紅線框起的部分就是2階線性方程組的Cramer法則，只是當年沒有採用行列式記號。下面跟著的是3階的情況。

2. 用2階Cramer法則解3階線性方程組，用2階行列式導出3階行列式  

​ 現在考慮3階線性方程組

$$\left\{ \begin{eqnarray*} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 &=& b_1 \\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 &=& b_2 \\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 &=& b_3 \end{eqnarray*} \right. .$$

首先針對其中的第2式與第3式，改寫作

$$\left\{ \begin{eqnarray*} a_{22}x_2 + a_{23}x_3 &=& b_2 - a_{21}x_1 \\ a_{32}x_2 + a_{33}x_3 &=& b_3 - a_{31}x_1 \end{eqnarray*} \right. .$$

然後使用2階線性方程組的Cramer法則，得到

$$x_2 = \frac{\left| \begin{array}{cc} b_2 - a_{21}x_1 & a_{23} \\ b_3 - a_{31}x_1 & a_{33} \end{array} \right|}{\left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right|} = \frac{\left| \begin{array}{cc} b_2 & a_{23} \\ b_3 & a_{33} \end{array} \right| - x_1 \left| \begin{array}{cc} a_{21} & a_{23} \\ a_{31} & a_{33} \end{array} \right|}{\left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right|},$$

以及

$$x_3 = \frac{\left| \begin{array}{cc} a_{22} & b_2 - a_{21}x_1 \\ a_{32} & b_3 - a_{31}x_1 \end{array} \right|}{\left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right|} = \frac{\left| \begin{array}{cc} a_{22} & b_2 \\ a_{32} & b_3 \end{array} \right| - x_1 \left| \begin{array}{cc} a_{22} & a_{21} \\ a_{32} & a_{31} \end{array} \right|}{\left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right|}.$$

代回原方程組中的第1式，

$$a_{11} x_1 + a_{12} \frac{\left| \begin{array}{cc} b_2 & a_{23} \\ b_3 & a_{33} \end{array} \right| - x_1 \left| \begin{array}{cc} a_{21} & a_{23} \\ a_{31} & a_{33} \end{array} \right|}{\left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right|} + a_{13} \frac{\left| \begin{array}{cc} a_{22} & b_2 \\ a_{32} & b_3 \end{array} \right| - x_1 \left| \begin{array}{cc} a_{22} & a_{21} \\ a_{32} & a_{31} \end{array} \right|}{\left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right|} = b_1,$$

整理得

$$\left( a_{11} \left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right| - a_{12}\left| \begin{array}{cc} a_{21} & a_{23} \\ a_{31} & a_{33} \end{array} \right| - a_{13}\left| \begin{array}{cc} a_{22} & a_{21} \\ a_{32} & a_{31} \end{array} \right| \right) x_1 = b_1 \left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right| - a_{12}\left| \begin{array}{cc} b_2 & a_{23} \\ b_3 & a_{33} \end{array} \right| - a_{13}\left| \begin{array}{cc} a_{22} & b_2 \\ a_{32} & b_3 \end{array} \right|.$$

對於上式中，牽涉到$\begin{eqnarray*} a_{21} \\ a_{31} \end{eqnarray*}$與$\begin{eqnarray*} b_2 \\ b_3 \end{eqnarray*}$的行列式，將$\begin{eqnarray*} a_{21} \\ a_{31} \end{eqnarray*}$與$\begin{eqnarray*} b_2 \\ b_3 \end{eqnarray*}$各別調換至其所在行列式中的column1位置，利用前文推導過的「行列式交換column添負號」，得

$$\left( a_{11} \left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right| - a_{12}\left| \begin{array}{cc} a_{21} & a_{23} \\ a_{31} & a_{33} \end{array} \right| + a_{13}\left| \begin{array}{cc} a_{21} & a_{22} \\ a_{31} & a_{32} \end{array} \right| \right) x_1 = b_1 \left| \begin{array}{cc} a_{22} & a_{23} \\ a_{32} & a_{33} \end{array} \right| - a_{12}\left| \begin{array}{cc} b_2 & a_{23} \\ b_3 & a_{33} \end{array} \right| + a_{13}\left| \begin{array}{cc} b_2 & a_{22} \\ b_3 & a_{32} \end{array} \right|.$$

如果我們定義3階行列式 (determinant of order 3)為

$$\left| \begin{array}{ccc} d_{11} & d_{12} & d_{13} \\ d_{21} & d_{22} & d_{23} \\ d_{31} & d_{32} & d_{33} \\  \end{array} \right| = d_{11} \left| \begin{array}{cc} d_{22} & d_{23} \\ d_{32} & d_{33} \end{array} \right| - d_{12} \left| \begin{array}{cc} d_{21} & d_{23} \\ d_{31} & d_{33}  \end{array} \right| + d_{13} \left| \begin{array}{cc} d_{21} & d_{22} \\ d_{31} & d_{32} \end{array} \right|.$$

那麼上式可改寫為

$$\left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right| x_1 = \left| \begin{array}{ccc} b_1 & a_{12} & a_{13} \\ b_2 & a_{22} & a_{23} \\ b_3 & a_{32} & a_{33} \end{array} \right|.$$

從而可解出

$$x_1 = \frac{\left| \begin{array}{ccc} b_1 & a_{12} & a_{13} \\ b_2 & a_{22} & a_{23} \\ b_3 & a_{32} & a_{33} \end{array} \right|}{\left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right|}.$$

要解出$x_2$與$x_3$，無須將方才解出的$x_1$代回方程組，我們採取調換標號的手段，如下所示：

$$\left\{ \begin{array}{ccc} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 &=& b_1 \\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 &=& b_2 \\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 &=& b_3 \end{array} \right. \rightarrow \left\{ \begin{array}{ccc} a_{12}x_2 + a_{11}x_1 + a_{13}x_3 &=& b_1 \\ a_{22}x_2 + a_{21}x_1 + a_{23}x_3 &=& b_2 \\ a_{32}x_2 + a_{31}x_1 + a_{33}x_3 &=& b_3 \end{array} \right. \Rightarrow x_2 = \frac{\left| \begin{array}{ccc} b_1 & a_{11} & a_{13} \\ b_2 & a_{21} & a_{23} \\ b_3 & a_{31} & a_{33} \end{array} \right|}{\left| \begin{array}{ccc} a_{12} & a_{11} & a_{13} \\ a_{22} & a_{21} & a_{23} \\ a_{32} & a_{31} & a_{33} \end{array} \right|}.$$

以及

$$\left\{ \begin{array}{ccc} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 &=& b_1 \\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 &=& b_2 \\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 &=& b_3 \end{array} \right. \rightarrow \left\{ \begin{array}{ccc} a_{13}x_3 + a_{12}x_2 + a_{11}x_1 &=& b_1 \\ a_{23}x_3 + a_{22}x_2 + a_{21}x_1 &=& b_2 \\ a_{33}x_3 + a_{32}x_2 + a_{31}x_1 &=& b_3 \end{array} \right. \Rightarrow x_3 = \frac{\left| \begin{array}{ccc} b_1 & a_{12} & a_{11} \\ b_2 & a_{22} & a_{21} \\ b_3 & a_{32} & a_{31} \end{array} \right|}{\left| \begin{array}{ccc} a_{13} & a_{12} & a_{11} \\ a_{23} & a_{22} & a_{21} \\ a_{33} & a_{32} & a_{31} \end{array} \right|}.$$

為了使$x_2, x_3$的分母形式與$x_1$一致，我們還要證明：

性質  3階行列式中，對調column後，新行列式值為原行列式值添上一負號。

[證]. 考慮column 1與column 2對調的情況：

$$\begin{eqnarray*} \left| \begin{array}{ccc} d_{12} & d_{11} & d_{13} \\ d_{22} & d_{21} & d_{23} \\ d_{32} & d_{31} & d_{33} \end{array} \right| &=& d_{12} \left| \begin{array}{cc} d_{21} & d_{23} \\ d_{31} & d_{33} \end{array} \right| - d_{11}\left| \begin{array}{cc} d_{22} & d_{23} \\ d_{32} & d_{33} \end{array} \right| + d_{13} \left| \begin{array}{cc} d_{22} & d_{21} \\ d_{32} & d_{31} \end{array} \right| \\ &=& d_{12} \left| \begin{array}{cc} d_{21} & d_{23} \\ d_{31} & d_{33} \end{array} \right| - d_{11}\left| \begin{array}{cc} d_{22} & d_{23} \\ d_{32} & d_{33} \end{array} \right| - d_{13} \left| \begin{array}{cc} d_{21} & d_{22} \\ d_{31} & d_{32} \end{array} \right| \\ &=& -\left( d_{11}\left| \begin{array}{cc} d_{22} & d_{23} \\ d_{32} & d_{33} \end{array} \right| - d_{12} \left| \begin{array}{cc} d_{21} & d_{23} \\ d_{31} & d_{33} \end{array} \right| + d_{13} \left| \begin{array}{cc} d_{21} & d_{22} \\ d_{31} & d_{32} \end{array} \right| \right) \\ &=& - \left| \begin{array}{ccc} d_{11} & d_{12} & d_{13} \\ d_{21} & d_{22} & d_{23} \\ d_{31} & d_{32} & d_{33} \end{array} \right|. \end{eqnarray*}$$

其餘調換的情況也是類推。

(證明終了)

由此性質，可得

$$x_2 = \frac{\left| \begin{array}{ccc} b_1 & a_{11} & a_{13} \\ b_2 & a_{21} & a_{23} \\ b_3 & a_{31} & a_{33} \end{array} \right|}{\left| \begin{array}{ccc} a_{12} & a_{11} & a_{13} \\ a_{22} & a_{21} & a_{23} \\ a_{32} & a_{31} & a_{33} \end{array} \right|} = \frac{-\left| \begin{array}{ccc} a_{11} & b_1 & a_{13} \\ a_{21} & b_2 & a_{23} \\ a_{31} & b_3 & a_{33} \end{array} \right|}{-\left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right|} = \frac{\left| \begin{array}{ccc} a_{11} & b_1 & a_{13} \\ a_{21} & b_2 & a_{23} \\ a_{31} & b_3 & a_{33} \end{array} \right|}{\left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right|},$$

與

$$x_3 = \frac{\left| \begin{array}{ccc} b_1 & a_{12} & a_{11} \\ b_2 & a_{22} & a_{21} \\ b_3 & a_{32} & a_{31} \end{array} \right|}{\left| \begin{array}{ccc} a_{13} & a_{12} & a_{11} \\ a_{23} & a_{22} & a_{21} \\ a_{33} & a_{32} & a_{31} \end{array} \right|} = \frac{-\left| \begin{array}{ccc} a_{11} & a_{12} & b_1 \\ a_{21} & a_{22} & b_2 \\ a_{31} & a_{32} & b_3 \end{array} \right|}{-\left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right|} = \frac{\left| \begin{array}{ccc} a_{11} & a_{12} & b_1 \\ a_{21} & a_{22} & b_2 \\ a_{31} & a_{32} & b_3 \end{array} \right|}{\left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right|}.$$

​ 類似對2階線性方程組的討論，我們可定義3階線性方程組$\left\{ \begin{eqnarray*} a_{11}x_1 + a_{12}x_2 + a_{13}x_3 &=& b_1 \\ a_{21}x_1 + a_{22}x_2 + a_{23}x_3 &=& b_2 \\ a_{31}x_1 + a_{32}x_2 + a_{33}x_3 &=& b_3 \end{eqnarray*} \right.$的係數行列式$D^{(3)}$及$D^{(3)}_1, D^{(3)}_2, D^{(3)}_3$如下：

$$D^{(3)} = \left| \begin{array}{ccc} a_{11} & a_{12} & a_{13} \\ a_{21} & a_{22} & a_{23} \\ a_{31} & a_{32} & a_{33} \end{array} \right|,  D^{(3)}_1 = \left| \begin{array}{ccc} b_1 & a_{12} & a_{13} \\ b_2 & a_{22} & a_{23} \\ b_3 & a_{32} & a_{33} \end{array} \right|, D^{(3)}_2 = \left| \begin{array}{ccc} a_{11} & b_1 & a_{13} \\ a_{21} & b_2 & a_{23} \\ a_{31} & b_3 & a_{33} \end{array} \right|, D^{(3)}_3 = \left| \begin{array}{ccc} a_{11} & a_{12} & b_1 \\ a_{21} & a_{22} & b_2 \\ a_{31} & a_{32} & b_3 \end{array} \right|.$$

從而3階線性方程組的Cramer法則可表述為

$$x_1 = \frac{D^{(3)}_1}{D^{(3)}}, x_2 = \frac{D^{(3)}_2}{D^{(3)}}, x_3 = \frac{D^{(3)}_3}{D^{(3)}}.$$

3. 從$n-1$到$n$

​ 對於$n$階線性方程組

$$\left\{ \begin{eqnarray*} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &=& b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &=& b_2 \\ \vdots&& \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n &=& b_n \end{eqnarray*} \right. ,$$

$A$中的column分別構成以下的column向量

$$A_1 = \left[ \begin{array}{c} a_{11} \\ a_{21} \\ \vdots \\ a_{n1} \end{array} \right], A_2 = \left[ \begin{array}{c} a_{12} \\ a_{22} \\ \vdots \\ a_{n2} \end{array} \right], \cdots, A_n = \left[ \begin{array}{c} a_{1n} \\ a_{2n} \\ \vdots \\ a_{nn} \end{array} \right].$$

方程組右端的常數項則記為

$$b = \left[ \begin{array}{c} b_1 \\ b_2 \\ \vdots \\ b_n \end{array} \right].$$

由於我們會針對原方程組中的後$n-1$條方程式進行討論，所以再定義以下的column向量：

$$\tilde{A_1} = \left[ \begin{array}{c} a_{21} \\ \vdots \\ a_{n1} \end{array} \right],\tilde{A_2} = \left[ \begin{array}{c} a_{22} \\ \vdots \\ a_{n2} \end{array} \right], \cdots, \tilde{A_n} = \left[ \begin{array}{c} a_{2n} \\ \vdots \\ a_{nn} \end{array} \right], \tilde{b} = \left[ \begin{array}{c} b_2 \\ \vdots \\ b_n \end{array} \right].$$

它們都是從原來的$A_1, A_2, \cdots, A_n, b$砍掉頭一個元素後得到的向量。注意它們都是$n-1$維。

​ 另外，我們用$det(d_1, d_2, \cdots, d_k)$表示由$k$維column向量所構成的$k$階行列式。

​ 由前面從2階推導至3階的經驗，考慮以下三條歸納假設：

1. 我們會計算$n-1$階行列式。
   $$D^{(n-1)} = \left| \begin{array}{cccc} d_{11} & d_{12} & \cdots & d_{1, n-1} \\ d_{21} & d_{22} & \cdots & d_{2, n-1} \\ \vdots & \vdots & & \vdots \\ d_{n-1, 1} & d_{n-1, 2} & \cdots & d_{n-1, n-1} \end{array} \right|.$$
2. $n-1$階行列式具有「交換column後加上負號」的性質。
3. 我們有$n-1$階Cramer法則。

 ​ 有了以上準備工作後，我們可以開始來討論$n$階線性方程組了。

 ​ 首先我們改寫原方程組中的後$n-1$條如下：

$$\left\{ \begin{eqnarray*} a_{22}x_2 + \cdots + a_{2n}x_n &=& b_2 - a_{21}x_1 \\ \vdots&& \\ a_{n2}x_2 + \cdots + a_{nn}x_n &=& b_n - a_{n1}x_1 \end{eqnarray*} \right.,$$

於是可根據歸納假設3解出$x_2, \cdots, x_n$

$$\displaystyle x_2 = \frac{det(\tilde{b} - x_1 \tilde{A_1}, \cdots, \tilde{A_n})}{det(\tilde{A_2}, \cdots, \tilde{A_n})}, \cdots,  x_n = \frac{det(\tilde{A_2}, \cdots, \tilde{b} - x_1 \tilde{A_1})}{det(\tilde{A_2}, \cdots, \tilde{A_n})}.$$

代回原方程組中的第一條式子，得到

$$a_{11}x_1 + a_{12} \frac{det(\tilde{b} - x_1 \tilde{A_1}, \cdots, \tilde{A_n})}{det(\tilde{A_2}, \cdots, \tilde{A_n})} + \cdots + a_{1n} \frac{det(\tilde{A_2}, \cdots, \tilde{b} - x_1 \tilde{A_1})}{det(\tilde{A_2}, \cdots, \tilde{A_n})} = b_1,$$

左右同乘以$det(\tilde{A_2}, \cdots, \tilde{A_n})$，變為

$$a_{11} x_1 det(\tilde{A_2}, \cdots, \tilde{A_n}) + a_{12} det(\tilde{b} - x_1 \tilde{A_1}, \cdots, \tilde{A_n}) + \cdots + a_{1n} det(\tilde{A_2}, \cdots, \tilde{b} - x_1 \tilde{A_1}) = b_1det(\tilde{A_2}, \cdots, \tilde{A_n}),$$

再利用$n-1$階行列式的多重線性性質，得

$$\begin{eqnarray*}&&a_{11} x_1 det(\tilde{A_2}, \cdots, \tilde{A_n}) + a_{12} det(\tilde{b}, \cdots, \tilde{A_n}) - a_{12} x_1 det(\tilde{A_1}, \cdots, \tilde{A_n}) + \cdots + a_{1n} det(\tilde{A_2}, \cdots, \tilde{b}) - a_{1n} x_1 det(\tilde{A_2}, \cdots, \tilde{A_1}) \\ &=& b_1 det(\tilde{A_2}, \cdots, \tilde{A_n}),\end{eqnarray*}$$

重新整理得

$$\begin{eqnarray*}&& \left[ a_{11} det(\tilde{A_2}, \cdots, \tilde{A_n}) - a_{12} det(\tilde{A_1}, \cdots, \tilde{A_n}) - \cdots - a_{1n} det(\tilde{A_2}, \cdots, \tilde{A_1}) \right] x_1 \\ &=& b_1 det(\tilde{A_2}, \cdots, \tilde{A_n}) - a_{12} det(\tilde{b}, \cdots, \tilde{A_n}) - \cdots - a_{1n} det(\tilde{A_2}, \cdots, \tilde{b})\end{eqnarray*}$$

對於上式中的每個$n-1$階行列式，將其中的$\tilde{A_1}$或$\tilde{b}$逐步與其前頭的元素交換，挪移到column 1的位置，並且保持其餘column的相對順序不變，則得

$$ \begin{eqnarray*} && \left[ a_{11} det(\tilde{A_2}, \cdots, \tilde{A_n}) + a_{12} (-1)^1 det(\tilde{A_1}, \tilde{A_3}, \cdots, \tilde{A_n}) + \cdots + a_{1n} (-1)^{1 + (n-2)} det(\tilde{A_1}, \tilde{A_2}, \cdots, \tilde{A_{n - 1}}) \right] x_1 \\ &=& b_1 det(\tilde{A_2}, \cdots, \tilde{A_n}) + a_{12} (-1)^1 det(\tilde{b}, \tilde{A_3}, \cdots, \tilde{A_n}) + \cdots + a_{1n} (-1)^{1 + (n-2)} det(\tilde{b}, \tilde{A_2}, \cdots, \tilde{A_{n - 1}}). \end{eqnarray*} $$

這啟發了我們定義$n$階行列式 (determinant of order n)為

$$ \begin{eqnarray*} D^{(n)} &=& \left| \begin{array}{cccc} d_{11} & d_{12} & \cdots & d_{1n} \\ d_{21} & d_{22} & \cdots & d_{2n} \\ \vdots & \vdots & & \vdots \\ d_{n1} & d_{n2} & \cdots & d_{nn} \\  \end{array} \right| \\ &=& d_{11} (-1)^{1 + 1} \left| \begin{array}{ccc} d_{22} & \cdots & d_{2n} \\ \vdots & & \vdots \\ d_{n2} & \cdots & d_{nn} \\ \end{array} \right| + d_{12} (-1)^{1+2} \left| \begin{array}{cccc} d_{21} & d_{23} & \cdots & d_{2n} \\ \vdots & & \vdots \\ d_{n1} & d_{n3} & \cdots & d_{nn} \\ \end{array} \right| + \cdots + d_{1n} (-1)^{1 + n}\left| \begin{array}{ccc} d_{22} & \cdots & d_{2, n-1} \\ \vdots & & \vdots \\ d_{n2} & \cdots & d_{n, n-1} \\ \end{array} \right|. \end{eqnarray*} $$

從而可將方才的等式改寫為

$$ \left| \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array} \right| x_1 = \left| \begin{array}{cccc} b_1 & a_{12} & \cdots & a_{1n} \\ b_2 & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ b_n & a_{n2} & \cdots & a_{nn} \end{array} \right|. $$

因為假定了方程組非奇異(non-singular)，所以上式中$x_1$的係數必非零，故

$$ x_1 = \frac{\left| \begin{array}{cccc} b_1 & a_{12} & \cdots & a_{1n} \\ b_2 & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ b_n & a_{n2} & \cdots & a_{nn} \end{array} \right|}{\left| \begin{array}{cccc} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & \cdots & a_{nn} \end{array} \right|} = \frac{det(b, A_2, \cdots, A_n)}{det(A)}. $$

如果將原方程組改寫為

$$ \left\{ \begin{eqnarray*} a_{12}x_2 + a_{11}x_1 + a_{13}x_3 + \cdots + a_{1n}x_n &=& b_1 \\ a_{22}x_2 + a_{21}x_1 + a_{23}x_3 + \cdots + a_{2n}x_n &=& b_2 \\ \vdots && \\ a_{n2}x_2 + a_{n1}x_1 + a_{n3}x_3 + \cdots + a_{nn}x_n &=& b_1 \\ \end{eqnarray*} \right. ,$$

那麼仿照以上的討論，可解得

$$ x_2 = \frac{\left|  \begin{array}{ccccc} b_1 & a_{11} & a_{13} & \cdots & a_{1n} \\ b_2 & a_{21} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & & \vdots \\ b_n & a_{n1} & a_{n3} &  \cdots & a_{nn} \end{array} \right|}{\left| \begin{array}{cccc} a_{12} & a_{11} & a_{13} & \cdots & a_{1n} \\ a_{22} & a_{21} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & & \vdots \\ a_{n2} & a_{n1} & a_{n3} &  \cdots & a_{nn} \end{array} \right|}. $$

而根據歸納假設2，有

$$ \begin{eqnarray*} x_2 &=& \frac{\left| \begin{array}{ccccc} b_1 & a_{11} & a_{13} & \cdots & a_{1n} \\b_2 & a_{21} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & & \vdots \\ b_n & a_{n1} & a_{n3} &  \cdots & a_{nn} \end{array} \right|}{\left| \begin{array}{cccc} a_{12} & a_{11} & a_{13} & \cdots & a_{1n} \\a_{22} & a_{21} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & & \vdots \\ a_{n2} & a_{n1} & a_{n3} &  \cdots & a_{nn} \end{array} \right|} = \frac{-\left| \begin{array}{ccccc} a_{11} & b_1 & a_{13} & \cdots & a_{1n} \\ a_{21} & b_2 & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & & \vdots \\ a_{n1} & b_n & a_{n3} &  \cdots & a_{nn} \end{array} \right|}{-\left| \begin{array}{cccc} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & a_{n3} &  \cdots & a_{nn} \end{array} \right|} = \frac{\left| \begin{array}{ccccc} a_{11} & b_1 & a_{13} & \cdots & a_{1n} \\ a_{21} & b_2 & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & & \vdots \\ a_{n1} & b_n & a_{n3} &  \cdots & a_{nn} \end{array} \right|}{\left| \begin{array}{cccc} a_{11} & a_{12} & a_{13} & \cdots & a_{1n} \\a_{21} & a_{22} & a_{23} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & & \vdots \\ a_{n1} & a_{n2} & a_{n3} &  \cdots & a_{nn} \end{array} \right|} \\ &=& \frac{det(A_1, b, A_3, \cdots, A_n)}{det(A)}. \end{eqnarray*} $$

其餘$x_3, \cdots, x_n$的討論亦類似，得

$$ x_3 = \frac{det(A_1, A_2, b, A_4, \cdots, A_n)}{det(A)}, \cdots, x_n = \frac{det(A_1, \cdots, A_{n-1}, b)}{det(A)}. $$

結論：

1. $n$階行列式是靠$n-1$階行列式的線性組合所定義出來的：
   
   $$ \begin{eqnarray*} D^{(n)} &=& \left| \begin{array}{cccc} d_{11} & d_{12} & \cdots & d_{1n} \\ d_{21} & d_{22} & \cdots & d_{2n} \\ \vdots & \vdots & & \vdots \\ d_{n1} & d_{n2} & \cdots & d_{nn} \\  \end{array} \right| \\  &=& d_{11} (-1)^{1 + 1} \left| \begin{array}{ccc} d_{22} & \cdots & d_{2n} \\ \vdots & & \vdots \\ d_{n2} & \cdots & d_{nn} \\ \end{array} \right| + d_{12} (-1)^{1+2} \left| \begin{array}{cccc} d_{21} & d_{23} & \cdots & d_{2n} \\ \vdots & & \vdots \\ d_{n1} & d_{n3} & \cdots & d_{nn} \\ \end{array} \right| + \cdots + d_{1n} (-1)^{1 + n}\left| \begin{array}{ccc} d_{22} & \cdots & d_{2, n-1} \\ \vdots & & \vdots \\ d_{n2} & \cdots & d_{n, n-1} \\ \end{array} \right|. \end{eqnarray*} $$
2. Cramer公式：對於非奇異的$n$階線性方程組
   $$ \left\{ \begin{eqnarray*} a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n &=& b_1 \\ a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n &=& b_2 \\ \vdots&& \\ a_{n1}x_1 + a_{n2}x_2 + \cdots + a_{nn}x_n &=& b_n \end{eqnarray*} \right. , $$
   其解為
   $$ x_i = \frac{det(\cdots, A_{i-1}, b, A_{i+1}, \cdots)}{det(A)}. $$

  

參考文獻

[1] 朱富海，问题引导的代数学: 行列式的多样性，知乎專欄《數林廣記》

(最後更新：2020/06/05)

大栗博司，《用數學的語言看世界》，第1章，第2節，賭博的不敗之法，公式推導

加州理工學院物理系的大栗博司教授為其女兒撰有《数学の言葉で世界を見たら》一書(介紹頁面連結)(簡體中譯版：《從數學的語言看世界》，人民郵電出版社，介紹頁面連結；繁體中譯版：《用數學的語言看世界：一位博士爸爸送給女兒的數學之書，發現數學真正的趣味、價值與美》，臉譜出版社，介紹頁面連結)。

此書深入淺出，讀來彷若一位和藹的父親以親切的語言為愛女講解數學。美中不足之處在於本書部分內容連載於大栗教授的網站，不僅讀來不甚方便，一個更嚴重的問題是那些補充資料都是日文，無論是簡體還是繁體翻譯版都沒有譯出，在在顯示出規劃此書的編輯的眼光不夠深遠。人民郵電出版社的介紹頁面的討論區中，有大陸網友留言：「作者在个人网站补充的一些内容会有翻译吗？日文实在看不懂，要是英文就好了」

我手上的版本是簡體中文翻譯版。我覺得無論是印刷還是排版都勝過台版，更重要的是，簡體版的網站上附有勘誤，這是台灣出版社完全不及中國的。

第1章第2節〈賭博的不敗之法〉的公式推導是刊於網站的補充內容。我不會日文，只能靠著google翻譯，配著數學式去猜測內容。以下內容雖是該公式的推導，但並非大栗教授原文的全譯，一半混雜了我自己的推導，記號也與大栗教授原文略有差異。

首先，假定$m \ge 1$。對於擲出第1次的結果，有2種可能性：以p的機率擲出正面，資金變為$m+1$元；以q的機率擲出反面，資金變為$m-1$元。再從第2次開始，如果是從$m+1$元開始，那麼按照書中的定義，變為N元的機率為$P(m+1, N)$；從$m-1$元開始，變為N元的機率則是$P(m-1, N)$。因此得到遞迴關係式：
$$P(m, N) = p \times P(m+1, N) + q \times P(m-1, N).$$
不難理解$P(0, N) = 0, P(N, N) = 1$。前者的原因為0元毫無翻本的可能；後者好比一起跑就在終點。

(類似的遞迴之推導另可參考我的文章〈台中區國立高級中學103學年度大學入學第一次學科能力測驗聯合模擬考，選填2〉。)

為方便計算，以下記$P(k, N) = a_k$。所以根據上文的討論，我們要求解的即是以下的遞迴式：
$$\left\{ \begin{align*} a_k &= p \times a_{k+1} + q \times a_{k-1}, k \ge 1 \\ a_0 &=0 \\ a_N &= 1 \end{align*} \right.$$
對於遞迴關係$a_k = p \times a_{k+1} + q \times a_{k-1}$，變形為
$$p \times a_{k+1} = a_k - q \times a_{k-1}.$$
左右同時減去$p \times a_k$，於是
$$p \times a_{k+1} - p \times a_k = a_k  - p \times a_k - q \times a_{k-1},$$
注意到$p+q = 1$，所以得
$$p(a_{k+1} - a_k) = q(a_k - a_{k-1}).$$
此為等比關係！故得
$$a_{k+1} - a_k = \left( \frac{q}{p} \right)^k (a_1 - a_0).$$
代入初始條件$a_0 = 0, a_N = 1$，有
$$a_N = \left[ 1 + \left( \frac{q}{p} \right) + \cdots + \left( \frac{q}{p} \right)^{N-1} \right] a_1$$
與
$$a_m = \left[ 1 + \left( \frac{q}{p} \right) + \cdots + \left( \frac{q}{p} \right)^{m-1} \right] a_1.$$
故
\begin{align*}  a_m &=  \left[ 1 + \left( \frac{q}{p} \right) + \cdots + \left( \frac{q}{p} \right)^{m-1} \right] a_1 \\ &= \left[ 1 + \left( \frac{q}{p} \right) + \cdots + \left( \frac{q}{p} \right)^{m-1} \right] \times \frac{a_N}{1 + \left( \frac{q}{p} \right) + \cdots + \left( \frac{q}{p} \right)^{N-1}} \\ &= \frac{1 - \left( \frac{q}{p} \right)^m}{1 - \frac{q}{p}} \times \frac{1}{1 + \left( \frac{q}{p} \right) + \cdots + \left( \frac{q}{p} \right)^{N-1}} \\ &= \frac{1 - \left( \frac{q}{p} \right)^m}{1 - \frac{q}{p}} \times \frac{1 - \frac{q}{p}}{1 - \left( \frac{q}{p} \right)^N} \\ &= \frac{1 - \left( \frac{q}{p} \right)^m}{1 - \left( \frac{q}{p} \right)^N}. \end{align*}

(證明終了)

參考資料

[1] 大栗博司，第１話　補遺：①　ギャンブラーの破産問題。

Apostol Linear Algebra Exercise 0.13.2

題目

若一個實數$x$有性質$x^2=x+1$，用歸納法證明存在函數$f(n)$，使得對所有整數$n \geq 1$，都有$x^{n+1} = f(n+1)x +f(n)$。

解答

• 分析

$n=1$時，所要證明的的式子為
$$x^{1+1}=f(1+1)x + f(1),$$
也就是
$$x^2 = f(2) x + f(1).$$

比對題目所給的條件$x^2 = x +1$，合理猜測$f(2) = 1, f(1) = 1$。

現在看$n=2$的情況。此時要有
\begin{align*}
x^{2+1} &= f(2+1)x + f(2), \\
x^3 &= f(3) x + 1, \\
f(3) &= \frac{x^3 - 1}{x} \\
&= \frac{x \cdot x^2 - 1}{x} \\
&= \frac{x \cdot (x+1) -1}{x} \\
&= \frac{x^2 + x -1}{x} \\
&= \frac{(x+1)+ x -1}{x} \\
&= \frac{2x}{x} \\
&= 2.
\end{align*}
(注意顯然$x \neq 0$，所以$\frac{\square}{x}$是有意義的)而我們有
$$x^3 = 2x + 1.$$

再繼續看看$n=3$的情況。
\begin{align*}
x^{3+1} &= f(3+1)x + f(3) \\
x^4 &= f(4)x + 2 \\
f(4) &= \frac{x^4 - 2}{x} \\
&= \frac{x \cdot x^3 - 2}{x} \\
&= \frac{x \cdot (2x + 1) -2}{x} \\
&= \frac{2x^2 + x - 2}{x} \\
&= \frac{2(x+1) + x - 2}{x} \\
&= \frac{3x}{x} \\
&= 3.
\end{align*}而我們有
$$x^4 = 3x + 2.$$

彙整以上的計算結果如下
$$f(1) = 1, f(2) = 1, f(3) = 2, f(4) =3.$$
這些結果似乎構成Fibonacci數列，故猜測$f(5) = 5$。

計算$n=4$的情況來確認看看。
\begin{align*}
x^{4+1} &= f(4+1)x + f(4) \\
x^5 &= f(5)x + 3 \\
f(5) &= \frac{x^5 - 3}{x} \\
&= \frac{x \cdot x^4 - 3}{x} \\
&= \frac{x \cdot (3x + 2) -3}{x} \\
&= \frac{3x^2 + 2x - 3}{x} \\
&= \frac{3(x+1) + 2x - 3}{x} \\
&= \frac{5x}{x} \\
&= 5.
\end{align*}
而我們有
$$x^5 =5x + 3.$$

果真有$f(5) = 5$！

所以我們的猜測有可能正確！

甚至，由Fibonacci數列的通式可猜測
$$f(n) = \frac{\sqrt{5}}{5} \cdot \left[\left(\frac{1 + \sqrt{5}}{2}\right)^{n} - \left(\frac{1 - \sqrt{5}}{2}\right)^{n}\right].$$
(如此就把函數$f(n)$的顯式給表示出來)參考維基百科關於Fibonacci數列的條目。

• 正式解答

$n=1$時，由條件$x^2 = x + 1$可取$f(1) = 1, f(2) = 1$。

假定命題對於$n - 1$時成立，亦即存在函數$f$使得有$x^{(n-1)+1} = f\left[ (n-1) + 1 \right]x + f(n-1)$，這也意味著我們確定了$f(n-1)$與$f(n)$的值。

在$n$時，
\begin{align*}
x^{n+1} &= x \cdot x^n &[\text{指數的定義}] \\
&= x \cdot x^{(n - 1) + 1} & \\
&= x \cdot \left\{f[(n - 1) + 1]x + f(n-1) \right\} &[\text{歸納假設}] \\
&= x \cdot \left[ f(n)x + f(n-1) \right] & \\
&= f(n) x^2 + f(n-1) x &[\text{分配律}]\\
&= f(n) (x + 1) + f(n-1)x &[x\text{滿足的性質}]\\
&= \left[ f(n-1) + f(n) \right]x + f(n). &
\end{align*}
因為$f(n-1)$與$f(n)$的值都已確定，由此可定義
$$f(n + 1) = f(n-1) + f(n).$$
亦即$f(n+1)$之存在性由$f(n-1)$與$f(n)$所保證。

由數學歸納法證明了命題。

(證明終了)

105，指考，數學甲，多選7

==問題==

在實數線上，動點A從原點開始往正向移動，動點B從8的位置開始往負向移動。兩個動點每一秒移動一次，已知第一秒A、B移動的距離分別為1、4，且A、B每次移動的距離分別為其前一次移動距離的$\frac{1}{2}$倍、$\frac{1}{3}$倍。令$c_n$為第$n$秒時A、B的中點位置。請選出正確選項。
(1) $c_1 = \frac{5}{2}$
(2) $c_2 > c_1$
(3) 數列$\left< c_{n+1} - c_n \right>$是一個等比數列
(4) $\displaystyle \lim_{n \rightarrow \infty} c_n = 2$
(5) $c_{1000} > 2$

[105，指考，數學甲，多選7]

==解答==

假定第$n$秒時，點A的位置為$a_n$，點B的位置為$b_n$。

於是$a_1 = 1, b_1 = 4$。

再假定點A於第$n$秒內的移動量(考慮正負)為$d_n$，點B於第$n$秒內的移動量(考慮正負)為$\delta_n$。

於是$d_1 = 1, \delta_1 = -4$，然後$d_2 = \frac{1}{2}, \delta_2 = -4 \cdot \frac{1}{3}$，因此可推論$d_n = \left( \frac{1}{2} \right)^{n-1}, \delta_n = -4 \cdot \left( \frac{1}{3} \right)^{n-1}$。

根據題意與假設，可得

$$a_n = a_{n-1} + d_n, b_n = b_{n-1} + \delta_n.$$

代入前述對$d_n$與$\delta_n$的計算，可得

$$a_n = a_{n-1} + \left( \frac{1}{2} \right)^{n-1}, b_n = b_{n-1} -4 \cdot \left( \frac{1}{3} \right)^{n-1}.$$

接著，由於
\begin{eqnarray*}
a_2 - a_1 &=& \left( \frac{1}{2} \right)^1 \\
a_3 - a_2 &=& \left( \frac{1}{2} \right)^2 \\
  &\vdots&  \\
a_n - a_{n-1} &=& \left( \frac{1}{2} \right)^{n-1}
\end{eqnarray*}
從而
\begin{eqnarray*}
a_n - a_1 &=& \left( \frac{1}{2} \right)^1 + \left( \frac{1}{2} \right)^2 + \cdots + \left( \frac{1}{2} \right)^{n-1} \\
  &=& \frac{\frac{1}{2} \cdot \left[ 1 - \left( \frac{1}{2} \right)^{n-1} \right]}{1 - \frac{1}{2}} \\
  &=& 1 - \frac{1}{2^{n-1}}
\end{eqnarray*}
故
$$a_n = 2 - \frac{1}{2^{n-1}}.$$

另外一方面，由於
\begin{eqnarray*}
b_2 - b_1 &=& -4 \cdot \left( \frac{1}{3} \right)^1 \\
b_3 - b_2 &=& -4 \cdot \left( \frac{1}{3} \right)^2 \\
  &\vdots&  \\
b_n - b_{n-1} &=& -4 \cdot \left( \frac{1}{3} \right)^{n-1}
\end{eqnarray*}
從而
\begin{eqnarray*}
b_n - b_1 &=& -4 \cdot \left[ \left( \frac{1}{3} \right)^1 + \left( \frac{1}{3} \right)^2 + \cdots + \left( \frac{1}{3} \right)^{n-1} \right] \\
  &=& -4 \cdot \frac{\frac{1}{3} \cdot \left[ 1 - \left( \frac{1}{3} \right)^{n-1} \right]}{1 - \frac{1}{3}} \\
  &=& -2 + \frac{2}{3^{n-1}}
\end{eqnarray*}
故
$$b_n = 2 + \frac{2}{3^{n-1}}.$$

那麼
$$c_n = \frac{a_n + b_n}{2} = \frac{2 - \frac{1}{2^{n-1}} + 2 + \frac{2}{3^{n-1}}}{2} = 2 - \frac{1}{2^n} + \frac{1}{3^{n-1}}.$$

以下開始處理各選項。

(1) $c_1 = 2 - \frac{1}{2^1} + \frac{1}{3^{1-1}} = 2 - \frac{1}{2} + 1 = \frac{5}{2}$。正確。

(2) $c_2 = 2 - \frac{1}{2^2} + \frac{1}{3^{2-1}} = 2 - \frac{1}{4} + \frac{1}{3} = \frac{25}{12} < \frac{30}{12} = \frac{5}{2} = c_1$。錯誤。

(3) $c_{n-1} - c_n = \left( 2 - \frac{1}{2^{n+1}} + \frac{1}{3^n} \right) - \left( 2 - \frac{1}{2^n} + \frac{1}{3^{n-1}} \right) = \frac{1}{2^{n+1}} - \frac{2}{3^n}$。錯誤。

(4) $\displaystyle \lim_{n \rightarrow \infty} c_n = \lim_{n \rightarrow \infty} \left( 2 - \frac{1}{2^n} + \frac{1}{3^{n-1}} \right) = 2 - 0 + 0 = 0$(請注意，$\displaystyle \lim_{n \rightarrow \infty} \frac{1}{2^n} = 0$且$\displaystyle \lim_{n \rightarrow \infty} \frac{1}{3^{n-1}} = 0$，故可使用極限的四則運算)。正確。

(5) $c_{1000} = 2 - \frac{1}{2^{1000}} + \frac{1}{3^{999}}$，由於$\log 2^{1000} = 1000 \cdot \log 2 \approx 1000 \cdot 0.301 = 301$，$\log 3^{999} = 999 \cdot \log 3 \approx 999 \cdot 0.4771 = 476.6229$，故$2^{1000}< 3^{999}$，從而$- \frac{1}{2^{1000}} + \frac{1}{3^{999}} = \frac{1}{3^{999}} - \frac{1}{2^{1000}} < 0$，因此$c_{1000} = 2 + \text{負數} < 2$。錯誤。

選(1)、(4)。

(解答結束)

台中區國立高級中學103學年度大學入學第一次學科能力測驗聯合模擬考，選填2

=題目=

紅綠建設公司在台中打算建造10層樓高的總部大樓，為了凸顯公司特色，決定每層樓只能用紅色或綠色的油漆來粉刷，而且不能有連續兩層是紅色的，則他們有幾種可能的粉刷方式？

=解答=

俞克斌先生的解法是插空隙，請參考http://web.tcfsh.tc.edu.tw/jflai/rab/RA367ans.swf。

事實上本題可以考慮遞迴解法。

定義全部n層樓時，塗法為$a_n$種。

先對幾個比較小的n值來計算。

$n=1$時，因為可以塗紅色或綠色，所以$a_1=2$。

$n=2$時，從一樓開始記起，合乎條件的塗色方式有：「綠綠」(1樓為綠色、2樓為綠色)、「綠紅」(1樓為綠色、2樓為紅色)、「紅綠」(1樓為紅色、2樓為綠色)。所以$a_2=3$。

$n=3$時，合乎條件的塗色方式有：

$(1^{\circ})$ 3綠：「綠綠綠」

$(2^{\circ})$2綠1紅：「綠綠紅」、「綠紅綠」、「紅綠綠」

$(3^{\circ})$1綠2紅：「紅綠紅」

所以$a_3=5$。

彙整以上結果有：$a_1=2, a_2=3, a_3=5$。可以猜測$a_n=a_{n-1}+a_{n-2}, n \geq 3$。

事實上，當全部樓層為n層時(n當然要足夠大，總不會對很小的n來討論)，最後一層，也就是第n層，其顏色只有2種可能，綠色或是紅色。

若是第n層為綠色，那麼向前推，第$n-1$層會是什麼顏色呢？其實紅跟綠都可以的。換句話說，如果確定第n層為綠色，那麼只需考慮前面全部$n-1$層的塗法，因此這時的塗法數為$a_{n-1}$。

若是第n層為紅色，那麼根據題目條件「不能有連續兩層是紅色的」，可以推知第$n-1$層必定是綠色。再繼續向前推，類似於方才的討論，只需考慮前面全部$n-2$層的塗法，因此這時的塗法數為$a_{n-2}$。

我們將全部n層時的塗法分為兩大類，一類是「第n層樓為綠色」，此時塗法數為$a_{n-1}$；另一類是「第n層樓為綠色」，此時塗法數為$a_{n-2}$。所以得到

$\left \{ \begin{array}{l} a_1=2, a_2=3, \\ a_n=a_{n-1}+a_{n-2}, n \geq 3.\end{array} \right.$

這是Fibonacci數列。題目所求的$a_{10}$，基本上可以直接用手算，列表如下：

2, 3, 5, 8, 13, 21, 34, 55, 89, 144

故所求$a_{10}=144$。

當然，利用Fibonacci數列的一般項公式，可以輕易算出任何n值時的$a_n$，我個人偏好的生成函數解法，請參考https://ccjou.wordpress.com/2013/10/23/%E9%81%9E%E8%BF%B4%E9%97%9C%E4%BF%82%E5%BC%8F%E7%9A%84%E6%AF%8D%E5%87%BD%E6%95%B8%E8%A7%A3%E6%B3%95/的例三。