Mathematical Induction

Prove infinite statements using the domino effect

Welcome to Mathematical Induction!

Mathematical induction is a powerful proof technique for statements about natural numbers. Think of it like a line of dominoes: if you can knock down the first one (base case) and prove that each domino knocks down the next (inductive step), then ALL dominoes will fall. This lets us prove infinitely many statements with just two steps!

What You'll Learn

1

The Domino Analogy

Visualize how induction works through an animated domino chain

2

Classic Formulas

See geometric proofs of sum formulas like 1+2+...+n = n(n+1)/2

3

Proof Structure

Build complete induction proofs step by step with guided examples

4

Common Patterns

Recognize when and how to apply induction to different problems

The Domino Effect

Mathematical induction works like falling dominoes: prove the first case falls (base case), then prove each domino knocks over the next (inductive step).

10

The Induction Analogy

Base case: The first domino falls (we prove P(1) is true).
Inductive step: Each domino knocks over the next (we prove P(k) → P(k+1)).
Conclusion: All dominoes fall (P(n) is true for all n ≥ 1).

The Principle of Mathematical Induction

To prove that a statement P(n) is true for all natural numbers n ≥ 1:

  1. Base Case: Prove that P(1) is true.
  2. Inductive Step: Prove that for any k ≥ 1, if P(k) is true, then P(k+1) is also true.

Then P(n) is true for all n ≥ 1.

Why Base Case?

The base case gives us a starting point. Without it, we have no "first domino" to fall. The chain reaction needs somewhere to begin!

Why Inductive Step?

The inductive step creates the chain reaction. By proving P(k) → P(k+1), we ensure each "domino" knocks over the next.

Sum Formula: 1 + 2 + ... + n

Visualize why the sum of the first n positive integers equals n(n+1)/2. This classic formula can be proven by induction!

n = 5

Proving by Induction

Base case (n=1): 1 = 1(2)/2 = 1 ✓
Inductive step: If 1+2+...+k = k(k+1)/2, then
1+2+...+k+(k+1) = k(k+1)/2 + (k+1) = (k+1)(k+2)/2 ✓

Induction Proof Builder

Walk through complete induction proofs step by step. Understand each part before moving on.

Statement to Prove

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

Left side
1
Right side
1(1+1)/2 = 1

When n=1, both sides equal 1.

Common Mistakes to Avoid

✗

Forgetting the Base Case

Without a base case, you can "prove" false statements! For example, the statement "n = n+1 for all n" satisfies the inductive step vacuously, but fails the base case.

✗

Not Using the Hypothesis

The inductive step must actually USE the assumption that P(k) is true. If your proof of P(k+1) doesn't reference P(k), something is wrong.

✗

Circular Reasoning

Don't assume P(k+1) while trying to prove it. You can only assume P(k) (the inductive hypothesis) and must derive P(k+1) from it.

Key Takeaways

  • 1.Mathematical induction proves statements for ALL natural numbers using just two steps: a base case and an inductive step.
  • 2.The base case establishes the starting point; the inductive step creates the "domino effect" that reaches every number.
  • 3.The inductive hypothesis (assuming P(k)) is your main tool in proving P(k+1). Always look for ways to use it!
  • 4.Induction is perfect for sum formulas, inequalities, divisibility properties, and any statement about "all n ≥ some starting value."