📐 Concept diagram

03-08 - Mathematical Induction

Phase: 3 | Subject: 03-08 Prerequisites: 03-07-sequences-and-series.md (sum formulas, patterns) Next subject: 03-09-binomial-theorem.md

Learning Objectives

By the end of this subject, you will be able to:

1. Understand the principle of mathematical induction
2. Prove summation formulas by induction
3. Prove divisibility statements by induction
4. Prove inequalities by induction
5. Apply strong induction when needed

Core Content

The Principle of Induction

Mathematical induction is used to prove statements true for ALL positive integers.

Analogy: Dominoes. If you knock over the first one, and each one knocks over the next, ALL dominoes fall.

Two steps: 1. Base case: Prove true for n = 1 (or whatever starting value) 2. Inductive step: Assume true for n = k, then prove true for n = k + 1

If both hold, the statement is true for ALL n ≥ 1.

Why it works

• Base case: P(1) is true
• Inductive step: If P(k) is true, then P(k+1) is true
• Chain: P(1) → P(2) → P(3) → ... forever

Proving Summation Formulas

Example: Prove that 1 + 2 + 3 + ... + n = n(n+1)/2

Base case (n = 1): LHS = 1, RHS = 1(2)/2 = 1. ✓

Inductive step: Assume true for n = k: 1 + 2 + ... + k = k(k+1)/2

Prove for n = k + 1: 1 + 2 + ... + k + (k+1) = [k(k+1)/2] + (k+1) = [k(k+1) + 2(k+1)] / 2 = (k+1)(k+2) / 2 = (k+1)((k+1)+1) / 2

This matches the formula with n = k+1. ✓

Therefore, true for all n ≥ 1.

Proving Divisibility

Example: Prove n³ - n is divisible by 6 for all n ≥ 1.

Base case (n = 1): 1 - 1 = 0, divisible by 6. ✓

Inductive step: Assume k³ - k = 6m for some integer m. Prove (k+1)³ - (k+1) is divisible by 6.

(k+1)³ - (k+1) = k³ + 3k² + 3k + 1 - k - 1 = k³ + 3k² + 2k = (k³ - k) + 3k² + 3k = 6m + 3k(k+1)

Now k(k+1) is always even (product of consecutive integers). So 3k(k+1) is divisible by 6. And 6m is divisible by 6. Sum is divisible by 6. ✓

Proving Inequalities

Example: Prove 2ⁿ > n² for all n ≥ 5.

Base case (n = 5): 2⁵ = 32 > 25 = 5². ✓

Inductive step: Assume 2ᵏ > k². Prove 2^(k+1) > (k+1)².

2^(k+1) = 2 · 2ᵏ > 2k² (by hypothesis) Need: 2k² > (k+1)² = k² + 2k + 1 This is true when k² - 2k - 1 > 0 For k ≥ 5: k² - 2k - 1 ≥ 25 - 10 - 1 = 14 > 0. ✓

Strong Induction

Instead of assuming just P(k), assume P(1), P(2), ..., P(k) ALL true, then prove P(k+1).

Use when: The k+1 case depends on multiple earlier cases.

Example: Prove every integer n ≥ 2 can be written as a product of primes.

Proof by strong induction:

Base case (n = 2): 2 is prime, so it's a product of one prime. ✓

Inductive step: Assume the statement holds for ALL integers from 2 to k (inclusive). Prove for k+1.

• If k+1 is prime: done — it's a product of one prime.
• If k+1 is composite: then k+1 = a·b where 2 ≤ a ≤ b < k+1. By the strong induction hypothesis, both a and b can be written as products of primes. Multiplying these gives k+1 as a product of primes. ✓

Therefore, every integer n ≥ 2 is a product of primes.

Key Terms

• 03 08 Mathematical Induction
• Correct: A)
• Correct: B)
• Correct: C)
• **Principle of Induction

Mathematical induction - Proving Divisibility - Proving Inequalities - Proving Summation Formulas - Strong Induction - The Principle of Induction - Why it works**

Worked Examples

Example 1: Proving a Summation Formula

Problem: Prove that $1 + 2 + 3 + ... + n = n(n+1)/2$ for all positive integers $n$.

Solution:

Base case (n = 1): LHS = 1, RHS = 1(2)/2 = 1. ✓

Inductive step: Assume true for n = k: $1 + 2 + ... + k = k(k+1)/2$

Prove for n = k + 1: $$1 + 2 + ... + k + (k+1) = [k(k+1)/2] + (k+1)$$ $$= [k(k+1) + 2(k+1)] / 2$$ $$= (k+1)(k+2) / 2$$ $$= (k+1)((k+1)+1) / 2$$

This matches the formula with n = k+1. ✓

Answer: The formula holds for all $n \geq 1$.

Example 2: Proving a Divisibility Statement

Problem: Prove that $n^3 - n$ is divisible by 6 for all integers $n \geq 1$.

Solution:

Base case (n = 1): $1^3 - 1 = 0$, and 0 is divisible by 6. ✓

Inductive step: Assume $k^3 - k = 6m$ for some integer $m$.

