Lesson 5 — Intermediate

Mathematical Induction

Induction proof karne ka sabse classical tool hai — "har natural number ke liye ye statement sahi hai" sabit karne ke liye. Is lesson mein seekhenge principle kya hai aur do classic proofs khud karenge: summation formula aur divisibility.

Induction kya hai

Domino effect socho — agar pehla domino girta hai aur har domino apne aage wale ko girata hai, toh poori line gir jaayegi. Induction bilkul yahi karta hai: base case = pehla domino, inductive step = har domino aage wala gira de.

Induction ka principle (3 steps)

Principle of Mathematical Induction:
Statement P(n) ko prove karna hai (n = 1, 2, 3, ...)

Step 1 — BASE CASE   : P(1) sahi hai, ye PROVE karo
Step 2 — HYPOTHESIS  : maan lo P(k) sahi hai (k koi bhi)
Step 3 — INDUCTION   : P(k) use karke P(k + 1) sahi
                       hai ye PROVE karo

Conclusion: P(n) har natural number n par sahi ✓

Worked proof — pehli n natural numbers ka yog

Ab ek classic proof — ye GATE mein aur B.Sc exams mein bar bar aata hai. Formula: 1 + 2 + ... + n = n(n+1)/2

Prove: 1 + 2 + ... + n = n(n + 1)/2   for all n ≥ 1

Base case (n = 1):
  LHS = 1
  RHS = 1 × (1 + 1) / 2 = 1  → LHS = RHS ✓

Hypothesis: maan lo
  1 + 2 + ... + k = k(k + 1)/2

Inductive step (prove for k + 1):
  1 + 2 + ... + k + (k + 1)
  = k(k + 1)/2 + (k + 1)        [hypothesis use ki]
  = (k + 1) [ k/2 + 1 ]
  = (k + 1)(k + 2) / 2
  = (k + 1)[(k + 1) + 1] / 2    → wahi formula ✓

⇒ P(k + 1) sahi. Proof complete.

Dhyan se dekho — hypothesis ki value substitute ki, phir algebra se factor kiya. Target formula (k+1) wala tha, usko peeche se yaad rakh kar factor karna sabse smart tarika hai.

Worked proof — divisibility wala pattern

Ek aur GATE-style proof — divisibility. Is pattern mein inductive step mein factor nikalna hota hai:

Prove: 6^n − 1 divisible by 5, for all n ≥ 1

Base case (n = 1):
  6^1 − 1 = 5 → 5 se divide ✓

Hypothesis: 6^k − 1 = 5m  (kuch integer m)

Inductive step (k se k + 1):
  6^(k+1) − 1
  = 6 × 6^k − 1
  = 6(5m + 1) − 1        [hypothesis se 6^k = 5m + 1]
  = 30m + 6 − 1
  = 30m + 5
  = 5(6m + 1)             → 5 se divide ✓

Pattern: base → hypothesis → substitute → 5 common lo

• Summation formulas: 1+2+...+n = n(n+1)/2, pehli n odd = n², squares = n(n+1)(2n+1)/6.
• Divisibility: a^n − b^n type — inductive step mein divisor ko common lo.
• Inequalities: 2^n > n (sab n ≥ 1), n! ≥ 2^n (n ≥ 4).
• Recurrence ka proof: closed forms (jaise Hanoi ka 2^n − 1) induction se verify hote hain.

Exercise

Common mistakes

• Base case chhod dena: Base case ke bina induction adhoora hai — P(1) hi nahi check kiya toh domino line shuru hi nahi hui. P(0) wali statement ho toh 0 se shuru karo.
• Sirf P(k) par ruk jaana: Poora step P(k) se P(k+1) tak jaana hai. Sirf P(k) verify karke chhod diya toh kuch prove nahi hua — hypothesis USE karna padta hai.
• Hypothesis ke bina P(k+1) prove karna: P(k) ko use kiye bina (bina maane) P(k+1) sabit karna — wo tohar (strong) proving hai jo allowed nahi. Hamesha "maan lo P(k) sahi hai" likho.

P(1) : pehla card girta hai          (base case)
P(k) : k cards gir chuke hain         (hypothesis)
Step : (k+1)th card ko bhi gira do   (inductive step)
Result : saare cards — poora tower girega
Proof ka pattern bilkul same, bas cards ki jagah numbers