Sequences and Mathematical Induction

What is Mathematical Induction?

Mathematical induction: Proof technique for statements about natural numbers

Like dominos:

• Knock down first domino (base case)
• Each domino knocks down next (inductive step)
• All dominos fall

Use when: Proving formulas or properties for all n ≥ 1 (or other starting value)

Principle of Mathematical Induction

To prove P(n) is true for all n ≥ n₀:

Step 1: Base Case

• Prove P(n₀) is true

Step 2: Inductive Step

• Assume P(k) is true for some arbitrary k ≥ n₀ (inductive hypothesis)
• Prove P(k+1) is true using this assumption

Conclusion: P(n) is true for all n ≥ n₀

Example 1: Sum Formula

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

Base Case (n = 1):

LHS: 1
RHS: 1(1+1)/2 = 2/2 = 1
LHS = RHS ✓

Inductive Step:

Assume true for n = k:

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

Prove true for n = k+1:

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

Start with left side:

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

Conclusion: Formula true for all n ≥ 1

Example 2: Sum of Odd Numbers

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

Base Case (n = 1):

LHS: 1
RHS: 1² = 1
LHS = RHS ✓

Inductive Step:

Assume for n = k:

1 + 3 + 5 + ... + (2k-1) = k²

Prove for n = k+1:

1 + 3 + 5 + ... + (2k-1) + (2(k+1)-1) = (k+1)²

The next odd number: 2(k+1) - 1 = 2k + 1

Start with LHS:

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

Conclusion: Formula true for all n ≥ 1

Example 3: Powers of 2

Prove: 2ⁿ > n for all n ≥ 1

Base Case (n = 1):

2¹ = 2 > 1 ✓

Inductive Step:

Assume for n = k:

2^k > k

Prove for n = k+1:

2^(k+1) > k+1

Start with LHS:

2^(k+1) = 2 · 2^k
        > 2 · k                      [by inductive hypothesis]
        = k + k
        ≥ k + 1                      [since k ≥ 1]
        = RHS ✓

Conclusion: 2ⁿ > n for all n ≥ 1

Example 4: Divisibility

Prove: n³ - n is divisible by 3 for all n ≥ 1

Base Case (n = 1):

1³ - 1 = 0
0 ÷ 3 = 0 ✓ (divisible)

Inductive Step:

Assume for n = k: k³ - k = 3m for some integer m

Prove for n = k+1: (k+1)³ - (k+1) is divisible by 3

Expand:

(k+1)³ - (k+1) = k³ + 3k² + 3k + 1 - k - 1
                = k³ - k + 3k² + 3k
                = (k³ - k) + 3(k² + k)
                = 3m + 3(k² + k)        [by inductive hypothesis]
                = 3[m + k² + k]         [factor]

This is 3 times an integer, so divisible by 3 ✓

Conclusion: n³ - n divisible by 3 for all n ≥ 1

Example 5: Inequality

Prove: n! > 2ⁿ for all n ≥ 4

Base Case (n = 4):

4! = 24
2⁴ = 16
24 > 16 ✓

Inductive Step:

Assume for n = k ≥ 4: k! > 2^k

Prove for n = k+1: (k+1)! > 2^(k+1)

Start with LHS:

(k+1)! = (k+1) · k!
       > (k+1) · 2^k                 [by inductive hypothesis]
       > 2 · 2^k                     [since k+1 > 2 when k ≥ 4]
       = 2^(k+1)
       = RHS ✓

Conclusion: n! > 2ⁿ for all n ≥ 4

Common Mistakes

Don't assume what you're trying to prove

• Inductive hypothesis assumes P(k), not P(k+1)

Don't skip base case

• Formula might work inductively but fail for initial value

Don't confuse n and k

• k is arbitrary value in inductive step

Show all algebra steps

• Must explicitly use inductive hypothesis

Variations of Induction

Strong induction: Assume P(1), P(2), ..., P(k) all true

Complete induction: Prove P(n) using P(m) for all m < n

Backwards induction: Start from high value, work backwards

Sequences and Induction

Recursively defined sequences often proved by induction

Example: Fibonacci

Define: F₁ = 1, F₂ = 1, Fₙ = Fₙ₋₁ + Fₙ₋₂ for n ≥ 3

Prove: Fₙ < 2ⁿ for all n ≥ 1

Base cases: (need two for recursive formula)

F₁ = 1 < 2¹ = 2 ✓
F₂ = 1 < 2² = 4 ✓

Inductive step: Assume true for all m ≤ k

Prove for k+1:

F_(k+1) = F_k + F_(k-1)
        < 2^k + 2^(k-1)               [by hypothesis]
        = 2^(k-1)(2 + 1)
        = 3 · 2^(k-1)
        < 4 · 2^(k-1)
        = 2² · 2^(k-1)
        = 2^(k+1) ✓

When to Use Induction

Proving formulas for sums, products

Proving inequalities involving n

Proving divisibility properties

Proving properties of recursively defined sequences

Proving statements about sets or graphs (advanced)

Real-World Connection

Computer science: Prove algorithm correctness

Proving loop invariants

Proving recursive functions terminate

Understanding mathematical certainty

Practice