フィボナッチ数列の演習２

今回の例題は，表現が違うだけで，前回の「フィボナッチ数列の演習」
と同じ内容の問題です．

正の整数の集合$${S_{n}={\{}1,2, \ldots ,n{\}}}$$の部分集合で，連続する整数を含まない集合の数$${a_{n}}$$を求めなさい．ただし，どの集合にも空集合$${ \phi }$$は含まれ,空集合は１つと数えます．

＜この例題は，Fibanacci and Lucas Numbers with Applications, Thomas Koshyより引用＞

（実験）

$${n=0,1,2,3,4}$$の場合

$${a_{n}}$$は$${a_{0}=1, a_{1}=2}$$より始まるフィボナッチ数列$${a_{n}=a_{n-1}+a_{n-2}}$$になることが予想できる．フィボナッチ数列の定義式は再帰的な関係式であるので，数学的帰納法に類似している．

$${A}$$を連続する整数を含まない$${S_{n}}$$の任意の部分集合とします．
２つの場合に分けて考察しましょう．

（１）$${n \in A}$$のとき，すなわち，$${n}$$が$${A}$$に含まれている場合には，$${n-1 \notin A}$$（$${A}$$は$${n-1}$$を含むことができない）．従って，$${A}$$は連続する整数を含まない集合$${S_{n-2}}$$の要素に$${n}$$を追加したものになる．
定義により，$${S_{n-2}}$$の要素の数は$${a_{n-2}}$$であるので，$${S_{n}}$$のうちで（１）の場合の要素の数は$${a_{n-2}}$$である．

（２）$${n \notin A}$$のとき，すなわち，$${n}$$が$${A}$$に含まれていない場合の$${S_{n}}$$の要素数は，$${S_{n-1}}$$と一致し，定義により$${a_{n-1}}$$である．

これらの２つの場合は，互いに排他的であるので，加算原理により,
$${a_{n}=a_{n-1}+a_{n-2}}$$が得られる．

ーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーーー
◆前回の練習問題の解答は，$${a_{n}/2^{n}}$$です．