Mathematical Induction & Recursion

🎯 Introduction

Mathematical Induction and Recursive Definitions are fundamental proof techniques in discrete mathematics and computer science. They allow us to prove statements about infinite sets and define functions in elegant, self-referential ways.

🪜 Mathematical Induction

🪜 The Infinite Ladder Analogy

Imagine an infinite ladder:

Step 1: We can reach the first rung of the ladder
Step 2: If we can reach any particular rung, we can reach the next rung

Conclusion: We can reach ALL rungs of the ladder!

🎲 The Domino Effect

Think of propositions as dominoes: P(0), P(1), P(2), ..., P(n), P(n+1), ...

If the first domino falls AND each domino knocks over the next one, then ALL dominoes will fall!

The Principle of Mathematical Induction

To prove that P(n) is true for all positive integers n:

1. BASIS STEP (Base Case)

Show that P(1) is true (or P(0), depending on the problem)

2. INDUCTIVE STEP

Show that P(k) → P(k+1) is true for all positive integers k

Inductive Hypothesis: Assume P(k) is true
Show: P(k+1) is true based on this assumption

Rule of Inference: [P(1) ∧ ∀k (P(k) → P(k+1))] → ∀n P(n)

🔑 Key Points

Induction can start at any integer (not just 1 or 0)
The inductive hypothesis is an ASSUMPTION (not something to prove)
You must use the inductive hypothesis in proving P(k+1)
Both steps (basis and inductive) are required for a complete proof

📝 Worked Examples - Mathematical Induction

Example 1: Sum of First n Positive Integers

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

BASIS STEP (n = 1):
LHS = 1
RHS = 1(1+1)/2 = 2/2 = 1
LHS = RHS ✓ So P(1) is true

INDUCTIVE HYPOTHESIS:
Assume P(k) is true: 1 + 2 + ... + k = k(k+1)/2

INDUCTIVE STEP:
We need to show P(k+1) is true:
1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2

LHS = [1 + 2 + ... + k] + (k+1) = k(k+1)/2 + (k+1) [by inductive hypothesis] = k(k+1)/2 + 2(k+1)/2 = [k(k+1) + 2(k+1)]/2 = (k+1)(k+2)/2 = RHS ✓

CONCLUSION:
By mathematical induction, the formula holds for all positive integers n.

Example 2: Sum of First n Odd Integers

Prove: 1 + 3 + 5 + ... + (2n-1) = n² for all positive integers n

BASIS STEP (n = 1):
LHS = 1
RHS = 1² = 1
LHS = RHS ✓

INDUCTIVE HYPOTHESIS:
Assume: 1 + 3 + 5 + ... + (2k-1) = k²

INDUCTIVE STEP:
Show: 1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)²

LHS = [1 + 3 + 5 + ... + (2k-1)] + (2k+1) = k² + (2k+1) [by inductive hypothesis] = k² + 2k + 1 = (k+1)² = RHS ✓

CONCLUSION:
By mathematical induction, the sum of the first n odd integers is n².

Example 3: Powers of 2

Prove: 1 + 2 + 2² + ... + 2ⁿ = 2^(n+1) - 1 for all non-negative integers n

BASIS STEP (n = 0):
LHS = 1 = 2⁰
RHS = 2^(0+1) - 1 = 2¹ - 1 = 2 - 1 = 1
LHS = RHS ✓

INDUCTIVE HYPOTHESIS:
Assume: 1 + 2 + 2² + ... + 2^k = 2^(k+1) - 1

INDUCTIVE STEP:
Show: 1 + 2 + 2² + ... + 2^k + 2^(k+1) = 2^(k+2) - 1

LHS = [1 + 2 + 2² + ... + 2^k] + 2^(k+1) = [2^(k+1) - 1] + 2^(k+1) [by inductive hypothesis] = 2·2^(k+1) - 1 = 2^(k+2) - 1 = RHS ✓

CONCLUSION:
By mathematical induction, the formula holds for all non-negative integers n.

Example 4: Geometric Progression

