Mathematical Induction

Mathematical Induction is a proof technique used in mathematics to establish the validity of a statement for all natural numbers. It is particularly useful for proving properties of sequences, inequalities, and recurrence relations.

Principle of Mathematical Induction

Mathematical induction consists of two main steps:

Base Case: Prove that the statement holds for the smallest natural number (usually n = 1 or n = 0).
Inductive Step: Assume the statement holds for some arbitrary natural number k (inductive hypothesis) and prove it for k + 1.

If both steps are satisfied, the statement holds for all natural numbers.

Example Proofs

Sum of First n Natural Numbers

To prove:

1 + 2 + 3 + ... + n = n(n + 1) / 2

Base Case (n = 1)
- 1 = 1(1 + 1) / 2 = 1 (True).
Inductive Step
- Assume for some k:
  - 1 + 2 + ... + k = k(k + 1) / 2
- Prove for k + 1:
  - (1 + 2 + ... + k) + (k + 1) = k(k + 1) / 2 + (k + 1)
  - = (k + 1)(k / 2 + 1) = (k + 1)(k + 2) / 2 (True).

Thus, by mathematical induction, the formula holds for all n.

Inequality Proof

To prove:

2ⁿ ≥ n + 1 for all n ≥ 1

Base Case (n = 1):
- 2¹ = 2 ≥ 1 + 1 (True).
Inductive Step:
- Assume for some k:
  - 2^k ≥ k + 1
- Prove for k + 1:
  - 2^(k+1) = 2 × 2^k ≥ 2(k + 1) (by induction assumption)
  - Since 2(k + 1) ≥ k + 2 for all k ≥ 1, the statement holds.

Thus, 2ⁿ ≥ n + 1 for all n ≥ 1.

Strong Induction

A variation of mathematical induction where the inductive step assumes the statement holds for multiple previous cases (not just k but all values up to k).

Example: Fibonacci sequence:

F(n) = F(n-1) + F(n-2) for n ≥ 2

Base Case: F(0) = 0, F(1) = 1
Inductive Hypothesis: Assume F(k) and F(k-1) hold.
Inductive Step: Prove F(k+1) = F(k) + F(k-1).

Applications

Proving formulas and sequences
Verifying properties of algorithms
Establishing correctness in recurrence relations