Prove $(k+1)^3 - (k+1)$ is divisible by 6:

$$(k+1)^3 - (k+1) = k^3 + 3k^2 + 3k + 1 - k - 1$$ $$= (k^3 - k) + 3k^2 + 3k$$ $$= 6m + 3k(k+1)$$

Since $k(k+1)$ is always even (consecutive integers), $3k(k+1)$ is divisible by 6. Both terms are divisible by 6, so their sum is divisible by 6. ✓

Answer: $n^3 - n$ is divisible by 6 for all $n \geq 1$.

Example 3: Proving an Inequality

Problem: Prove that $2^n > n^2$ for all integers $n \geq 5$.

Solution:

Base case (n = 5): $2^5 = 32 > 25 = 5^2$. ✓

Inductive step: Assume $2^k > k^2$.

Prove $2^{k+1} > (k+1)^2$:

$$2^{k+1} = 2 \cdot 2^k > 2k^2$$

Need: $2k^2 > (k+1)^2 = k^2 + 2k + 1$

This requires $k^2 - 2k - 1 > 0$, which holds for $k \geq 5$ since: $k^2 - 2k - 1 \geq 25 - 10 - 1 = 14 > 0$. ✓

Answer: $2^n > n^2$ for all $n \geq 5$.

Example 4: Strong Induction — Prime Factorisation

Problem: Prove that every integer $n \geq 2$ can be written as a product of primes.

Solution:

Base case (n = 2): 2 is prime — a product of one prime. ✓

Inductive step (strong): Assume true for ALL integers from 2 to k. Prove for k+1.

• If k+1 is prime: done.
• If k+1 is composite: $k+1 = a \cdot b$ where $2 \leq a \leq b < k+1$. By strong hypothesis, both a and b are products of primes. Multiplying gives k+1 as a product of primes. ✓

Answer: Every integer $n \geq 2$ is a product of primes (Fundamental Theorem of Arithmetic).

Quiz

Q1: What does the concept of Proving Divisibility primarily refer to in this subject?

A) A computational error related to Proving Divisibility B) A historical anecdote about Proving Divisibility C) The definition and application of Proving Divisibility D) A visual representation of Proving Divisibility

Correct: C)

• If you chose A: This is incorrect. Proving Divisibility is defined as: the definition and application of proving divisibility. The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Proving Divisibility is defined as: the definition and application of proving divisibility. The other options describe different aspects that are not the primary focus.
• If you chose C: Proving Divisibility is defined as: the definition and application of proving divisibility. The other options describe different aspects that are not the primary focus. Correct!
• If you chose D: This is incorrect. Proving Divisibility is defined as: the definition and application of proving divisibility. The other options describe different aspects that are not the primary focus.

Q2: Which of the following is the key formula discussed in this subject?

A) 1 + 2 + 3 + ... + n = n(n+1)/2 B) A simplified version of 1 + 2 + 3 + ... + n = n(n+1)/2... C) An unrelated formula from a different topic D) The inverse operation of the formula in question

Correct: A)

• If you chose A: The formula 1 + 2 + 3 + ... + n = n(n+1)/2 is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose B: This is incorrect. The formula 1 + 2 + 3 + ... + n = n(n+1)/2 is central to this subject. The other options are either simplified versions or unrelated.
• If you chose C: This is incorrect. The formula 1 + 2 + 3 + ... + n = n(n+1)/2 is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula 1 + 2 + 3 + ... + n = n(n+1)/2 is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Proving Inequalities?

A) It replaces all other methods in this domain B) It is used to proving inequalities in mathematical analysis C) It is used only in advanced research contexts D) It is primarily a historical notation system

Correct: B)

• If you chose A: This is incorrect. Proving Inequalities serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: Proving Inequalities serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose C: This is incorrect. Proving Inequalities serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: This is incorrect. Proving Inequalities serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Proving Summation Formulas is TRUE?

A) Proving Summation Formulas is not related to this subject B) Proving Summation Formulas is an advanced topic beyond this subject's scope C) Proving Summation Formulas is mentioned only as a historical footnote D) Proving Summation Formulas is a fundamental concept covered in this subject

Correct: D)

• If you chose A: This is incorrect. Proving Summation Formulas is a fundamental concept covered in this subject. This subject covers Proving Summation Formulas as part of its core content.
• If you chose B: This is incorrect. Proving Summation Formulas is a fundamental concept covered in this subject. This subject covers Proving Summation Formulas as part of its core content.
• If you chose C: This is incorrect. Proving Summation Formulas is a fundamental concept covered in this subject. This subject covers Proving Summation Formulas as part of its core content.
• If you chose D: Proving Summation Formulas is a fundamental concept covered in this subject. This subject covers Proving Summation Formulas as part of its core content. Correct!

Q5: Based on the worked examples in this subject, what is the correct result?

A) ** Prove n³ - n is divisible by 6 for all n ≥ 1. B) A different result from a common mistake C) An unrelated numerical value D) The inverse of the correct answer

Correct: A)

