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 \underline\hspace2cm

Sets and Relations PYQ — JEE Main 2025 · 7 Apr · Shift 1 · Q49 with Solution

View written solutionFree

Correct answer: 13

We need to find $n(S_5)$ , i.e. the number of subsets of $\{1,2,3,4,5\}$ having no two consecutive elements.
Let $a_n = n(S_n)$ .

We form a recurrence based on whether a valid subset of $\{1,2,\dots,n\}$ contains $n$ or not.

Case 1: The subset does not contain $n$ . Then it is simply a valid subset of $\{1,2,\dots,n-1\}$ . Number of such subsets = $a_{n-1}$ .
Case 2: The subset contains $n$ . Then it cannot contain $n-1$ (since no two consecutive numbers are allowed). So the remaining elements must form a valid subset of $\{1,2,\dots,n-2\}$ . Number of such subsets = $a_{n-2}$ .

Hence,

a_n = a_{n-1} + a_{n-2}.

For $n=1$ : Valid subsets of $\{1\}$ are $\emptyset,\ \{1\}$ so $a_1=2.$
For $n=2$ : Valid subsets of $\{1,2\}$ are $\emptyset,\ \{1\},\ \{2\}$ so $a_2=3.$

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.

Therefore,

n(S_5)=13.

They match.