Prove statements for all positive integers using base cases and inductive steps. Master summation formulas, divisibility proofs, inequality proofs, and strong induction — with every step written out.
Mathematical induction is a method for proving that a statement P(n) is true for every positive integer n. Think of it like an infinite row of dominoes: if the first domino falls (base case), and every falling domino knocks over the next one (inductive step), then all the dominoes fall.
The Principle of Mathematical Induction states:
Let P(n) be a statement about positive integers. If P(1) is true, and for every positive integer k, the truth of P(k) implies the truth of P(k+1), then P(n) is true for all positive integers n.
The word "implies" is critical. You do not prove P(k) and P(k+1) separately. You prove a conditional: IF P(k) is true, THEN P(k+1) must also be true. Combined with the verified base case, this is enough to guarantee truth for every n.
Prove the statement is true when n = 1 (or whatever the starting value is). Substitute n = 1 into both sides of the equation and verify they are equal. This is usually the easiest step — do not skip it.
Assume the statement is true for n = k. Write out the statement explicitly with k substituted in. This assumption is called P(k) and you are allowed to treat it as given for the rest of the proof.
Using the inductive hypothesis, prove the statement for n = k + 1. Write the k + 1 version of the formula, then manipulate one side until you can use the P(k) assumption. Conclude that the statement holds for k + 1.
State that by the Principle of Mathematical Induction, the statement is true for all positive integers n. Both steps together — base case and inductive step — complete the proof.
Claim: 1 + 2 + 3 + ... + n = n times (n + 1) divided by 2, for all positive integers n.
In shorthand: Sn = n(n+1)/2
Base Case (n = 1):
Left side: 1.
Right side: 1 times (1 + 1) divided by 2 = 1 times 2 divided by 2 = 1.
Both sides equal 1. Base case verified. ✓
Inductive Hypothesis:
Assume 1 + 2 + ... + k = k(k+1)/2 for some positive integer k.
Inductive Step (prove for n = k + 1):
We need to show: 1 + 2 + ... + k + (k+1) = (k+1)(k+2)/2.
1 + 2 + ... + k + (k+1)
= [1 + 2 + ... + k] + (k+1)
= k(k+1)/2 + (k+1) [by the inductive hypothesis]
= (k+1) times [k/2 + 1] [factor out (k+1)]
= (k+1) times [(k + 2)/2]
= (k+1)(k+2)/2 [this is exactly P(k+1)] ✓
Conclusion:
By the Principle of Mathematical Induction, 1 + 2 + ... + n = n(n+1)/2 for all positive integers n.
Claim: 1² + 2² + 3² + ... + n² = n(n+1)(2n+1) divided by 6, for all positive integers n.
Base Case (n = 1):
Left side: 1² = 1.
Right side: 1 times 2 times 3 divided by 6 = 6/6 = 1.
Equal. Base case verified. ✓
Inductive Hypothesis:
Assume 1² + 2² + ... + k² = k(k+1)(2k+1)/6.
Inductive Step:
Goal: prove 1² + 2² + ... + k² + (k+1)² = (k+1)(k+2)(2k+3)/6.
1² + 2² + ... + k² + (k+1)²
= k(k+1)(2k+1)/6 + (k+1)² [by hypothesis]
= (k+1) times [k(2k+1)/6 + (k+1)]
= (k+1) times [k(2k+1)/6 + 6(k+1)/6]
= (k+1) times [(2k² + k + 6k + 6)/6]
= (k+1) times [(2k² + 7k + 6)/6]
= (k+1) times [(k+2)(2k+3)/6]
= (k+1)(k+2)(2k+3)/6 [matches P(k+1)] ✓
Conclusion:
The formula holds for all positive integers n by the Principle of Mathematical Induction.
Key technique: Factor out (k+1) early. This almost always works in sum-of-powers proofs and simplifies the algebra dramatically.
1 + 2 + 3 + ... + n = n times (n + 1) divided by 2
Check: n=4: 1+2+3+4 = 10 = 4 times 5 divided by 2 = 10 ✓
1² + 2² + 3² + ... + n² = n times (n+1) times (2n+1) divided by 6
Check: n=3: 1+4+9 = 14 = 3 times 4 times 7 divided by 6 = 14 ✓
1³ + 2³ + 3³ + ... + n³ = [n times (n+1) divided by 2] squared
Check: n=3: 1+8+27 = 36 = (3 times 4 divided by 2)² = 6² = 36 ✓
1 + r + r² + ... + r^(n−1) = (r^n − 1) divided by (r − 1) when r is not 1
Check: r=2, n=4: 1+2+4+8 = 15 = (16−1)/(2−1) = 15 ✓
Claim: For r not equal to 1, the sum 1 + r + r² + ... + r^(n−1) = (rⁿ − 1) divided by (r − 1), for all positive integers n.
Base Case (n = 1):
Left side: r⁰ = 1.
Right side: (r¹ − 1)/(r − 1) = (r − 1)/(r − 1) = 1.
Equal. ✓
Inductive Hypothesis:
Assume 1 + r + r² + ... + r^(k−1) = (rᵏ − 1)/(r − 1).
Inductive Step:
Goal: prove 1 + r + ... + r^(k−1) + r^k = (r^(k+1) − 1)/(r − 1).
1 + r + ... + r^(k−1) + rᵏ
= (rᵏ − 1)/(r − 1) + rᵏ [hypothesis]
= (rᵏ − 1)/(r − 1) + rᵏ(r − 1)/(r − 1) [common denominator]
= [rᵏ − 1 + rᵏ(r − 1)] / (r − 1)
= [rᵏ − 1 + r^(k+1) − rᵏ] / (r − 1)
= (r^(k+1) − 1) / (r − 1) ✓
Connection to sequences: This formula is the finite geometric series sum you also use in the Sequences & Series chapter. Induction provides the rigorous proof that the formula works for every n.
Divisibility proofs follow the same two-step structure. The trick in the inductive step is to write the expression for k+1 in a way that lets you factor out the divisor. You almost always do this by adding and subtracting a strategically chosen term.
Claim: 3 divides n³ − n for every positive integer n
Base Case:
n=1: 1³ − 1 = 0 = 3 times 0. True.
Inductive Hypothesis:
Assume 3 divides k³ − k, so k³ − k = 3m for some integer m.
Inductive Step:
Show 3 divides (k+1)³ − (k+1). Expand: k³ + 3k² + 3k + 1 − k − 1 = k³ − k + 3k² + 3k = (k³ − k) + 3(k² + k). By the hypothesis, k³ − k = 3m, so the whole expression = 3m + 3(k² + k) = 3(m + k² + k). This is divisible by 3.
Therefore: 3 divides n³ − n for all n ≥ 1 ✓
Claim: 6 divides n³ + 5n for every positive integer n
Base Case:
n=1: 1 + 5 = 6 = 6 times 1. True.
Inductive Hypothesis:
Assume 6 divides k³ + 5k, so k³ + 5k = 6m.
Inductive Step:
Compute (k+1)³ + 5(k+1) = k³ + 3k² + 3k + 1 + 5k + 5 = (k³ + 5k) + 3k² + 3k + 6 = 6m + 3k(k+1) + 6. Since one of k or k+1 is even, k(k+1) is always even, so 3k(k+1) is divisible by 6. Thus the whole thing is divisible by 6.
Therefore: 6 divides n³ + 5n for all n ≥ 1 ✓
Inequality proofs are often the hardest type because you need a chain of inequalities in the inductive step, and each link must be justified. The standard approach: write the left side for n = k+1, apply the inductive hypothesis to replace part of it with something you know is bounded, then use a simple numerical inequality to close the gap.
Claim: 2^n is greater than n for all positive integers n
Base Case:
n=1: 2¹ = 2 > 1. True.
Inductive Hypothesis:
Assume 2^k > k.
Inductive Step:
Need to show 2^(k+1) > k+1. We have 2^(k+1) = 2 times 2^k > 2k (using hypothesis). Since k ≥ 1, we know 2k = k + k ≥ k + 1. So 2^(k+1) > k + 1.
Claim: n! is greater than or equal to 2^(n−1) for all n ≥ 1
Base Case:
n=1: 1! = 1 = 2⁰ = 1. True (equal, which is fine).
Inductive Hypothesis:
Assume k! ≥ 2^(k−1).
Inductive Step:
Show (k+1)! ≥ 2^k. We have (k+1)! = (k+1) times k! ≥ (k+1) times 2^(k−1). Since k+1 ≥ 2, this is ≥ 2 times 2^(k−1) = 2^k.
Why it fails: Without a base case there is no starting point. The chain of implications has nothing to anchor to. Both steps are mandatory.
Fix: Always verify the base case first, explicitly. If the statement starts at n = 0, verify n = 0, not n = 1.
Why it fails: If you assume what you are trying to prove, the argument is invalid no matter how convincing it looks.
Fix: Start with the left side for n = k+1. Use only algebra and the inductive hypothesis P(k) — never P(k+1) — to reach the right side.
Why it fails: You must prove that P(k) implies P(k+1). Proving that P(k+1) implies P(k) — or that P(k) is equivalent to P(k+1) — is not sufficient.
Fix: Always write your argument as: Assume P(k) is true. Then ... [algebra] ... therefore P(k+1) is true.
Why it fails: Jumping straight into algebra without a clear statement of P(n) makes it easy to lose track of what you are proving.
Fix: Start every induction proof by writing P(n): [exact statement]. Then P(k): [k version]. Then P(k+1): [k+1 version]. Know your destination before you start.
Why it fails: The inductive step often requires algebraic manipulation before you can apply the hypothesis. Rushing through the algebra causes errors.
Fix: Write out every step. Factor carefully. After applying the hypothesis, double-check that the result matches P(k+1) exactly.
Strong (complete) induction is a variant where the inductive hypothesis assumes the statement true for ALL values from the base case through k, rather than just for the single value k. This gives you more ammunition in the inductive step when proving k+1 requires more than just the immediately preceding case.
Strong Induction — Worked Example: Every integer n ≥ 2 is divisible by a prime.
Base Case (n = 2):
2 is prime and is divisible by itself. True. ✓
Strong Inductive Hypothesis:
Assume every integer j with 2 at most j at most k is divisible by a prime.
Inductive Step (n = k + 1):
Case 1: k+1 is prime. Then it is divisible by itself. Done.
Case 2: k+1 is not prime. Then k+1 = a times b for some integers a and b with 2 at most a, b at most k. By the strong hypothesis, a is divisible by some prime p. But p divides a and a divides k+1, so p divides k+1.
Either way, k+1 has a prime divisor. ✓
Why strong induction was needed:
The divisor a could be any value from 2 up to k, not necessarily k itself. We needed the hypothesis for ALL earlier values, not just the immediately preceding one.
Use strong induction when proving P(k+1) requires knowledge of multiple earlier cases — not just P(k). Classic examples: Fibonacci numbers, the Fundamental Theorem of Arithmetic, and statements about game theory or recursive algorithms.
In strong induction, the hypothesis is: Assume P(j) is true for all j with the base value at most j at most k. This lets you use any of P(1), P(2), ..., P(k) — not just P(k) — in your proof of P(k+1).
Sometimes strong induction requires multiple base cases. If the proof of P(k+1) uses P(k) and P(k-1), you must verify both P(1) and P(2) before the induction can begin. Check how far back your proof reaches.
Logically, strong induction and weak induction are equivalent — any theorem provable by one is provable by the other. Strong induction is simply more convenient when you need multiple earlier results.
The Well-Ordering Principle is the logical foundation that makes mathematical induction work. It is taught in Stewart Chapter 12 alongside induction because the two ideas are deeply connected.
Every non-empty set of positive integers has a smallest element. This seems obvious but is actually equivalent to mathematical induction as a logical foundation.
You can prove the Principle of Mathematical Induction from the Well-Ordering Principle, and vice versa. They are two ways of stating the same fundamental fact about the integers.
An alternative proof style uses well-ordering: assume the set of counterexamples to P(n) is non-empty, take its smallest element m, derive a contradiction (often by showing P(m-1) implies P(m)). This is equivalent to an induction proof.
Alternative proof that 1 + 2 + ... + n = n(n+1)/2: Suppose the formula fails for some positive integer. Let m be the smallest such integer. Since the formula works for n = 1, m is at least 2. Because m is the smallest counterexample, the formula works for m−1: the sum to m−1 equals (m−1)m/2. Adding m to both sides gives: sum to m = (m−1)m/2 + m = m[(m−1)/2 + 1] = m(m+1)/2. But this means the formula DOES work for m, contradicting that m is a counterexample. The set of counterexamples must therefore be empty, and the formula holds for all n.
This argument uses the well-ordering principle (there is a smallest counterexample) to reach a contradiction — logically equivalent to a standard induction proof.
Standard induction starts at n = 1, but the technique extends naturally to other starting points and other types of statements.
Some statements hold for all non-negative integers. Verify the base case at n = 0 instead of n = 1. Everything else is the same.
Prove 2^n ≥ n + 1 for n ≥ 0. Base case: 2⁰ = 1 = 0 + 1 = 1. True.
If a statement is only true from n = 2 onward, set the base case at n = 2. The inductive step still proves k implies k+1, but the chain only reaches integers from 2 upward.
Prove n² > 2n + 1 for all n ≥ 3. Base case: n=3: 9 > 7. True.
Write the statement in terms of k where n = 2k. The base case is n = 2 (k = 1) and each step goes from 2k to 2(k+1) = 2k+2.
Prove 4 divides (2k)! divided by (k!)² — or equivalently that C(2k, k) is even, by expressing the inductive step in terms of k.
Rarely tested in precalculus, but some proofs go from large n down to small n. The base case is a large value and you prove P(k) from P(k+1).
The AM-GM inequality can be proved by proving it for n = 2^m by forward induction, then filling in the gaps going downward.
Induction is the right tool when:
Other methods are better when:
Practical note for exams: On a precalculus test, if the problem says "prove using mathematical induction," you must use induction regardless of whether another approach is shorter. Always show all three components: base case, inductive hypothesis (stated explicitly), and inductive step with the hypothesis applied.
Proof by Mathematical Induction
Let P(n) be the statement: [write the exact formula or claim here].
Base Case (n = 1):
P(1): [substitute n = 1 into both sides and verify equality or inequality].
Therefore P(1) is true.
Inductive Step:
Let k be a positive integer and assume P(k) is true.
That is, assume: [write out P(k) explicitly].
We will show P(k+1) is true, that is: [write out P(k+1) explicitly].
[Algebra: start from one side of P(k+1), use the hypothesis to substitute, simplify]
Therefore P(k+1) is true.
Conclusion:
By the Principle of Mathematical Induction, P(n) is true for all positive integers n.
Mathematical induction is a proof technique used to prove statements that hold for all positive integers n. It works in two steps: first, you verify the statement is true for n = 1 (the base case). Second, you prove that IF the statement is true for some integer k, THEN it must also be true for k + 1 (the inductive step). Because the base case is true and each case implies the next, the statement must be true for all positive integers.
The inductive hypothesis is the assumption you make at the start of the inductive step. You write: Assume the statement is true for n = k. Then you write out exactly what that means for your specific formula. For example, if the statement is that 1 + 2 + ... + n equals n times (n+1) divided by 2, the inductive hypothesis says: 1 + 2 + ... + k equals k times (k+1) divided by 2. You then use this assumption to prove the statement for n = k + 1.
In weak (standard) induction, the inductive hypothesis assumes the statement is true for just one value, n = k, and uses it to prove the statement for n = k + 1. In strong induction, the inductive hypothesis assumes the statement is true for ALL integers from the base case up through n = k, and uses that broader assumption to prove n = k + 1. Strong induction is useful when the proof for k + 1 depends on earlier cases besides just k, such as in Fibonacci sequence proofs or prime factorization arguments.
To prove that an expression is divisible by some integer d for all n, you set up the two steps as usual. In the inductive step, you write the expression for n = k + 1, then substitute the inductive hypothesis to rewrite part of it as a multiple of d. The goal is to factor or reorganize the expression so it visibly equals d times some integer. A common approach: write the expression for k + 1, subtract and add the expression for k, then use the inductive hypothesis to replace the k version with a known multiple of d.
The most common mistakes are: (1) Forgetting the base case entirely — both steps are required. (2) Proving the wrong direction — you must show k implies k+1, not the reverse. (3) Circular reasoning — using n = k+1 to prove n = k+1 without connecting to the hypothesis. (4) Assuming what you want to prove — the inductive hypothesis is an assumption about k, not about k+1. (5) Wrong base case — if the statement starts at n = 0 or n = 2, you must verify that specific starting value, not n = 1.
Mathematical induction applies whenever you need to prove a statement for all positive integers (or all integers beyond some starting point). Common types include: summation formulas, divisibility statements, inequality proofs, and statements about sequences or recursive definitions. Induction is the right tool when you can express the n = k + 1 case in terms of the n = k case. If the problem involves finitely many cases or is not about integers, direct proof or another method is usually better.
Step-by-step induction problems with private tutoring — free to try. Build the proof-writing skills that separate A students from the rest.
Start Practicing Free