Animated Solution for Mathematics - Permutations and Combinations: For $n\ge 2$, let $S_n$ denote the set of all subsets of $\{1,2,\dots ,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 ________

Imagine you are standing before a row of five numbered seats, labeled $1$ through $5$. You are tasked with selecting a group of people to sit in these seats, but there is a peculiar, strict rule: no two people can sit in adjacent seats.

This is a fundamental problem in combinatorics that tests your ability to organize chaos into a logical structure. When we face a problem like this in the JEE Advanced, the secret is to break the problem down into manageable, bite-sized pieces.

The Foundation of Cases

To find the total number of valid subsets, $n(S_5)$, we must categorize our possibilities by the size of the subset, which we denote as $k$. We start with the simplest case: $k=0$.

The empty set, $\varnothing$, contains no elements. Since there are no elements to be consecutive, it does not violate our rule. Thus, we have exactly $1$ valid subset here.

Next, we look at $k=1$. If we pick only one person, they can sit anywhere without fear of being adjacent to someone else. The possible subsets are $\{1\},\{2\},\{3\},\{4\},\{5\}$, giving us $5$ valid subsets.

The Logic of Pairs

For $k=2$, we need to pick two numbers such that their difference is at least $2$. We list the valid pairs methodically:

- Starting with $1$: We can pair it with $3,4,$ or $5$. This yields $3$ pairs: $\{1,3\},\{1,4\},\{1,5\}$.

- Starting with $2$: We cannot pick $1$ or $3$. We pair it with $4$ or $5$, yielding $2$ pairs: $\{2,4\},\{2,5\}$.

- Starting with $3$: We cannot pick $2$ or $4$. We can only pair it with $5$, yielding $1$ pair: $\{3,5\}$.

Summing these up, we find $3+2+1=6$ valid subsets of size two.

The Limit of Possibility

Finally, we consider $k=3$. We need three numbers with no two being consecutive.

If we pick $1$, we must skip $2$, pick $3$, skip $4$, and pick $5$. This gives us the set $\{1,3,5\}$.

Any other combination inevitably results in a consecutive pair or exceeds the available seats. Thus, there is only $1$ valid subset of size three. For $k\ge 4$, it is physically impossible to fit four non-consecutive numbers into five seats.

Summing our results, we have $1$ (empty) $+5$ (singletons) $+6$ (pairs) $+1$ (triplet) $=13$.

There is a deeper, more elegant truth here: the number of such subsets follows the Fibonacci sequence. If $a_n$ is the number of valid subsets for a set of size $n$, the recurrence relation is:

For $n=1$, we have $2$ subsets; for $n=2$, we have $3$; for $n=3$, we have $5$; for $n=4$, we have $8$; and for $n=5$, we have $13$.

The total number of valid subsets is 13. This mathematical pattern turns a tedious counting exercise into a predictable, beautiful rhythm.