Mathematical Induction Problems

[MathDefinition title="Mathematical Induction"] Mathematical induction is a method of proving that a statement P(n) is true for all natural numbers n. It involves two steps:

1. Base case: Verify that P(1) is true
2. Inductive step: Assume P(k) is true and prove P(k+1) is true [/MathDefinition]

[MathDefinition title="Principle of Mathematical Induction"] If P(1) is true and P(k) ⟹ P(k+1) is true for all natural numbers k, then P(n) is true for all natural numbers n. [/MathDefinition]

[MathKeyFormula title="Steps for Mathematical Induction"] Step 1: Verify P(1) is true Step 2: Assume P(k) is true for some arbitrary natural number k (Inductive Hypothesis) Step 3: Using the inductive hypothesis, prove P(k+1) is true Step 4: Conclude that P(n) is true for all natural numbers n by the principle of mathematical induction [/MathKeyFormula]

[MathNote title="Common Mistakes to Avoid"]

1. Always verify the base case completely
2. Clearly state the inductive hypothesis
3. Use the inductive hypothesis in proving P(k+1)
4. Don't assume what you're trying to prove
5. Show that P(k+1) follows logically from P(k) [/MathNote]

[MathExample title="Example 1: Sum of Natural Numbers"] Problem: Prove that 1 + 2 + 3 + ... + n = n(n+1)/2 for all natural numbers n.

Solution: Let P(n): 1 + 2 + 3 + ... + n = n(n+1)/2

Step 1: Base case (n = 1) LHS = 1 RHS = 1(1+1)/2 = 1(2)/2 = 1 LHS = RHS, so P(1) is true.

Step 2: Inductive hypothesis Assume P(k) is true for some k ∈ N: 1 + 2 + 3 + ... + k = k(k+1)/2

Step 3: Prove P(k+1) We need to prove: 1 + 2 + 3 + ... + k + (k+1) = (k+1)(k+2)/2

LHS = [1 + 2 + 3 + ... + k] + (k+1) = k(k+1)/2 + (k+1) [using inductive hypothesis] = (k+1)[k/2 + 1] = (k+1)(k+2)/2 = RHS

Step 4: Conclusion Since P(1) is true and P(k) ⟹ P(k+1), by mathematical induction, P(n) is true for all n ∈ N. [/MathExample]

[MathExample title="Example 2: Geometric Series"] Problem: Prove that 1 + 3 + 3² + ... + 3ⁿ⁻¹ = (3ⁿ − 1)/2 for all n ∈ N.

Solution: Let P(n): 1 + 3 + 3² + ... + 3ⁿ⁻¹ = (3ⁿ − 1)/2

Step 1: Base case (n = 1) LHS = 3⁰ = 1 RHS = (3¹ − 1)/2 = 2/2 = 1 LHS = RHS, so P(1) is true.

Step 2: Inductive hypothesis Assume P(k) is true: 1 + 3 + 3² + ... + 3ᵏ⁻¹ = (3ᵏ − 1)/2

Step 3: Prove P(k+1) We need to prove: 1 + 3 + 3² + ... + 3ᵏ = (3ᵏ⁺¹ − 1)/2

LHS = [1 + 3 + 3² + ... + 3ᵏ⁻¹] + 3ᵏ = (3ᵏ − 1)/2 + 3ᵏ [using inductive hypothesis] = (3ᵏ − 1 + 2·3ᵏ)/2 = (3·3ᵏ − 1)/2 = (3ᵏ⁺¹ − 1)/2 = RHS

Step 4: Conclusion By mathematical induction, P(n) is true for all n ∈ N. [/MathExample]

[MathExample title="Example 3: Divisibility"] Problem: Prove that 4ⁿ + 15n − 1 is divisible by 9 for all n ∈ N.

Solution: Let P(n): 4ⁿ + 15n − 1 is divisible by 9

Step 1: Base case (n = 1) 4¹ + 15(1) − 1 = 4 + 15 − 1 = 18 18 is divisible by 9, so P(1) is true.

Step 2: Inductive hypothesis Assume P(k) is true: 4ᵏ + 15k − 1 = 9m for some integer m

Step 3: Prove P(k+1) We need to show 4ᵏ⁺¹ + 15(k+1) − 1 is divisible by 9

4ᵏ⁺¹ + 15(k+1) − 1 = 4·4ᵏ + 15k + 15 − 1 = 4·4ᵏ + 15k + 14

From inductive hypothesis: 4ᵏ = 9m − 15k + 1

= 4(9m − 15k + 1) + 15k + 14 = 36m − 60k + 4 + 15k + 14 = 36m − 45k + 18 = 9(4m − 5k + 2)

This is divisible by 9.

Step 4: Conclusion By mathematical induction, 4ⁿ + 15n − 1 is divisible by 9 for all n ∈ N. [/MathExample]

[MathExample title="Example 4: Product Formula"] Problem: Prove that (1 + 1/1)(1 + 1/2)(1 + 1/3)...(1 + 1/n) = n + 1 for all n ∈ N.

Solution: Let P(n): (1 + 1/1)(1 + 1/2)(1 + 1/3)...(1 + 1/n) = n + 1

Step 1: Base case (n = 1) LHS = (1 + 1/1) = 2 RHS = 1 + 1 = 2 LHS = RHS, so P(1) is true.

Step 2: Inductive hypothesis Assume P(k) is true: (1 + 1/1)(1 + 1/2)(1 + 1/3)...(1 + 1/k) = k + 1

Step 3: Prove P(k+1) We need to prove: (1 + 1/1)(1 + 1/2)...(1 + 1/k)(1 + 1/(k+1)) = k + 2

LHS = [(1 + 1/1)(1 + 1/2)...(1 + 1/k)] × (1 + 1/(k+1)) = (k + 1) × (1 + 1/(k+1)) [using inductive hypothesis] = (k + 1) × ((k+1+1)/(k+1)) = (k + 1) × ((k+2)/(k+1)) = k + 2 = RHS

Step 4: Conclusion By mathematical induction, P(n) is true for all n ∈ N. [/MathExample]