==問題==
集合{1,2,3}總共有23=8個部分集合,其中有些部分集合所含的元素中沒有任何兩個元素的大小之差為1,這樣的部分集合有∅,{1},{2},{3},{1,3}等五個。對任意正整數n,假設an代表集合{1,2,⋯,n}的所有部分集合中,不含大小之差為1的兩個元素的部分集合個數;我們已知a3=5,試用遞迴的方式定義數列a1,a2,a3,⋯,然後利用本篇的方法求出an的一般式。
==解答==
n時,將集合{1,2,⋯,n}滿足題目所求的部分集合所構成的集合記為Dn。
下面列出前幾個Dn。
D1={∅,{1}},D2={∅,{1},{2}},D3={∅,{1},{2},{3},{1,3}},D4={∅,{1},{2},{3},{4},{1,3},{1,4},{2,4}},D5={∅,{1},{2},{3},{4},{5},{1,3},{1,4},{1,5},{2,4},{2,5},{3,5},{1,3,5}}.
於是可知
a1=2,a2=3,a3=5,a4=8,a5=13.
猜測{an}為Fibonacci數列。
下面來證明{an}確實為Fibonacci數列。
首先觀察n=5的情形,在D5中,∅,{1},{2},{3},{4},{1,3},{1,4},{2,4}都恰好是D4的所有元素,而剩下的{5},{1,5},{2,5},{3,5},{1,3,5},如果把5刪去,變成∅,{1},{2},{3},{1,3},恰好就是D3的所有元素。所以自然有
a5=a4+a3.
從而an+2=an+1+an應該會成立。
對於充分大的n,在Dn+2中,依據「是否包含元素n+2」可分為兩大類,我們將含有元素n+2的子集合所構成的集合記為An+2,而不含元素n+2的子集合所構成的集合記為Bn+2。所以顯然有
Dn+2=An+2∪Bn+2,且An+2∩Bn+2=∅.
在An+2中,每個成員集合都含有元素n+2,而第二大的元素要嘛不存在,要嘛不超過n,因此如果將所有成員集合中的元素n+2刪除,於是這些集合就都會變成Dn的元素。
另外,在Dn中,由於每個成員集合中所包含的數最大不超過n,因此如果在每個成員集合中的尾巴添上n+2,那麼這些新構造出來的集合都會是Dn+2的元素。
以上我們構造出An+2與Dn之間的一個雙射(bijection),故|An+2|=|Dn|=an。
接著來討論Bn+2
由於其中每個成員集合皆不包含n+2,所以要不是空集合,要不所含的數最大不超過n+1,同時因為Bn+2要滿足條件「部分集合所含的元素中沒有任何兩個元素的大小之差為1」,於是可斷定Bn+2根本就是Dn+1,從而|Bn+2|=|Dn+1|=an+1。
綜上所述,我們確實得到
an+2=an+1+an,(n≥1).
此為Fibonacci數列關係式,其一般式的解法可見課文第149頁,在此不加贅述。
(解答終了)