Prove: Σ(j=0 to n) ar^j = a + ar + ar² + ... + ar^n = a(r^(n+1) - 1)/(r - 1) when r ≠ 1

BASIS STEP (n = 0):
LHS = ar⁰ = a
RHS = a(r^(0+1) - 1)/(r - 1) = a(r - 1)/(r - 1) = a
LHS = RHS ✓

INDUCTIVE HYPOTHESIS:
Assume: Σ(j=0 to k) ar^j = a(r^(k+1) - 1)/(r - 1)

INDUCTIVE STEP:
Show: Σ(j=0 to k+1) ar^j = a(r^(k+2) - 1)/(r - 1)

LHS = [Σ(j=0 to k) ar^j] + ar^(k+1) = a(r^(k+1) - 1)/(r - 1) + ar^(k+1) [by IH] = [a(r^(k+1) - 1) + ar^(k+1)(r - 1)]/(r - 1) = [ar^(k+1) - a + ar^(k+2) - ar^(k+1)]/(r - 1) = [ar^(k+2) - a]/(r - 1) = a(r^(k+2) - 1)/(r - 1) = RHS ✓

🔄 Recursive Definitions

What is a Recursive Definition?

A recursive (or inductive) definition defines a function or sequence in terms of itself for smaller values.

Two Essential Parts:

Initialization (Base Case): Specify the value at zero or the starting point
Recursion: Give a rule for finding the value at n from values at smaller integers

🔗 The Connection with Induction

Recursive definitions and inductive proofs are complementary:

Recursive Definition	Mathematical Induction
Initialization	Basis Step
Recursion	Inductive Step

Both use the domino analogy: define/prove the first case, then show how each case follows from the previous one.

🔢 Worked Examples - Recursive Definitions

Example 1: Linear Recursion

Given: f(0) = 3, f(n+1) = 2f(n) + 3 for n ≥ 0

Find: f(1), f(2), f(3), f(4)

f(1) = 2f(0) + 3 = 2(3) + 3 = 9 f(2) = 2f(1) + 3 = 2(9) + 3 = 21 f(3) = 2f(2) + 3 = 2(21) + 3 = 45 f(4) = 2f(3) + 3 = 2(45) + 3 = 93

Example 2: Factorial Function

Definition: f(0) = 1, f(n) = n · f(n-1) for n ≥ 1

Find: f(5)

f(1) = 1 · f(0) = 1 · 1 = 1 f(2) = 2 · f(1) = 2 · 1 = 2 f(3) = 3 · f(2) = 3 · 2 = 6 f(4) = 4 · f(3) = 4 · 6 = 24 f(5) = 5 · f(4) = 5 · 24 = 120 Or in one step: f(5) = 5 · f(4) = 5 · 4 · f(3) = 5 · 4 · 3 · f(2) = 5 · 4 · 3 · 2 · f(1) = 5 · 4 · 3 · 2 · 1 · f(0) = 5 · 4 · 3 · 2 · 1 · 1 = 120

Note: This is the definition of n! (n factorial)

Example 3: Fibonacci Sequence

Definition: f₀ = 0, f₁ = 1, fₙ = fₙ₋₁ + fₙ₋₂ for n ≥ 2

Find: f₂, f₃, f₄

f₂ = f₁ + f₀ = 1 + 0 = 1 f₃ = f₂ + f₁ = 1 + 1 = 2 f₄ = f₃ + f₂ = 2 + 1 = 3

Sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Example 4: Powers of 2

Given: f(0) = 3, f(n+1) = 2f(n) for n ≥ 0

Find: f(1) through f(5)

n=0: f(1) = 2f(0) = 2(3) = 6 n=1: f(2) = 2f(1) = 2(6) = 12 n=2: f(3) = 2f(2) = 2(12) = 24 n=3: f(4) = 2f(3) = 2(24) = 48 n=4: f(5) = 2f(4) = 2(48) = 96

Pattern: f(n) = 3 · 2ⁿ

Example 5: Quadratic Recursion

