Sign in
Please select an account to continue using cracku.in
↓ →
Join Our JEE Preparation Group
Prep with like-minded aspirants; Get access to free daily tests and study material.
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}$$.
Predict your JEE Main percentile, rank & performance in seconds
Educational materials for JEE preparation
Ask our AI anything
AI can make mistakes. Please verify important information.
AI can make mistakes. Please verify important information.