ISRO CS 2025 Q.60: solution and answer

ISRO 2025 · CSQ.60 · 1 mark · MCQ

How many subsets of {1, 2, 3, 4…12} can be formed such that no two elements in the subset are consecutive?

(A)
144
(B)
377
(C)
610
(D)
89

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

The number of such subsets is $377$ , option (B).

Official answer: BSource: ISRO's final answer key of 15 May 2026

Let $a_{n}$ be the number of subsets of ${1, 2, \dots, n}$ with no two consecutive elements. The empty set counts as a valid subset.
Split on the element $n$ . If $n$ is not chosen, the subset is any valid subset of ${1, \dots, n - 1}$ , giving $a_{n - 1}$ ways.
If $n$ is chosen, then $n - 1$ must be left out. The rest is any valid subset of ${1, \dots, n - 2}$ , giving $a_{n - 2}$ ways.
Every valid subset falls in exactly one of these two cases, so $a_{n} = a_{n - 1} + a_{n - 2}$ for $n \geq 2$ . This is the Fibonacci recurrence.
Base cases: $a_{0} = 1$ (only the empty set) and $a_{1} = 2$ (the empty set and ${1}$ ).
Compute: $a_{2} = 3, a_{3} = 5, a_{4} = 8, a_{5} = 13, a_{6} = 21, a_{7} = 34, a_{8} = 55, a_{9} = 89, a_{10} = 144, a_{11} = 233, a_{12} = 377$ .
Hence $a_{n} = F_{n + 2}$ with $F_{1} = F_{2} = 1$ , and $a_{12} = F_{14} = 377$ . The other options are Fibonacci numbers at the wrong index: $144 = a_{10}$ , $89 = a_{9}$ and $610 = a_{13}$ .

KEY IDEA

Condition on whether the largest element is chosen. This gives $a_{n} = a_{n - 1} + a_{n - 2}$ , so the count of subsets of ${1, \dots, n}$ with no two consecutive elements is the Fibonacci number $F_{n + 2}$ .

WATCH OUT FOR

Starting the recurrence from the wrong base case, or leaving out the empty set. That shifts the answer to a neighbouring Fibonacci number such as $233$ , $610$ , $144$ or $89$ .

From the ISRO CS 2025 paper. Every question of this paper · The full paper (PDF, ISRO) · All 5 ISRO Counting & axioms questions, with notes

ISRO CS 2025 Q.60: solution and answer

Answer and solution

More ISRO Counting & axioms questions