Mathematical induction — principle, steps, problems

3.3.9 · Maths › Sequences & Series

WHAT is the Principle?

Inductive step ke andar use ki gayi assumption " $P (k)$ true hai" ko inductive hypothesis (IH) kehte hain.

WHY kya yeh sach mein sab kuch prove karta hai? Maano $P$ kahin fail ho gayi. $m$ ko woh smallest number maano jahaan yeh fail hoti hai. Toh $m \neq = n_{0}$ (base case hold karta hai), isliye $m - 1 \geq n_{0}$ aur $P (m - 1)$ sach hai (warna $m - 1$ chhota hota aur fail hota). Lekin inductive step kehta hai $P (m - 1) \Rightarrow P (m)$ — contradiction. Toh $P$ kabhi fail nahi hoti. Yahi wajah hai ki PMI Well-Ordering Principle ke equivalent hai (har nonempty set of naturals mein ek least element hota hai).

HOW to write an induction proof (the ritual)

Dil step 4 hai: tumhe $P (k)$ se $P (k + 1)$ banana hoga, usually dono sides mein "next term" add karke.

Worked Example 1 — Sum of first $n$ naturals

Claim: $P (n) : 1 + 2 + \dots + n = \frac{n ( n + 1 )}{2}$ .

Base case $n = 1$ : LHS $= 1$ , RHS $= \frac{1 \cdot 2}{2} = 1$ . ✓ Yeh step kyun? Ek true starting domino ke bina, chain kuch bhi prove nahi karti.

IH: maano $1 + 2 + \dots + k = \frac{k ( k + 1 )}{2}$ .

Step: Dono sides mein next term $(k + 1)$ add karo: $use IH 1 + 2 + \dots + k + (k + 1) = \frac{k ( k + 1 )}{2} + (k + 1)$ Yeh step kyun? $P (k + 1)$ ka LHS bas $P (k)$ ka LHS plus ek aur term hai — toh exactly woh term add karo. $= (k + 1) (\frac{k}{2} + 1) = (k + 1) \cdot \frac{k + 2}{2} = \frac{( k + 1 ) ( k + 2 )}{2} .$ Yeh precisely $P (k + 1)$ hai (formula mein $n$ ki jagah $k + 1$ daalo). PMI se, saare $n \geq 1$ ke liye sach. ∎

Worked Example 2 — Sum of squares

Claim: $P (n) : 1^{2} + 2^{2} + \dots + n^{2} = \frac{n ( n + 1 ) ( 2 n + 1 )}{6}$ .

Base $n = 1$ : LHS $= 1$ , RHS $= \frac{1 \cdot 2 \cdot 3}{6} = 1$ . ✓

IH: $\sum_{i = 1}^{k} i^{2} = \frac{k ( k + 1 ) ( 2 k + 1 )}{6}$ .

Step: $(k + 1)^{2}$ add karo: $\frac{k ( k + 1 ) ( 2 k + 1 )}{6} + (k + 1)^{2} = (k + 1) [\frac{k ( 2 k + 1 )}{6} + (k + 1)] .$ Yeh step kyun? Common $(k + 1)$ ko pehle factor out karo — yeh target formula ka leading factor hai. $= (k + 1) \cdot \frac{k ( 2 k + 1 ) + 6 ( k + 1 )}{6} = (k + 1) \cdot \frac{2 k ^{2} + 7 k + 6}{6} = (k + 1) \cdot \frac{( k + 2 ) ( 2 k + 3 )}{6} .$ Yeh $\frac{( k + 1 ) ( k + 2 ) ( 2 ( k + 1 ) + 1 )}{6} = P (k + 1)$ ke barabar hai. PMI se, done. ∎

Worked Example 3 — Divisibility

Claim: $P (n) : n^{3} - n$ , saare $n \geq 1$ ke liye $6$ se divisible hai.

Base $n = 1$ : $1 - 1 = 0$ , aur $6 ∣ 0$ . ✓

IH: $6 ∣ k^{3} - k$ , yaani $k^{3} - k = 6 m$ kisi integer $m$ ke liye.

Step: $(k + 1)^{3} - (k + 1)$ compute karo: $(k + 1)^{3} - (k + 1) = k^{3} + 3 k^{2} + 3 k + 1 - k - 1 = (k^{3} - k) + 3 k^{2} + 3 k .$ Yeh step kyun? Hum "purana" chunk $k^{3} - k$ (IH se 6 se divisible) aur ek leftover alag karte hain. $= 6 m + 3 k (k + 1) .$ Ab $k (k + 1)$ do consecutive integers ka product hai, isliye yeh even hai, maano $2 t$ . Toh $3 k (k + 1) = 6 t$ . Isliye total $= 6 m + 6 t = 6 (m + t)$ , 6 se divisible. PMI se, done. ∎

Worked Example 4 — Inequality

