Introduction to Proofs · Mathematical induction
Prove a statement for every integer from a specified starting point. Learn to choose the base case, use the induction hypothesis, and check the step without assuming the conclusion.
Before you start
You should be able to expand products, add terms to a finite sum, and read an implication. Review the preceding lesson on direct proof if needed.
Direct proof and counterexamples
The induction principle
Let P(n) be a statement about an integer n and let b be the first integer in the claim. Prove P(b) directly. Then take an arbitrary integer k ≥ b, assume P(k) for that k, and derive P(k + 1). These two steps imply P(n) for every integer n ≥ b.
Why it works: if a counterexample existed, there would be a smallest one m ≥ b. The base case rules out m = b. Then m − 1 ≥ b satisfies the statement, and the step forces m to satisfy it too. This contradicts the choice of m.
Worked examples
Sum an arithmetic sequence
Claim: the sum of 4j + 1 for j = 1 through n is n(2n + 3) for n ≥ 1. At n = 1, both sides equal 5. Assume the sum through k equals k(2k + 3). The next term is 4(k + 1) + 1 = 4k + 5. Adding gives 2k² + 7k + 5 = (k + 1)(2(k + 1) + 3), the required formula at k + 1.
Prove divisibility
Claim: 4 divides 5ⁿ − 1 for every n ≥ 0. At n = 0 the expression is zero. Assume 5ᵏ − 1 = 4q for an integer q. Then 5ᵏ⁺¹ − 1 = 5(5ᵏ − 1) + 4 = 4(5q + 1), again a multiple of 4.
Common mistakes
- Start at the first claimed integer. A base case at n = 2 cannot establish n = 1.
- Assume P(k) only. Write the target P(k + 1) separately before doing algebra.
- A few matching values can support a guess. The general step is what proves the claim.
Practice
- Show that the first n positive odd integers sum to n² for n ≥ 1.
- Show that n! ≥ 2ⁿ⁻¹ for n ≥ 1. Explain why multiplying preserves the inequality.
Worked solutions
- At n = 1, 1 = 1². Assume the sum through k terms is k². The next odd term is 2k + 1, so the new sum is k² + 2k + 1 = (k + 1)². Induction proves the claim.
- At n = 1, 1! = 2⁰ = 1. Assume k! ≥ 2ᵏ⁻¹. Since k + 1 ≥ 2 is positive, (k + 1)! = (k + 1)k! ≥ (k + 1)2ᵏ⁻¹ ≥ 2ᵏ. This is the target for k + 1.
Assessment · 10 points
- 5 points. Prove that 2 + 4 + … + 2n = n(n + 1) for n ≥ 1.
- 5 points. Prove that 7ⁿ − 1 is divisible by 6 for n ≥ 0.
Answer key and scoring
For each proof, award 1 point for the correct base case, 1 for a hypothesis at arbitrary k, 2 for deriving the next case, and 1 for the conclusion and domain.
- At n = 1, both sides equal 2. Assume the sum through k is k(k + 1). Add 2(k + 1) to get (k + 1)(k + 2). Thus the formula holds for every n ≥ 1.
- At n = 0, 7⁰ − 1 = 0. Assume 7ᵏ − 1 = 6q for an integer q. Then 7ᵏ⁺¹ − 1 = 7(7ᵏ − 1) + 6 = 6(7q + 1). Therefore 6 divides 7ⁿ − 1 for every n ≥ 0.
Free reading
Read sections 3.1–3.2 for the induction principle and proof template. Use Recitation 2 for additional worked problems.
Virtual lab · Compare two formulas
Find the first disagreement between two formulas and explain why matching samples do not prove a claim.
Free tool built into this page. Use it in your browser without an account or download.
Procedure
Use the built-in calculator below. Try n = 1, 2, 3, 4, and 5 in order. Outputs are n² and n² + n(n − 1)(n − 2)(n − 3), respectively. Record the first disagreement. Which factor explains each earlier match? Does agreement at n = 3 imply agreement at n = 4?
Expected results and answer check
At n = 1, 2, and 3, the respective factors n − 1, n − 2, and n − 3 vanish. At n = 4 the outputs are 16 and 40, so agreement at 3 does not imply agreement at 4. At n = 5 the outputs are 25 and 145.
The calculator compares finite samples. A counterexample can disprove the claim, while a general argument is needed to prove a universal identity.