Fibonacci Method for Counting Valid Subsets

 

❓ Question

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,\quad \{1,2,4\}\notin S_6.$$

Then the value of

$$n(S_5)$$

(i.e. the number of elements in $S_5$) is equal to ?

---

🖼️ Question Image

---

✍️ Short Solution

This is a classic JEE combinatorics + recurrence question.

Key idea:
👉 Subsets with no consecutive integers follow the Fibonacci pattern.

We’ll first understand why, then apply it to $n=5$.

---

🔹 Step 1 — Understand the restriction

We are forming subsets of $\{1,2,3,4,5\}$ such that:

• You may include a number

• But if you include $k$, you cannot include $k+1$
  

So every choice blocks the next number.

---

🔹 Step 2 — Define a counting approach

Let:

$$f(n)=\text{number of subsets of }\{1,2,\dots,n\}\text{ with no consecutive numbers}$$

We now look at what happens with the element $n$.

---

🔹 Step 3 — Case-wise reasoning (MOST IMPORTANT 🔥)**

Case 1: $n$ is not included

Then we are free to choose any valid subset from:

$$\{1,2,\dots,n-1\}$$

Number of ways:

$$f(n-1)$$

---

Case 2: $n$ is included

Then $n-1$ cannot be included.

So we choose a valid subset from:

$$\{1,2,\dots,n-2\}$$

Number of ways:

$$f(n-2)$$

---

🔹 Step 4 — Recurrence relation

From both cases:

$$f(n)=f(n-1)+f(n-2)$$

📌 Exactly the Fibonacci recurrence!

---

🔹 Step 5 — Base values

Let’s compute the starting terms carefully:

For $n=1$:

$$S_1=\{\varnothing,\{1\}\} \Rightarrow f(1)=2$$

For $n=2$:

Valid subsets:

$$\varnothing,\{1\},\{2\} \Rightarrow f(2)=3$$

So:

$$f(1)=2,\quad f(2)=3$$

---

🔹 Step 6 — Build up to $n=5$

Using:

$$f(n)=f(n-1)+f(n-2)$$

Compute step by step:

$$f(3)=f(2)+f(1)=3+2=5$$
$$f(4)=f(3)+f(2)=5+3=8$$
$$f(5)=f(4)+f(3)=8+5=13$$

---

🔹 Step 7 — Direct Fibonacci shortcut (for JEE 😎)**

This result is well known:

$$f(n)=F_{n+2}$$

where $F_k$ is the Fibonacci sequence:

$$1,1,2,3,5,8,13,\dots$$

So:

$$n(S_5)=F_7=13$$

---

✅ Final Answer

$$\boxed{13}$$

---