斐波那契数列的第n项同时也代表了集合…没看懂就句话,斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数.

Question

斐波那契数列的第n项同时也代表了集合…没看懂就句话,
斐波那契数列的第n项同时也代表了集合{1,2,...,n}中所有不包含相邻正整数的子集个数.

Answer 1

集合{1,2,3.,n} 中不包含相邻正整数的子集个数
可以分成两种情况：
1）子集中不包含n,则子集个数为{1,2,3...n-1}中不包含相邻正整数的子集个数
2）子集中包含n,则子集个数等于{1,2,3,4...n-2}中不包含相邻正整数的子集个数
明显这个递归关系就是斐波那契额序列的递归关系f(n)=f(n-1)+f(n-2)