Join WhatsApp Icon JEE WhatsApp Group
Question 25

For $$n \geq 2$$, let $$S_n$$ denote the set of all subsets of $$\{1, 2, \ldots, n\}$$ with no two consecutive numbers. For example $$\{1, 3, 5\} \in S_6$$, but $$\{1, 2, 4\} \notin S_6$$. Then $$n(S_5)$$ is equal to ______.


Correct Answer: 13

Let $$a_n$$ denote the number of subsets of $$\{1,2,\ldots ,n\}$$ in which no two elements are consecutive.
We have to find $$a_5$$.

Step 1 Establish a recurrence for $$a_n$$.
Consider whether the element $$n$$ is present in a subset.

• Subsets that do not contain $$n$$: these are exactly the admissible subsets of $$\{1,2,\ldots ,n-1\}$$. The count is $$a_{\,n-1}$$.

• Subsets that do contain $$n$$: then $$n-1$$ cannot be present (to avoid consecutiveness). After fixing $$n$$, the remaining admissible part comes from $$\{1,2,\ldots ,n-2\}$$. The count is $$a_{\,n-2}$$.

Add the two mutually exclusive cases:
$$a_n = a_{\,n-1} + a_{\,n-2}$$ $$-(1)$$

Step 2 Set the initial values.
For $$n = 1$$: admissible subsets are $$\emptyset$$ and $$\{1\}$$, so $$a_1 = 2$$.
For $$n = 2$$: admissible subsets are $$\emptyset, \{1\}, \{2\}$$, so $$a_2 = 3$$.

Step 3 Use the recurrence to reach $$n = 5$$.

Using $$(1)$$:
$$a_3 = a_2 + a_1 = 3 + 2 = 5$$
$$a_4 = a_3 + a_2 = 5 + 3 = 8$$
$$a_5 = a_4 + a_3 = 8 + 5 = 13$$

Step 4 Conclusion.
Thus, the number of subsets of $$\{1,2,3,4,5\}$$ with no two consecutive elements is $$\boxed{13}$$.

Get AI Help

50,000+ JEE Students Trusted Our Score Calculator

Predict your JEE Main percentile, rank & performance in seconds

Ask AI

Ask our AI anything

AI can make mistakes. Please verify important information.