Courses / Mathematics XI (HSSC-I) – FBISE Complete SLO-Based Course

7.1 The Principle of Mathematical Induction

Unit 7 – Mathematical Induction and Binomial Theorem · 60 min read · 18 MCQs to check yourself

Mathematical induction practice problems (The Organic Chemistry Tutor)

1. The domino idea

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

Step What you show
1. Base case P(n₀) is true (usually n₀ = 1)
2. Induction hypothesis assume P(k) is true for some k ≥ n₀
3. Induction step using the assumption, prove P(k + 1) is true
4. Conclusion by the principle of mathematical induction, P(n) is true for all n ≥ n₀
Like a line of dominoes: the first falls (base case), and each falling domino knocks over the next (induction step), so all fall.

2. Proving a summation formula

Prove 1 + 3 + 5 + … + (2n - 1) = n².

3. Proving divisibility

Prove 5ⁿ - 1 is divisible by 4 for all n ∈ N.

4. Proving an inequality

Prove 2ⁿ > n for all n ≥ 1. Base: 2 > 1 ✓. Assume 2^k > k. Then 2^(k+1) = 2 · 2^k > 2k = k + k ≥ k + 1 ✓. Statements that start later: n! > 2ⁿ is true only for n ≥ 4 (24 > 16), so the base case is n = 4.

5. Why both steps are needed

Short and long questions

1. Prove by mathematical induction that 1 + 2 + 3 + … + n = (n(n + 1))/2 for all n ∈ N.

Model answer

Base case n = 1: LHS = 1, RHS = (1(2))/2 = 1 ✓ Hypothesis: assume 1 + 2 + … + k = (k(k + 1))/2. Step: 1 + 2 + … + k + (k + 1) = (k(k + 1))/2 + (k + 1) = ((k + 1)(k + 2))/2, which is the formula for n = k + 1 ✓ Conclusion: by the principle of mathematical induction the formula is true for all n ∈ N.

2. Prove by induction that n³ - n is divisible by 6 for all n ∈ N.

Model answer

Base n = 1: 1 - 1 = 0 = 6(0) ✓ Hypothesis: k³ - k = 6m. Step: (k + 1)³ - (k + 1) = k³ + 3k² + 3k + 1 - k - 1 = (k³ - k) + 3k(k + 1) = 6m + 3k(k + 1). k(k + 1) is a product of consecutive integers, so it is even; 3k(k + 1) is divisible by 6. Hence (k + 1)³ - (k + 1) is divisible by 6 ✓ Conclusion: true for all n ∈ N.

3. Prove by induction that 1² + 2² + … + n² = (n(n + 1)(2n + 1))/6.

Model answer

Base n = 1: 1 = (1 · 2 · 3)/6 ✓ Hypothesis: 1² + … + k² = (k(k + 1)(2k + 1))/6. Step: add (k + 1)²: (k(k + 1)(2k + 1) + 6(k + 1)²)/6 = ((k + 1)[2k² + k + 6k + 6])/6 = ((k + 1)(k + 2)(2k + 3))/6 – the formula for n = k + 1 ✓ Conclusion: true for all n ∈ N.

4. Prove by mathematical induction: (a) 1 · 2 + 2 · 3 + … + n(n + 1) = (n(n + 1)(n + 2))/3; (b) 4ⁿ - 1 is divisible by 3.

Model answer

(a) Base n = 1: 2 = (1 · 2 · 3)/3 ✓. Assume true for k. Add (k + 1)(k + 2): (k(k + 1)(k + 2))/3 + (k + 1)(k + 2) = ((k + 1)(k + 2)(k + 3))/3 ✓ – true for k + 1, hence for all n. (b) Base n = 1: 4 - 1 = 3 ✓. Assume 4^k - 1 = 3m. Then 4^(k+1) - 1 = 4 · 4^k - 1 = 4(3m + 1) - 1 = 12m + 3 = 3(4m + 1) ✓. By induction both statements hold for all n ∈ N.

This lesson ends with a quiz of 18 MCQs. Open the lesson on PrepOasis to take it and save your progress.

Previous: Unit 6 Review, Checklist and Unit Test · Next: 7.2 The Binomial Theorem: Expansion, Pascal's Triangle and the General Term

All lessons in Mathematics XI (HSSC-I) – FBISE Complete SLO-Based Course