Mathematical induction — A/L Combined Mathematics

What must I remember about Mathematical induction?

• Principle of Mathematical Induction (PMI): A deductive mathematical technique used to prove that a statement P(n) is true for all positive integers n ≥ n0 (typically n0 = 1).
• Basis Step (Base Case): Verify explicitly that the proposition P(1) is true.
• Inductive Hypothesis: Assume that P(k) is true for an arbitrary positive integer k ≥ 1.
• Inductive Step: Using the inductive hypothesis P(k), prove logically that P(k + 1) must also be true.
• Conclusion: By the Principle of Mathematical Induction, since P(1) is true and P(k) => P(k + 1) for all k ≥ 1, P(n) is true for all positive integers n ∈ ℤ+.

Test yourself (1 minute)

1. Divisibility proofs via induction

   To prove f(n) is divisible by d, evaluate f(k+1) - f(k) or f(k+1) - m*f(k) to extract d as an explicit factor using inductive hypothesis f(k) = d*M.

2. Inequality proofs via induction

   When proving f(n) > g(n), start from f(k+1), express it using f(k), substitute f(k) > g(k), and demonstrate that the resulting expression exceeds g(k+1).

3. Non-standard base case

   If proposition holds for n ≥ 4 (e.g., 2ⁿ > n²), the base case MUST be verified at n = 4, not n = 1.

Practise Mathematical induction questions today

Source: NIE G.C.E. (A/L) Combined Mathematics Resource Book - Pure Mathematics, Unit 20

What should I study first?

What comes next?

Next in the syllabus

Where does Mathematical induction fit in the syllabus?

Year 1 · Term 3