Maths Q21 – JEE-MAIN 2025

Home Maths Permutations and CombinationsQuestion #330

For

n \geq 2

, let

S_{n}

denote the set of all subsets of

{1, 2, . . ., 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 _______.

Enter Calculated Numerical Value:

Clue 1 of 3: Combinatorial Recurrence

Consider how the presence or absence of the largest number $n$ affects the valid subsets of ${1, 2, . . ., n}$ with no consecutive numbers.

🧠 Full Solution Path

Step 1: Define the Recurrence Relation✦ Active

Let $a_{n}$ be the number of subsets of ${1, 2, . . ., n}$ with no two consecutive numbers. We can derive a recurrence relation by considering two cases for a subset $S \in S_{n}$ :

Case 1: $n \notin S$ . If $n$ is not in the subset, then $S$ must be a valid subset of ${1, 2, . . ., n - 1}$ . There are $a_{n - 1}$ such subsets.

Case 2: $n \in S$ . If $n$ is in the subset, then $n - 1$ cannot be in the subset (to avoid consecutive numbers). Thus, the remaining elements of $S$ must form a valid subset of ${1, 2, . . ., n - 2}$ . There are $a_{n - 2}$ such subsets.

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

💡 Teacher's Secret Hint

This recurrence relation is characteristic of the Fibonacci sequence.

Step 2: Calculate Base Cases○ Expand

For $n = 1$ , the set is ${1}$ . The valid subsets are $\emptyset$ and ${1}$ . So, $a_{1} = 2$ .

For $n = 2$ , the set is ${1, 2}$ . The valid subsets are $\emptyset$ , ${1}$ , and ${2}$ . The subset ${1, 2}$ is not allowed as it contains consecutive numbers. So, $a_{2} = 3$ .

💡 Teacher's Secret Hint

Remember to include the empty set as a valid subset.

Step 3: Compute

n (S_{5})

○ Expand

Using the recurrence relation $a_{n} = a_{n - 1} + a_{n - 2}$ with the base cases $a_{1} = 2$ and $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

Thus, $n (S_{5}) = 13$ .

✦ STEM Console utilizes AI models to generate step-by-step explanations and math clues. AI can make mistakes.

Maths Question 21 – JEE-MAIN 2025

Clue 1 of 3: Combinatorial Recurrence

🧠 Full Solution Path