• If you chose A: The worked examples show that the result is ** Prove n³ - n is divisible by 6 for all n ≥ 1.. The other options represent common errors. Correct!
• If you chose B: This is incorrect. The worked examples show that the result is ** Prove n³ - n is divisible by 6 for all n ≥ 1.. The other options represent common errors.
• If you chose C: This is incorrect. The worked examples show that the result is ** Prove n³ - n is divisible by 6 for all n ≥ 1.. The other options represent common errors.
• If you chose D: This is incorrect. The worked examples show that the result is ** Prove n³ - n is divisible by 6 for all n ≥ 1.. The other options represent common errors.

Q6: How are Proving Summation Formulas and Strong Induction related?

A) Proving Summation Formulas and Strong Induction are closely related concepts B) Proving Summation Formulas is a special case of Strong Induction C) Proving Summation Formulas is the inverse of Strong Induction D) Proving Summation Formulas and Strong Induction are completely unrelated topics

Correct: A)

• If you chose A: Both Proving Summation Formulas and Strong Induction are covered in this subject as interconnected topics. Correct!
• If you chose B: This is incorrect. Both Proving Summation Formulas and Strong Induction are covered in this subject as interconnected topics.
• If you chose C: This is incorrect. Both Proving Summation Formulas and Strong Induction are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Proving Summation Formulas and Strong Induction are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with The Principle of Induction?

A) The main error with The Principle of Induction is using it when it is not needed B) A common mistake is confusing The Principle of Induction with a similar concept C) The Principle of Induction has no common misconceptions D) The Principle of Induction is always computed the same way in all contexts

Correct: B)

• If you chose A: This is incorrect. Students often confuse The Principle of Induction with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: Students often confuse The Principle of Induction with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose C: This is incorrect. Students often confuse The Principle of Induction with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose D: This is incorrect. Students often confuse The Principle of Induction with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Why it works?

A) Why it works is not practically useful B) Apply Why it works to solve problems in this subject's domain C) Use Why it works only in pure mathematics contexts D) Avoid Why it works unless explicitly instructed

Correct: B)

• If you chose A: This is incorrect. Why it works is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: Why it works is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose C: This is incorrect. Why it works is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: This is incorrect. Why it works is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. Prove by induction: 1 + 3 + 5 + ... + (2n-1) = n² Answer outline: Base: n=1 gives 1 = 1². Step: assume sum to k = k². Add (2k+1): k² + 2k + 1 = (k+1)².

2. Prove by induction: 2 + 4 + 6 + ... + 2n = n(n+1) Answer outline: Base: n=1 gives 2 = 1(2). Step: assume sum to k = k(k+1). Add 2(k+1): k(k+1) + 2(k+1) = (k+1)(k+2).

3. Prove n² + n is even for all n ≥ 1 Answer outline: Base: n=1 gives 2, even. Step: (k+1)² + (k+1) = k² + 2k + 1 + k + 1 = (k² + k) + 2(k+1). Both terms even.

4. Prove 7ⁿ - 1 is divisible by 6 for all n ≥ 1 Answer outline: Base: 7¹-1 = 6, divisible by 6. ✓ Step: assume 7ᵏ-1 = 6m. Then 7^(k+1)-1 = 7·7ᵏ-1 = 7(7ᵏ-1)+7-1 = 7(6m)+6 = 6(7m+1), divisible by 6. ✓

Summary

Key takeaways:

• Induction proves statements for ALL positive integers
• Base case: prove for starting value
• Inductive step: assume P(k), prove P(k+1)
• Like dominoes: first falls, each knocks the next
• Strong induction: assume all P(1)...P(k) to prove P(k+1)
• Works for sums, divisibility, inequalities, and more

Pitfalls

• Skipping the base case: Induction is logically incomplete without verifying the base case. Saying "the inductive step covers all n" without establishing a starting point proves nothing — the entire domino chain has nowhere to start. Always explicitly verify the base case (usually n = 1) before the inductive step.
• Not clearly stating the inductive hypothesis: The proof must say "Assume true for n = k" (or some equivalent phrasing). Without stating what you're assuming, the inductive step lacks logical grounding. Write this explicitly: "Assume P(k) holds, i.e., [specific statement with k]."
• Proving P(k+1) without using P(k): The inductive step MUST use the inductive hypothesis somewhere. If you prove P(k+1) directly without invoking P(k), you haven't done induction — you've done a direct proof. The power of induction comes from chaining P(k) to P(k+1).
• Using the inductive hypothesis incorrectly: In the inductive step, you assume P(k) for a specific, arbitrary k. You then use that assumption to prove P(k+1). Don't accidentally assume P(k+1) in the process, and don't treat the hypothesis as true for all possible n — it's only assumed for k.
• Confusing strong induction with weak induction: Regular (weak) induction assumes only P(k). Strong induction assumes P(1), P(2), ..., P(k) are all true. Use strong induction when P(k+1) depends on multiple earlier cases (e.g., prime factorisation, Fibonacci). Using weak induction for such problems often fails.

Next Steps

Next up: 03-09-binomial-theorem.md