主题：向各位高人求救一道离散数学的证明题：急用！谢谢！ -- 锦候

你那个公式的f(n) 处理的是包含n-1个元素集合的所有不相邻元素子集的数目。

第一项也可以写成 (n-1,0).这样，每一项就是就是刚好包含i个不相邻元素子集的数目。i=0到K。

这个也需要证明，但很简单，自己完成吧。

剩下的就是，证明包含n个元素的不相邻元素子集的数目是兔子数列。

只要证明递推公式就可以了。

这也不难，假定任意一个集合A，那么n要么属于A要么不属于

如果不属于，那么集合A必然对n-1的情况有效。

如果属于，那么n-1必然不在其中，此时再从A中拿掉n,则必然对于n-2的情况有效。

于是 f(n)=f(n-1)+f(n-2)

我这个方法好处是比较直观，能理解其中的数学内涵。

Doob兄的方法做起来肯定更快，直接代入公式，计算则可。