A statement indexed by an integer — An induction proof establishes a statement P(n) over a declared integer domain, such as all n ≥ 1. The statement might concern a sum, divisibility or a matrix power. Write the full claim and starting value before calculating. A formula for positive integers does not automatically include zero or negative integers.
The base case anchors the chain — Prove P(n₀) directly at the first allowed integer. For Σ from r = 1 to n of r = n(n + 1)/2 with n₀ = 1, the sum is 1 and the formula also gives 1. A base calculation must establish the actual claim, including any conditions, rather than simply restate it.
The hypothesis is conditional — Let k be an arbitrary integer with k ≥ n₀, and assume P(k) holds. This is the induction hypothesis. It is an assumption within the conditional step, not a claim that the theorem is already proved. Copy the hypothesis accurately because its precise expression is the permitted replacement later.
The induction step advances one case — Starting from the expression for k + 1, use the hypothesis at k and valid algebra to prove P(k + 1). The target is the original statement with every relevant n changed to k + 1. Do not assume P(k + 1) itself. Showing P(k) implies itself adds no link in the chain.
The conclusion identifies the domain — Since P(n₀) is true and P(k) implies P(k + 1) for every integer k ≥ n₀, conclude by induction that P(n) holds for all integers n ≥ n₀. Both premises are needed. The mechanism is a chain of finite implications from the proved starting case to any chosen later integer.
Evidence is different from proof — Checking n = 1,2,3 can reveal an error or suggest a pattern but cannot establish a claim for every positive integer. For example n² + n + 41 is prime for n = 0 and n = 1, yet at n = 40 it is 1681 = 41². A finite list does not rule out a later counterexample.
The starting value can be later — For 2ⁿ > n², the claim is false at n = 4 because both sides are 16, but it is true for all integers n ≥ 5. Start by checking n = 5. The implication must hold throughout the declared range, not merely from an arbitrary convenient value for which the proof happens to work.
Advancing by two leaves a gap — A proof of P(k) implies P(k + 2) only connects values of the same parity: both odd or both even. To cover all integers from one onward, establish both P(1) and P(2), or provide another argument connecting the chains. A single odd base with a two-step implication does not prove the even cases.An implication from k to k+2 preserves parity. The upper chain starts at 1 and reaches only odd positive integers; the lower starts at 2 and reaches only even ones. Both bases are required to cover all positive integers by this two-step route. The dots mean the established implication continues, not that a finite drawing proves it.
Induction for finite sums
Separate the new summand — For Sₙ = Σ from r = 1 to n of f(r), Sₖ₊₁ = Sₖ + f(k + 1). The extra term uses k + 1, not k, and the earlier sum's lower bound is unchanged. This decomposition is what allows the hypothesis to replace Sₖ. Match the exact indexing before expanding.
The sum of the first integers — Assume Sₖ = k(k + 1)/2. Then Sₖ₊₁ = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2. The last expression is the claimed formula with n = k + 1. Together with the n = 1 base this proves the formula for all positive integers.
The sum of the first odd integers — The claim 1 + 3 + … + (2n − 1) = n² has base 1 = 1². Assuming the sum through 2k − 1 is k², add the next odd number 2k + 1 to obtain k² + 2k + 1 = (k + 1)². Adding 2k − 1 again would repeat the last existing term rather than extend the sum.The illustration uses k=3. Nine pale cells form a 3×3 square; seven highlighted cells add one new row and column, counting their shared corner once, to make 4×4. Generally the added border has k+(k+1)=2k+1 cells. The algebraic induction step establishes the formula for all positive integers; this one picture illustrates its meaning.
The sum of squares — Assume Σ from r = 1 to k of r² = k(k + 1)(2k + 1)/6. Adding (k + 1)² gives (k + 1)[k(2k + 1) + 6(k + 1)]/6 = (k + 1)(k + 2)(2k + 3)/6. Show the factorisation 2k² + 7k + 6 = (k + 2)(2k + 3). Check n = 1 and conclude on positive integers.
A weighted geometric sum — For Σ from r = 1 to n of r2ʳ = (n − 1)2ⁿ⁺¹ + 2, the base n = 1 gives 2 = 2. Assume the formula at k. Add (k + 1)2ᵏ⁺¹ to obtain [(k − 1) + (k + 1)]2ᵏ⁺¹ + 2 = k2ᵏ⁺² + 2, the formula at k + 1. Retain the final constant two; it does not grow with each step.
A sum with a later lower bound — For Σ from r = 3 to n of (2r − 1) = n² − 4 with n ≥ 3, check the base n = 3: the one term is 5. Assume the sum to k is k² − 4 and add 2k + 1, giving (k + 1)² − 4. The lower bound changes the constant and the starting integer; using the first-odd-sum formula unchanged would be wrong.
Work toward the exact next-case form — If the target is a factored expression, the step should end with that form at k + 1 or explicitly show equivalence. Expanding two complicated expressions independently can obscure where the hypothesis is used. Begin with the actual next-case sum, replace only its known initial part and then simplify.
Divisibility and inequalities
What divisibility asserts — For integers d ≠ 0 and N, d divides N means N = dq for some integer q. In an induction hypothesis state the integer multiple explicitly or use a clear congruence: for example, N ≡ 0 (mod d) means that N leaves remainder zero on division by d. A quotient that happens to be a decimal approximation to an integer is not an exact divisibility proof.
A simple exponential divisibility proof — To prove 7 divides 8ⁿ − 1 for n ≥ 1, the base is 8 − 1 = 7. Assume 8ᵏ − 1 = 7q with integer q. Then 8ᵏ⁺¹ − 1 = 8(8ᵏ − 1) + 7 = 7(8q + 1). Since 8q + 1 is an integer, the next case is divisible by seven. State the induction conclusion.
Rewriting around the hypothesis — For 5ⁿ − 1 divisible by four, write 5ᵏ⁺¹ − 1 = 5(5ᵏ − 1) + 4. The additive correction restores the original constant after multiplication. Writing it as 5(5ᵏ − 1) alone omits four and does not equal the next-case expression.
A polynomial divisibility proof — The claim 3 divides n³ − n has base n = 1 giving zero, and zero is divisible by three. Assuming k³ − k = 3q, expand (k + 1)³ − (k + 1) = (k³ − k) + 3k(k + 1) = 3[q + k(k + 1)]. The bracket is an integer. This proves positive integers; other integer domains need a separate extension if requested.
An alternating-sign exponential claim — For 3 divides 2ⁿ − (−1)ⁿ, the base gives 2 − (−1) = 3. Let Eₖ = 2ᵏ − (−1)ᵏ be divisible by three. Then Eₖ₊₁ = 2Eₖ + 3(−1)ᵏ, a sum of multiples of three. Track the sign of (−1)ᵏ⁺¹ before simplifying; treating it as constant one loses half the cases.
An inequality needs a valid bridge — To prove 2ⁿ > n² for n ≥ 5, the base is 32 > 25. Assume 2ᵏ > k². Then 2ᵏ⁺¹ > 2k². For k ≥ 5, 2k² − (k + 1)² = k² − 2k − 1 = (k − 1)² − 2 > 0. Therefore 2ᵏ⁺¹ > (k + 1)². The bridge inequality is justified over the required range rather than silently assumed.
Safe inequality operations — Multiplying an inequality by a positive number preserves its direction; multiplying by a negative number reverses it. In an induction proof state why the relevant quantities have the signs used. Assuming P(k) and then squaring both sides without checking nonnegativity can make an invalid step look algebraically plausible.
Matrix powers and proof diagnosis
A matrix statement is an entrywise claim — For A = [1,a; 0,1] with fixed real a, the claim is Aⁿ = [1,na; 0,1] for positive integers n. Each entry matters. The parameter a stays fixed while n changes. Proving just one diagonal entry or the determinant does not establish the entire matrix identity.
An induction step for a shear matrix — The n = 1 case agrees with A. Assume Aᵏ = [1,ka; 0,1]. Then Aᵏ⁺¹ = AᵏA = [1,(k + 1)a; 0,1] by row-column multiplication. This is the target for k + 1. A⁰ = I also agrees with the same formula, but if the declared domain is n ≥ 0, verify zero as the base explicitly.
A second exact matrix-power family — For B = [2,1; 0,2], the claim is Bⁿ = [2ⁿ,n2ⁿ⁻¹; 0,2ⁿ] for n ≥ 1. At k, multiply the claimed Bᵏ by B: the top-right entry is 2ᵏ + 2k2ᵏ⁻¹ = (k + 1)2ᵏ. Both diagonal entries become 2ᵏ⁺¹. These are exactly the entries required for k + 1; the base is B itself.
Powers preserve factor order — Aᵏ⁺¹ = AᵏA = AAᵏ because these are powers of the same matrix. This does not establish that unrelated matrices commute. If a formula involves a product of different matrices, preserve their order through every substitution and multiplication. Entrywise exponentiation is not how a matrix power is defined.
A circular argument fails — Writing “assume the formula for k + 1, simplify it, therefore it is true” assumes the desired conclusion. A valid proof uses only the kth hypothesis plus established facts. Working backwards can help discover algebra, but the final justification must show a valid implication rather than rely on an unproved next case.
The gap in the all-horses argument — A false argument claims any group of n horses has one colour, then compares two overlapping n-horse subgroups of n + 1 horses. The base n = 1 is true, but at the step from one to two horses the two single-horse subgroups do not overlap. The supposed common horse does not exist, so the implication fails at the first required step.
Testing and repairing an attempted proof — Audit the domain, actual base, exact hypothesis, new summand or factor, and next-case target. Locate a concrete unsupported equality or failed range rather than declaring a proof wrong because it looks unfamiliar. A counterexample refutes a false statement; a corrected base or algebraic step repairs only a true statement for a justified domain.
Writing a complete proof efficiently — Name the claim, verify the starting case, assume it at arbitrary k in range, show the step with the hypothesis visibly used, then conclude for the declared integers. Include enough arithmetic for the crucial factorisation or divisibility multiple to be checked. A short complete argument is stronger than many unconnected calculations.
Test yourself
50 questions · Random sets of 10. These quick checks support revision; practise longer explanations and justified judgements too.
Mr Kidman's Classroom
