悬赏!!急求一道数学证明题的证明过程!!

来源:百度知道 编辑:UC知道 时间:2024/06/01 17:52:16
设n∈N,则{1,2,…n}中不含相邻数的子集为F(n+2)

按照你的观点F[1]=1,F[2]=1,F[n]=F[n-1]+F[n-2](n>2)了,

显然当
k=1,子集包括空集,{1},F[1+2]=F[3]=2
k=2,子集包括空集,{1},{2},F[2+2]=F[4]=3
k=3时,子集包括空集,{1},{2},{3},{1,3},F[3+2]=F[5]=5
结论均成立,

假设对于所有的n≤k-1(k>1)时结论均成立,
即设n≤k-1,{1,2,…n}中不含相邻数的子集为F(n+2),则
当n=k时,
满足条件的子集分为两类,
不含数字k的子集相当于{1,2,…k-1}的子集,总数为F[(k-1)+2],
含k的子集中必含k,又必不含(k-1),因为k与(k-1)相邻,所以我们不需要管k和(k-1),
只需要求出,{1,2,…k-2}的子集,然后给每个子集中都添上k就可以了.这样的子集总数为F[(k-2)+2],
于是{1,2,…k}中不含相邻数的子集为F[(k-1)+2]+F[(k-2)+2]=F[k+2].
由①②得结论成立.
证毕.

题目没说清楚。