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.
Understanding Math: Mathematical Induction
The important part of induction is the logical link between one case and the next. During the inductive step, k is not a particular number such as five or ten. It stands for any whole number in the allowed range.
This is why the argument reaches every later value. A proof that works only after choosing one convenient value of k is not an induction proof. Students should write clearly that k is arbitrary before doing the algebra.
In formula proofs, the inductive hypothesis usually replaces a long expression with a simpler one. For the sum of the first k positive integers, the hypothesis says that the sum equals k times the quantity k plus one, divided by two. To form the next case, add k plus one to that known sum.
The remaining work is algebra. Factor out k plus one, then simplify until the result becomes k plus one times k plus two, divided by two. That final form matters because it is exactly the claimed formula with the next input substituted in.
Many incorrect proofs fail because they assume the result they are trying to establish. It is valid to use the statement for k, because that is the temporary hypothesis. It is not valid to begin by writing the statement for k plus one as if it were already known.
Another common error is to show that both expressions happen to simplify to the same answer without explaining how the hypothesis was used. Each line should have a reason. This makes the proof easier to check and exposes hidden gaps.
Some situations need a stronger version of the method. In strong induction, the proof of a later case may use every earlier case, rather than only the case immediately before it. For example, an amount of postage may be formed from stamps of two different values.
To show that every sufficiently large total can be made, a new total may be created by adding one stamp to a total that is two or three units smaller. Recurrence rules in computing and number patterns often work this way. The starting cases must cover every earlier value that the later step needs.
Induction is useful beyond textbook sums. Computer scientists use it to show that a loop works for every permitted input size. It can justify patterns in geometric designs, rules for compound growth, and claims about factors or remainders.
The method does not discover a pattern by itself. Checking several examples can suggest a claim, but examples cannot prove an unlimited claim.
First state the claim precisely, including where it starts. Then test the early values, keep the hypothesis separate from the conclusion, and check that the algebra or reasoning truly reaches the next value.
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.