隣接数を含まない自然数の選び方の総数

｛1,2,…,ｎ｝の空でない部分集合のうち、隣り合う二つの数を含まないようなものはいくつあるか。（Marbel_NIKO様）

条件を満たす部分集合と空集合を合わせた集合を S(n), その要素数を A_n とする。
S(n+2) の要素は S(n+1) の要素そのものと、S(n) の要素に n+2 をつけ加えたものである。
よって、A_(n+2) = A_(n+1) + A_(n)

また、
S(1) = { {1}, {} } より A_1 = 2
S(2) = { {1}, {2}, {} } より A_2 = 3

つまり、F_n をフィボナッチ数として、
A_n = F_(n+2) = { φ^(n+2) - (-φ)^(-n-2) }/√5
ただしφは黄金比 (1+√5)/2

求める個数はこれから空集合を除いたものなので、
F_(n+2) - 1 = { φ^(n+2) - (-φ)^(-n-2) }/√5 - 1 個