Given: f(0) = 3, f(n+1) = f²(n) - 2f(n) - 2 for n ≥ 0

Find: f(1), f(2)

n=0: f(1) = f²(0) - 2f(0) - 2 = 3² - 2(3) - 2 = 9 - 6 - 2 = 1 n=1: f(2) = f²(1) - 2f(1) - 2 = 1² - 2(1) - 2 = 1 - 2 - 2 = -3

⚖️ Mathematical Induction vs Recursion

Aspect	Mathematical Induction	Recursive Definition
Purpose	Prove a statement is true	Define a function or sequence
Base/Basis	Prove P(1) or P(0) is true	Specify f(0) or f(1)
Recursive/Inductive Part	Prove P(k) → P(k+1)	Define f(n) in terms of f(n-1)
Result	Proves statement for all n	Defines value for all n
Example	Prove 1+2+...+n = n(n+1)/2	Define n! = n·(n-1)!

⚠️ Common Mistakes to Avoid

In Mathematical Induction:

❌ Forgetting the basis step
❌ Not using the inductive hypothesis in the inductive step
❌ Trying to prove the inductive hypothesis (it's an assumption!)
❌ Proving P(k+1) without assuming P(k)
❌ Starting at the wrong base case

In Recursive Definitions:

❌ Missing the base case
❌ Recursion that never reaches the base case
❌ Arithmetic errors in calculations
❌ Not substituting correctly in nested recursions
❌ Circular definitions (defining f(n) in terms of f(n))

💡 Tips and Strategies

For Mathematical Induction:

Always clearly state what P(n) is at the beginning
Label your basis step and inductive step clearly
Write out the inductive hypothesis explicitly
Show every algebraic step in the inductive step
Make it clear where you use the inductive hypothesis
End with a conclusion statement

For Recursive Definitions:

Always verify you have a base case
Check that recursion decreases toward the base case
Calculate a few values to check your understanding
Look for patterns in the sequence of values
Draw a recursion tree for complex recursions
Consider whether a closed-form formula exists

📋 Practice Problems

Induction Problems:

Prove: 1² + 2² + 3² + ... + n² = n(n+1)(2n+1)/6
Prove: 1³ + 2³ + 3³ + ... + n³ = [n(n+1)/2]²
Prove: 2ⁿ > n for all n ≥ 1
Prove: n! > 2ⁿ for all n ≥ 4
Prove: The sum of the first n even integers is n(n+1)

Recursion Problems:

Given f(0) = 1, f(n) = 3f(n-1) + 2, find f(4)
Given f(0) = 2, f(1) = 3, f(n) = f(n-1) + f(n-2), find f(5)
Define the sequence aₙ = 2aₙ₋₁ - 1 with a₁ = 3. Find a₅
Write a recursive definition for the sum 1 + 4 + 9 + ... + n²
Write a recursive definition for 2ⁿ

📖 Quick Reference

Mathematical Induction Template:

Let P(n) be: [state the proposition] BASIS STEP: P(1) (or P(0)) [Show P(1) is true] INDUCTIVE HYPOTHESIS: Assume P(k) is true for some arbitrary k ≥ 1 INDUCTIVE STEP: Show P(k+1) is true [Use P(k) to prove P(k+1)] CONCLUSION: By mathematical induction, P(n) is true for all n ≥ 1

Recursive Definition Template:

BASE CASE: f(0) = [value] (or f(1) = [value]) RECURSIVE CASE: f(n) = [expression involving f(n-1) or f(n-2), etc.] for n ≥ 1 (or n ≥ 2)

🎓 Summary

Mathematical Induction is a powerful proof technique that works like climbing an infinite ladder or toppling an infinite line of dominoes. By proving the base case and the inductive step, we establish truth for all natural numbers.

Recursive Definitions provide an elegant way to define sequences and functions by expressing each term in relation to previous terms. They mirror the structure of inductive proofs.

Both techniques are fundamental to computer science, algorithm analysis, and discrete mathematics. Master them, and you'll have powerful tools for solving a wide range of problems!