每日一题3

zhangyuong · 发表于 2009-8-9 22:14:32

集合Sn={1,2...,n}的子集中，若不含两个连续的自然数，则称为“好子集”。问Sn中有多少个好子集

xz5024 · 发表于 2009-8-9 22:35:39

不会强大的玻璃给我讲讲

元蛟 · 发表于 2009-8-10 07:07:00

好眼熟

EMP震荡波 · 发表于 2009-8-10 10:43:53

2ⁿ-(A_n-1¹+A_n-1²+…+A_n-1^n-1)

高斯门徒 · 发表于 2009-8-10 11:30:07

本帖最后由 474394820 于 2009-8-10 20:24 编辑

设Sn中有an个好子集
当n=1时an=2
当n=2时an=3
当n=3时an=5
当n=4时an=8
..............
由此猜想a(n+2)=a(n+1)+an
证明:若不含n+2则有a(n+1)个好子集
若含n+2必不含n+1因为Sn={1,2...,n}有an个好子集
把n+2放进去还是an个好子集
所以a(n+2)=a(n+1)+an得证
由特征方程x^2=x+1得x1=(1-根号5)/2 x2=(1+根号5)/2
由an=A*x1^(n-1)+Bx2^(n-1)得A=(5-2根号5)/5 B=(5+2根号5)/5
所以an=((5-2根号5)/5)*((1-根号5)/2)^(n-1)+((1+2根号5)/2)*((1+根号5)/2)^(n-1)

zhangyuong · 发表于 2009-8-10 16:33:44

楼上正确

阿南纳比 · 发表于 2010-10-17 12:30:54

先把它按元素个数分集而已还要考虑 n的正偶

阿南纳比 · 发表于 2010-10-17 12:32:12

不用全分下来找普遍规律即可

帐号		自动登录	找回密码
密码			注册

[已解决] 每日一题3