For n 2, let Sn denote the set of all subsets of \1, 2, , n\ with no two consecutive numbers. For example \1, 3, 5\ S6, but \1, 2, 4\ S6. Then n(S5) is equal to
Answer
13
Solution
Number of k-element subsets of \1, 2, , n\ with no two consecutive numbers = n-k+1Ck.
For n = 5:
k = 0: 6C0 = 1 (empty set)
k = 1: 5C1 = 5
k = 2: 4C2 = 6
k = 3: 3C3 = 1 (only 1, 3, 5)
n(S5) = 1 + 5 + 6 + 1 = 13
(Equivalently n(Sn) = n(Sn-1) + n(Sn-2): 3, 5, 8, 13 for n = 2, 3, 4, 5.)
Answer: 13