Mathematical Induction: Proving Statements for All Natural Numbers

Learn about mathematical induction, a powerful proof technique for establishing the truth of a statement for all natural numbers. This guide explains the principle of mathematical induction, its two key steps (base case, inductive step), and provides examples demonstrating its application in proving mathematical statements.

Mathematical Induction: Proving Statements for All Natural Numbers

The Principle of Mathematical Induction

Mathematical induction is a powerful technique for proving that a statement P(n) is true for all natural numbers n greater than or equal to a starting value n0. It's a method of proof, not an algorithm for solving problems directly. It relies on two key steps: establishing a base case and then showing that if the statement is true for a given value, it's also true for the next value. This allows you to prove the statement's validity for all natural numbers.

The Steps of Mathematical Induction

  1. Base Case: Prove that the statement P(n) is true for n = n0 (the starting value).
  2. Inductive Step: Assume that P(k) is true for some arbitrary value k ≥ n0 (the inductive hypothesis). Then, prove that P(k+1) is also true, based on the assumption that P(k) is true.

If both the base case and the inductive step are proven, then the statement P(n) is true for all n ≥ n0.

Example 1: Proving a Summation Formula

Prove that 1 + 3 + 5 + ... + (2n - 1) = n² for all n ≥ 1.

Solution:

  1. Base Case (n=1): 1 = 1² (True).
  2. Inductive Step: Assume 1 + 3 + 5 + ... + (2k - 1) = k² is true for some k ≥ 1. Then:
1 + 3 + 5 + ... + (2k - 1) + (2k + 1) = k² + 2k + 1 = (k + 1)²

Therefore, if the statement is true for k, it's also true for k+1. By the principle of mathematical induction, the statement is true for all n ≥ 1.

Example 2: Proving Another Summation Formula

Prove that 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6 for all n ≥ 1.

Solution:

  1. Base Case (n=1): 1² = 1(2)(3)/6 = 1 (True).
  2. Inductive Step: Assume 1² + 2² + ... + k² = k(k+1)(2k+1)/6 for some k ≥ 1. Then:
1² + 2² + ... + k² + (k+1)² = k(k+1)(2k+1)/6 + (k+1)² = (k+1)(k+2)(2k+3)/6

Therefore, if the statement is true for k, it's true for k+1. By mathematical induction, the statement is true for all n ≥ 1.

Example 3: Divisibility

Show that 11n+2 + 122n+1 is divisible by 133 for all n ≥ 1.

Solution:

  1. Base Case (n=1): 11³ + 12³ = 1331 + 1728 = 3059 = 133 * 23 (True).
  2. Inductive Step: Assume 11r+2 + 122r+1 = 133s for some integer s. Then show that 11r+3 + 122r+3 is divisible by 133.

(The inductive step calculations should be included here.)

Conclusion

Mathematical induction is a powerful technique for proving statements about natural numbers. It's a formal method of proof that relies on establishing a base case and then showing the inductive step. This allows us to prove a statement's validity for an infinite number of cases.