For n ≥ 2, let Sₙ denote the set of all subsets of {1,2, …, n} with no two consecutive numbers. For example {1,3,5} ∈ S₆, but {1,2,4} ∉ S₆. Then n(S₅) is equal to ________

Solution

Maths sir · 2 steps

Sort the subsets by size, and count each size with the gap trick C(n-k+1, k).

1. Gap trick. Pick k numbers from {1, …, n} with no two consecutive. Place the n-k numbers you do not pick in a row. They leave n-k+1 gaps, and each chosen number takes its own gap.

   Number of such k-subsets = C(n-k+1, k)

   Size k	Count C(6-k, k)	Subsets
   0	C(6, 0) = 1	the empty set
   1	C(5, 1) = 5	{1}, {2}, {3}, {4}, {5}
   2	C(4, 2) = 6	{1,3}, {1,4}, {1,5}, {2,4}, {2,5}, {3,5}
   3	C(3, 3) = 1	{1,3,5}
   4 or more	0	impossible, there is not enough room

2. So. n(S₅) = 1 + 5 + 6 + 1 = 13. The empty set counts because it has no two consecutive numbers.

The common slip: 12. Leaving out the empty set gives 12. It has no two consecutive numbers, so it belongs in S₅.

The idea to keep. For no two consecutive picks, put down the unpicked numbers first and choose gaps between them. The total over all sizes follows the Fibonacci pattern 2, 3, 5, 8, 13, …

Answer from the NTA final answer key. Solution by PrepWiser.