Mathematical Induction Explained

• Mathematical induction establishes a given statement for all natural numbers greater than or equal to a base value.
• It is analogous to a line of dominoes, where the fall of one domino causes the next to fall.

Principle of Mathematical Induction

• P(n) represents a statement involving a natural number n.
• To prove P(n) true for all n ≥ a:
  • Base Case: Verify P(a) is true.
  • Inductive Step: Assume P(k) is true for an arbitrary natural number k ≥ a; this is the inductive hypothesis.
  • Prove P(k+1) is true using the assumption that P(k) is true.

Steps for Mathematical Induction

• State the proposition P(n).
• Base Case: Verify P(a) for the smallest integer 'a' in the range.
• Inductive Hypothesis: Assume P(k) is true for some arbitrary integer k ≥ a.
• Inductive Step: Prove P(k+1) is true, using the inductive hypothesis P(k).
• Conclusion: State that P(n) is true for all n ≥ a by mathematical induction.

Example: Sum of First n Natural Numbers

• Proposition P(n): 1 + 2 + 3 + ... + n = n(n+1)/2
• Base Case (n=1): 1 = 1(1+1)/2 = 1, therefore P(1) is true.
• Inductive Hypothesis: Assume 1 + 2 + 3 + ... + k = k(k+1)/2 holds true for some k ≥ 1.
• Inductive Step: Prove that 1 + 2 + 3 + ... + (k+1) = (k+1)(k+2)/2.
  • Start with the left side: 1 + 2 + 3 + ... + k + (k+1).
  • Per the inductive hypothesis: 1 + 2 + 3 + ... + k = k(k+1)/2.
  • Therefore, k(k+1)/2 + (k+1) = [k(k+1) + 2(k+1)] / 2 = (k+1)(k+2) / 2.
  • Which equals the right side of P(k+1), thus P(k+1) is true.
• Conclusion: By mathematical induction, 1 + 2 + 3 + ... + n = n(n+1)/2 for all n ≥ 1.

Example: Divisibility

• Proposition P(n): n³ - n is divisible by 3 for all natural numbers n.
• Base Case (n=1): 1³ - 1 = 0, which is divisible by 3, thus P(1) is true.
• Inductive Hypothesis: Assume k³ - k is divisible by 3 for some k ≥ 1.
• Inductive Step: Prove that (k+1)³ - (k+1) is divisible by 3.
  • (k+1)³ - (k+1) = k³ + 3k² + 3k + 1 - k - 1 = (k³ - k) + 3k² + 3k.
  • By the inductive hypothesis, k³ - k is divisible by 3.
  • Furthermore, 3k² + 3k = 3(k² + k) is divisible by 3.
  • Consequently, (k³ - k) + 3(k² + k) is divisible by 3, which means (k+1)³ - (k+1) is divisible by 3, and P(k+1) is true.
• Conclusion: By mathematical induction, n³ - n is divisible by 3 for all n ≥ 1.

Example: Inequality

• Proposition P(n): 2ⁿ > n for all natural numbers n ≥ 1.
• Base Case (n=1): 2¹ = 2 > 1, therefore P(1) is true.
• Inductive Hypothesis: Assume 2ᵏ > k for some k ≥ 1.
• Inductive Step: Prove that 2^(k+1) > k+1.
  • Start with the left side: 2^(k+1) = 2 * 2ᵏ.
  • By the inductive hypothesis, 2ᵏ > k.
  • Thus, 2 * 2ᵏ > 2 * k = k + k.
  • Given that k ≥ 1, k + k ≥ k + 1.
  • Hence, 2^(k+1) > k + 1, so P(k+1) holds true.
• Conclusion: By mathematical induction, 2ⁿ > n for all n ≥ 1.

Common Mistakes

• Forgetting to prove the base case.
• Making an incorrect inductive hypothesis.
• Not clearly demonstrating the use of the inductive hypothesis in the inductive step.
• Committing algebraic errors during the inductive step.
• Omitting a clear conclusion.

Variants of Mathematical Induction

• Strong Induction: Assume P(a), P(a+1), ..., P(k) are all true, then prove P(k+1).
• Induction with a different starting point: The base case 'a' can be any integer, not just 1.
• Backward Induction: Prove P(n) => P(n-1), but this is less common.

When to Use Mathematical Induction

• When proving formulas for sums, products, or sequences.
• When proving divisibility results.
• When proving inequalities.
• When proving properties of algorithms or recursively defined data structures.

Tips for Success

• Thoroughly understand the principle.
• Practice diverse problem types.
• Write each step clearly and carefully.
• Verify your algebra and logic.
• Persevere and don't give up!