Lesson 10 — Intermediate

Recurrence Relations

Recurrence mein kisi term ko pichhli terms se likhte hain — jaise Fibonacci aur Tower of Hanoi. Is lesson mein seekhenge common patterns kaise pehchante hain, iteration method se closed form kaise nikalte hain, aur characteristic equation se linear recurrence kaise solve karte hain. Ye GATE ka fixed topic hai.

Recurrence relation kya hai

Recurrence solve ka matlab hai closed form nikalna — a_n ka direct formula jo bina pichhli terms ke chal sake. Ye recursion ko formula mein badalna hai, jise induction se verify bhi kar sakte hain.

Common patterns (pehchano, GATE shortcut)

Common patterns (pehchano, answer turant):

T(n) = T(n − 1) + c    → linear   → T(n) = cn + T(0)
T(n) = aT(n − 1)       → geometric → a^n
T(n) = 2T(n − 1) + 1, T(1) = 1 → Hanoi → 2^n − 1
T(n) = T(n/2) + c      → divide   → O(log n)
T(n) = 2T(n/2) + 1, T(1) = 1 → 2n − 1 → O(n)
T(n) = 2T(n/2) + n     → merge sort → O(n log n)

Multiply wala recurrence = geometric series (a^n)
Add wala recurrence     = arithmetic (cn)
Divide wala (n/2)       = log n

Iteration method — Tower of Hanoi solve

Sabse simple method — iteration (baar baar substitute karo). Isse Tower of Hanoi ka closed form nikalte hain:

T(n) = 2T(n − 1) + 1,   T(1) = 1

T(n) = 2T(n − 1) + 1
T(n) = 2[2T(n − 2) + 1] + 1 = 2²T(n − 2) + 2 + 1
T(n) = 2³T(n − 3) + 4 + 2 + 1
  ...
T(n) = 2^(n−1) T(1) + (1 + 2 + ... + 2^(n−2))
     = 2^(n−1) · 1 + (2^(n−1) − 1)   [geometric sum]
     = 2^n − 1

Check: T(1) = 1 ✓,  T(2) = 3 ✓,  T(3) = 7 ✓
3 disks = 7 moves,  64 disks = 2^64 − 1 moves

Geometric sum 1 + 2 + 4 + ... + 2^(n−2) = 2^(n−1) − 1 — ye power ka off-by-one sabse common galti hai. Har step mein ek baar count karke dekh lo.

Characteristic equation method

Linear homogeneous recurrence with constant coefficients ka standard method — characteristic equation banao, roots nikalo:

a_n = 3a_(n−1) − 2a_(n−2),   a_0 = 0, a_1 = 1

Step 1: assume a_n = r^n
        r^n = 3r^(n−1) − 2r^(n−2)
Step 2: divide r^(n−2)  →  r² = 3r − 2
Step 3: r² − 3r + 2 = 0  →  (r − 1)(r − 2) = 0
        roots r = 1, 2
Step 4: general solution a_n = A(1)^n + B(2)^n = A + B·2^n
Step 5: initial conditions se A, B nikalo
        a_0 = A + B = 0   ⇒ A = −B
        a_1 = A + 2B = 1  ⇒ B = 1, A = −1
        ⇒ a_n = 2^n − 1

Verify: a_2 = 3a_1 − 2a_0 = 3 = 2² − 1 ✓

Exercise

Common mistakes

• Initial conditions bhool jaana: A aur B constants hain — bina a_0, a_1 ke fix nahi hote. Recurrence akela solution nahi deta, uske saath initial conditions bhi chahiye.
• Geometric sum mein power off-by-one: 1 + 2 + 4 + ... + 2^k = 2^(k+1) − 1. Last term 2^(n−2) ho toh sum 2^(n−1) − 1 — count karke verify karo, yahin sabse zyada galti hoti hai.
• Homogeneous ka matlab bhool jaana: Homogeneous = right side par koi extra term nahi (a_n = 3a_(n−1)). Non-homogeneous (extra n ya constant ho) mein particular solution bhi chahiye — method alag hai.

T(n) = T(n − 1) + T(n − 2)   (1-step + 2-step wale raste)
T(1) = 1,   T(2) = 2
T(3) = 3,   T(4) = 5,   T(5) = 8
Har floor pichhle do ka sum — Fibonacci (1,1,2,3,5,8...)