Principle of Mathematical Induction

Mathematical induction is a small but examinable NDA topic — usually 1 question, often asking which statement is true 'for all n' or to identify the correct inductive step. Knowing the method plus a few standard results is enough.

Core ideas

To prove a statement P(n) holds for all natural numbers n ≥ 1:

1. Base step: verify P(1) is true.
2. Inductive step: assume P(k) is true (the induction hypothesis), then prove P(k+1) follows.
   If both hold, P(n) is true for every natural number.

Standard results often proved by induction (memorise the closed forms):

• 1 + 2 + … + n = n(n+1)/2
• 1² + 2² + … + n² = n(n+1)(2n+1)/6
• 1³ + 2³ + … + n³ = [n(n+1)/2]²
• 1 + 3 + 5 + … + (2n−1) = n²

Divisibility results (also proved by induction): n³ − n is divisible by 6; xⁿ − yⁿ is divisible by (x − y); 3^(2n) − 1 is divisible by 8.

Exam Tricks & Tips

• 🎯 The base case is not always n = 1 — some statements start at n = 0 or n = 2; check what the problem claims.
• 🎯 In the inductive step you must USE the assumption P(k); a proof that never uses it is invalid.
• 🎯 For divisibility, write P(k+1)'s expression to expose a P(k) factor plus a clearly divisible remainder.
• 🎯 To DISPROVE 'true for all n', one counterexample is enough — try small n quickly.
• 🎯 For NDA MCQs, verifying n = 1, 2, 3 numerically often reveals the right closed-form option faster than proving.
• ❌ Common mistake: thinking checking a few cases PROVES a statement. Verifying n=1,2,3 supports it but only the inductive step proves it for all n.

Expected exam pattern

Items ask: which formula is correct for the sum/divisibility (test small n), identify the valid inductive step, or the smallest n from which a statement holds. Rarely a full proof — usually recognition.

Quick recap

Induction = base step P(1) + inductive step P(k)⇒P(k+1). Memorise Σn, Σn², Σn³, odd-sum = n², and standard divisibility facts. One counterexample disproves; only the inductive step proves for all n.

Cover, recall, check. 10 cards on induction.

Q1. The two steps of mathematical induction?
A1. Base step: prove P(1). Inductive step: assume P(k), prove P(k+1).

Q2. What is the induction hypothesis?
A2. The assumption that P(k) is true, used to establish P(k+1).

Q3. 1 + 2 + … + n = ?
A3. n(n+1)/2.

Q4. 1² + 2² + … + n² = ?
A4. n(n+1)(2n+1)/6.

Q5. 1³ + 2³ + … + n³ = ?
A5. [n(n+1)/2]².

Q6. 1 + 3 + 5 + … + (2n−1) = ?
A6. n².

Q7. n³ − n is always divisible by?
A7. 6.

Q8. xⁿ − yⁿ is divisible by?
A8. (x − y).

Q9. How do you DISPROVE 'P(n) true for all n'?
A9. Provide a single counterexample.

Q10. Does checking n = 1, 2, 3 prove a statement for all n?
A10. No — it only supports it; the inductive step is required for a proof.

How do you prove a statement true for every natural number without checking infinitely many cases? The Principle of Mathematical Induction (PMI) is the domino trick that does it.

Core idea / what this tests: The rigorous three-step method to prove identities and divisibility results for all n ∈ ℕ.

Deep explanation

Beginner — The idea

Imagine a line of dominoes. If (1) the first falls, and (2) each falling domino knocks over the next, then all fall. PMI formalises this: to prove P(n) for all n ≥ 1,

1. Base step: show P(1) is true.
2. Inductive hypothesis: assume P(k) is true for some k.
3. Inductive step: using that, prove P(k+1) is true.
   Then P(n) holds for every natural number.

Intermediate — Proving a sum formula

Typical target: 1 + 2 + 3 + … + n = n(n+1)/2.

• Base: n = 1 gives LHS = 1, RHS = 1·2/2 = 1. ✓
• Assume true for k: 1+…+k = k(k+1)/2.
• For k+1: add (k+1) to both sides: 1+…+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2, which is the formula with n = k+1. ✓

Advanced — Divisibility proofs

To show, say, that n³ − n is divisible by 6 for all n: verify the base, assume k³ − k = 6m, then expand (k+1)³ − (k+1) and rewrite it as (k³ − k) + 3k(k+1). The first bracket is divisible by 6 by hypothesis, and 3k(k+1) is divisible by 6 because k(k+1) is always even. Hence the whole is divisible by 6.

Worked example

Prove that 3²ⁿ − 1 is divisible by 8 for all n ≥ 1.

• Base n = 1: 3² − 1 = 8, divisible by 8. ✓
• Assume 3²ᵏ − 1 = 8m.
• For n = k+1: 3^(2k+2) − 1 = 9·3²ᵏ − 1 = 9(3²ᵏ − 1) + 8 = 9·8m + 8 = 8(9m + 1), divisible by 8. ✓
  By PMI it holds for all n. ∎

NDA relevance

Induction appears both as a "which step is the inductive step" conceptual MCQ and as a short proof in the written paper's descriptive style. Recognising the structure earns quick marks; the sum/divisibility templates cover most cases.

Exam tricks & shortcuts

• Never skip the base step — a true inductive step with a false base proves nothing.
• In the inductive step, algebraically build P(k+1) from P(k): add the next term, or factor out the assumed multiple.
• Mnemonic: B-A-P — Base, Assume, Prove.

Worked Example

Problem: Using the principle of mathematical induction, prove that for every positive integer n:
1 + 2 + 3 + … + n = n(n + 1)/2.

Solution:
Let P(n) be the statement 1 + 2 + … + n = n(n + 1)/2.

Base step (n = 1): LHS = 1, RHS = 1(1 + 1)/2 = 2/2 = 1. LHS = RHS, so P(1) is true.

Inductive step: Assume P(k) is true for some positive integer k, i.e.
1 + 2 + … + k = k(k + 1)/2. (inductive hypothesis)

We must show P(k + 1) holds, i.e. that the sum up to (k + 1) equals (k + 1)(k + 2)/2.
Add (k + 1) to both sides of the hypothesis:
1 + 2 + … + k + (k + 1) = k(k + 1)/2 + (k + 1).
Factor out (k + 1) on the right:
= (k + 1)[ k/2 + 1 ] = (k + 1)·(k + 2)/2.
This is exactly the formula with n replaced by k + 1, so P(k + 1) is true.

Since P(1) is true and P(k) ⇒ P(k + 1), by the principle of mathematical induction P(n) holds for all positive integers n.

Answer: 1 + 2 + … + n = n(n + 1)/2 is proved for all n ∈ ℕ.