RankRizz
JEE MAIN 2025 · 07 APR S1+4 / −1EASYTRANSCRIBED

JEE Main 2025 Mathematics question — Cartesian products and counting relations

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

SOLUTION

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

Step 1 Establish a recurrence for ana_n.
Consider whether the element nn is present in a subset.

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

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

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

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

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

Using (1)(1):
a3=a2+a1=3+2=5a_3 = a_2 + a_1 = 3 + 2 = 5
a4=a3+a2=5+3=8a_4 = a_3 + a_2 = 5 + 3 = 8
a5=a4+a3=8+5=13a_5 = a_4 + a_3 = 8 + 5 = 13

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

Tagged Cartesian products and counting relations. Machine-assigned, so read it as a strong shortlist rather than a verdict.

TopicCartesian products and counting relations
TypeNumerical answer