Mathematical Induction

Mathematical induction is a proof method by which we show that a statement holds for every natural number. It is particularly useful in proving formulas for sums, sequences, and divisibility statements.

Steps of Induction

• 1. Base case: verify the statement for the first number (usually n=1).
• 2. Inductive hypothesis: assume the statement holds for n.
• 3. Inductive step: prove that if it holds for n, then it holds for n+1.

Simple Example

Prove that the sum of the first n natural numbers is given by the following formula:

1. Base case: for n=1, left side = 1, right side = 1·(1+1)/2 = 1 → true. 2. Assume it holds for n. 3. Inductive step: adding n+1, the formula holds for n+1 as well. Thus, we have proven the statement for all n.

General Schema

The essence of inductive proof is that we don't need to perform the proof separately for every n: it's enough to prove the base case and the inductive step, and it will automatically hold for all subsequent cases.

When to Use?

• Proving sum formulas.
• Divisibility properties (e.g., a number is always divisible by something).
• Verifying the correctness of recursive definitions.
• Theorems in number theory.

Summary

With the method of mathematical induction, we can show that a statement holds for every natural number. It has two main parts: base case and inductive step. This is one of the most important proof techniques in mathematics.

Practice Exercise