Claim: $P (n) : 2^{n} > n$ saare $n \geq 1$ ke liye.

Base $n = 1$ : $2^{1} = 2 > 1$ . ✓

IH: $2^{k} > k$ .

Step: $2^{k + 1} = 2 \cdot 2^{k} > 2 k$ (IH use karke). Yeh step kyun? $2^{k + 1}$ paane ke liye IH ko 2 se multiply karo. Ab kya $2 k \geq k + 1$ hai? Haan $k \geq 1$ ke liye kyunki $2 k - (k + 1) = k - 1 \geq 0$ . Toh $2^{k + 1} > 2 k \geq k + 1$ . ∎

Figure — Mathematical induction — principle, steps, problems

Strong (Complete) Induction — ek stronger tool

Common mistake Classic traps ko steel-man karna

Trap 1 — "Maine $n = 1, 2, 3$ check kar liya, toh yeh sach hai." Kyun sahi lagta hai: daily life mein pattern-spotting kaam karta hai. Fix: finitely many cases verify karna proof nahi hai — tumhe general step $P (k) \Rightarrow P (k + 1)$ chahiye. Counterexample: $n^{2} - n + 41$ , $n = 1..40$ ke liye prime hai lekin $n = 41$ par composite hai.

Trap 2 — Base case bhool jaana. Kyun sahi lagta hai: inductive step "puri proof jaisa lagta hai." Fix: pehle domino ke bina poori chain khaali hai. Jaise tum "prove" kar sakte ho ki saare numbers equal hain agar base check skip karo.

Trap 3 — Jo prove karna hai woh assume kar lena. Kyun sahi lagta hai: IH ( $P (k)$ ) aur goal ( $P (k + 1)$ ) similar lagte hain. Fix: tum $P (k)$ assume karte ho (ek fixed value), tum $P (k + 1)$ derive karte ho — kabhi $P (k + 1)$ khud assume mat karo.

Trap 4 — IH ek aisi value ke liye use karna jo abhi establish nahi hui. Ordinary induction mein tum sirf $P (k)$ use kar sakte ho; agar tumne secretly $P (k + 1)$ use kiya toh tumne circular argument bana diya. Strong induction use karo agar tumhe genuinely pehle ke cases chahiye.

Recall Ek 12-saal ke bachche ko samjhao (Feynman)

Dominoes line up karo. Agar tum pehle wale ko gira sakte ho, aur tumhe yakeen hai ki har domino itna paas hai ki woh agle ko hit kar sake, toh tum jaante ho ki saare girenge — chahe ek million bhi kyun na hon — bina har ek ko girte dekhe. Math induction wahi trick hai: prove karo "step 1 kaam karta hai" aur "agar koi bhi step kaam karta hai, toh next bhi kaam karta hai," aur tumne yeh har number ke liye hamesha ke liye prove kar diya.

Active-Recall Flashcards

Principle of Mathematical Induction ke do parts kya hain?

(1) Base case:

P (n_{0})

true. (2) Inductive step:

P (k) \Rightarrow P (k + 1)

saare

k \geq n_{0}

ke liye.

"Inductive hypothesis" kya hota hai?

Yeh assumption ki

P (k)

true hai, jo

P (k + 1)

prove karne ke liye use hoti hai.

Induction actually

P (n)

ko saare

n

ke liye kyun prove karta hai?

Yeh Well-Ordering Principle ke equivalent hai: ek smallest counterexample inductive step ko contradict kar deta.

Ek sum formula ke inductive step mein pehle kya karte ho?

Next term yaani

(k + 1)

-th term ko IH ki dono sides mein add karo.

Woh famous statement batao jo

n = 1..40

ke liye hold karta hai lekin

41

par fail hota hai.

n^{2} - n + 41

(40 tak prime, 41 par composite) — cases check karna proof nahi hai.

Strong induction, ordinary induction se kaise different hai?

Tum

P (k + 1)

prove karne ke liye

P (n_{0}), \dots, P (k)

saare assume karte ho (sirf

P (k)

nahi).

1 + 2 + \dots + n = ?

\frac{n ( n + 1 )}{2}

1^{2} + 2^{2} + \dots + n^{2} = ?

\frac{n ( n + 1 ) ( 2 n + 1 )}{6}

k (k + 1)

hamesha even kyun hota hai?

Yeh do consecutive integers ka product hai, jinmein se ek zaroor even hoga.

Induction proofs mein do common fatal errors?

Base case bhool jaana, aur

P (k + 1)

derive karne ki jagah assume kar lena.

Connections

Well-Ordering Principle — induction ki logical foundation
Arithmetic & Geometric Series — kai sum formulas induction se prove hote hain
Sum of Squares and Cubes — direct induction targets
Divisibility and Modular Arithmetic — divisibility inductions
Recurrence Relations & Fibonacci — strong induction ka natural ghar
Binomial Theorem — aksar $n$ par induction se prove hota hai