許介彥《數學悠哉遊》，第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頁，在此不加贅述。

（解答終了）