一道数列型组合数学题

这是2014年东城区一模压轴题： 已知集合$\{1,2,3,4,\cdots,n\}(n\geqslant 3$，若该集合具有下列性质的子集：每个子集至少含有$2$个元素，且每个子集中任意两个元素之差的绝对值大于$1$，则称这些子集为离散子集，记离散子集的个数为$a_n$．

（1）当$n=5$时，写出所有离散子集；

（2）求$a_{10}$;

（3）记 $$S_n=\frac {a_3}{2^3}+\frac {a_4}{2^4}+\cdots+\frac {a_n}{2^n},$$ 求证：$S_n<2$．

（1）（2）略； 我们容易得到 $$a_n=\mathrm C_{n-1}^2+\mathrm C_{n-2}^3+\mathrm C_{n-3}^4+\cdots$$ 对于这种许多组合数的和，可以利用杨辉三角找规律： 从图中容易得到递推规律： $$a_{n+2}=a_{n+1}+a_n+n.$$ 于是 $$\frac{a_{n+2}}{2^{n+2}}=\frac 12\cdot\frac{a_{n+1}}{2^{n+1}}+\frac 14\cdot\frac{a_n}{2^n}+\frac n{2^{n+2}}.$$ 两边求和，有 $$S_{n+2}=\frac 12S_{n+1}+\frac 14S_n+\sum_{k=1}^n\frac k{2^{k+2}}<\frac 12S_{n+1}+\frac 14S_n+\frac 12.$$ 所以由$S_3,S_4<2$可递推得$S_n<2$．

点评    已知通项时，一般先放缩后求和；已知递推时，一般先求和再放缩．