Mathematical induction is a proof method used to show that a statement is true for every integer in an infinite list, usually all positive integers. It is especially useful for formulas involving sums, divisibility, sequences, and inequalities. The idea is like a line of dominoes: if the first domino falls and each domino knocks down the next one, then every domino will fall.
In math, this lets us prove infinitely many cases using only two carefully written steps.
An induction proof begins with a base case, which verifies the first value such as n = 1. Then the inductive step assumes the statement is true for a general value n = k and uses that assumption to prove it is true for n = k + 1. The assumption for n = k is called the inductive hypothesis, and it must be used logically rather than just repeated.
For example, induction can prove 1 + 2 + 3 + ... + n = n(n + 1)/2 for every positive integer n.
Key Facts
- Induction proves a statement P(n) for all integers n greater than or equal to a starting value.
- Base case: prove P(1), or prove P(a) if the statement starts at n = a.
- Inductive hypothesis: assume P(k) is true for an arbitrary integer k greater than or equal to the start.
- Inductive step: use P(k) to prove P(k + 1).
- Sum formula example: 1 + 2 + 3 + ... + n = n(n + 1)/2.
- If P(a) is true and P(k) implies P(k + 1) for every k >= a, then P(n) is true for all n >= a.
Vocabulary
- Mathematical induction
- A proof technique that establishes a statement for infinitely many integers by proving a starting case and a next-case rule.
- Base case
- The first value of n that is checked directly in an induction proof.
- Inductive hypothesis
- The temporary assumption that the statement is true for n = k during the inductive step.
- Inductive step
- The part of the proof that shows the truth of P(k) forces the truth of P(k + 1).
- Predicate
- A statement P(n) that depends on the variable n and can be true or false for each value of n.
Common Mistakes to Avoid
- Skipping the base case is wrong because the domino chain has no guaranteed starting point.
- Assuming P(k + 1) instead of proving it is wrong because it uses the conclusion as if it were already known.
- Checking several small values and calling it a proof is wrong because examples do not prove every possible integer case.
- Not using the inductive hypothesis is wrong because the inductive step must connect P(k) to P(k + 1), not prove an unrelated statement.
Practice Questions
- 1 Use induction to prove that 1 + 2 + 3 + ... + n = n(n + 1)/2 for all integers n >= 1.
- 2 Use induction to prove that 2 + 4 + 6 + ... + 2n = n(n + 1) for all integers n >= 1.
- 3 Explain why proving P(1), P(2), and P(3) is not enough to prove P(n) for all positive integers n, and describe what the inductive step adds.