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.
1 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.
2 Example Proofs[편집 | 원본 편집]
2.1 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).
- Assume for some k:
Thus, by mathematical induction, the formula holds for all n.
2.2 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.
- Assume for some k:
Thus, 2ⁿ ≥ n + 1 for all n ≥ 1.
3 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).
4 Applications[편집 | 원본 편집]
- Proving formulas and sequences
- Verifying properties of algorithms
- Establishing correctness in recurrence relations
