Fibonacci Method for Subset Counting Problems

❓ Concept

Set ke subsets banana hai…
lekin ek strict rule —
👉 koi do numbers consecutive nahi hone chahiye!

JEE mein yeh pattern baar-baar repeat hota hai,
aur iska answer hamesha Fibonacci logic se aata hai 🔥

---

🖼️ Concept Image

---

✍️ Short Explanation

Is concept ka core idea bahut simple hai:
👉 har number ke paas sirf 2 choices hoti hain — include ya exclude.
Bas ek restriction add ho jaata hai:
include karte hi next number block ho jaata hai.

---

🔹 Step 1 — Problem Type

Given set:

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

Allowed:

• Any subset

• But NO two consecutive elements

Examples:

• $\{1,3,5\}$ ✔ allowed

• $\{1,2,4\}$ ❌ not allowed (1 & 2 consecutive)

---

🔹 Step 2 — Define a Counting Function

Let:

$$f(n)=\text{number of valid subsets of }\{1,2,\dots ,n\}$$

📌 Ab poora question f(n) nikaalne ka hai.

---

🔹 Step 3 — Key Idea (MOST IMPORTANT 🔥)**

Element n ko dekho.

Iske paas do options hote hain:

✅ Option 1: Exclude n

• Toh koi restriction nahi

• First $n-1$ elements se freely choose kar sakte ho

Number of ways:

$$f(n-1)$$

---

✅ Option 2: Include n

• Agar n include hua → n−1 include nahi ho sakta

• Ab choice bachi:

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

Number of ways:

$$f(n-2)$$

---

🔑 Final Relation

$$\boxed{{\displaystyle f(n)=f(n-1)+f(n-2)}}$$

👉 Exactly Fibonacci recurrence!

---

🔹 Step 4 — Base Cases (EXAM READY 📌)**

Always remember:

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

📌 Yeh base values se hi saara sequence banega.

---

🔹 Step 5 — Build Values Fast

Using:

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

Compute:

$$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$$

👉 Exam mein bas yahi logic use hota hai 👍

---

✅ Moral of the Concept

🧠 Golden Rule

• Subsets with no consecutive elements

• ⇒ Always follow Fibonacci pattern

Isliye:

• JEE Main

• JEE Advanced

👉 Is concept ko JEE wale pyaar karte hain ❤️

---