Mathematical induction

One new odd layer makes the next square

Start with one dot. Add an L-shaped layer of three dots to make a 2 by 2 square, then five dots to make a 3 by 3 square. The totals are 1, 4 and 9. The picture suggests that adding the first n positive odd numbers gives n². How could we prove this for every positive integer n, rather than merely checking the squares we can draw?

A k by k square contains k² dots. To grow it into a (k + 1) by (k + 1) square, add a row of k + 1 dots and a column of k dots. The corner belongs to the row only, so it is not counted twice. The new layer has 2k + 1 dots, the next odd number.

The equality k² + (2k + 1) = (k + 1)² explains the growth at any positive integer k. It tells us how a correct total at one stage leads to the correct total at the next. We also need a correct first stage. Mathematical induction combines exactly these two facts: a start and a rule that always reaches the next stage.

Prepare the algebra and read one proof first

Symbols, definitions and mathematical language helps you distinguish an index from a statement about it. Variables, expressions and substitution explains arbitrary k and substituting k + 1. Expanding, factoring and algebraic identities supplies (k + 1)² = k² + 2k + 1. Examples, explanations and counterexamples helps separate a successful sample from a general reason.

Chapter preparation to return to: Statements, truth values and logical connectives; Quantifiers and precise mathematical claims; Direct proof and contrapositive arguments. Their required ideas are explained in this lesson.

A first reading

Follow the growing square, the ordinary-induction rule and the first worked example. Inspect base and step failures next. Return to strong induction after identifying the exact allowed hypothesis.

Return for the proof structure

Revisit the least-failure explanation and the bundled-proposition equivalence once the ordinary base and step are clear.

Statements, truth values and logical connectives; Quantifiers and precise mathematical claims; and Direct proof and contrapositive arguments are further logical preparation in this chapter. Their roles are explained here: P(k) is one statement, “for every k” ranges over the stated integers, and an implication must derive its conclusion from its assumption. These chapter topics are preparation to return to, rather than extra assumptions inside a proof.

On a first reading, follow the growing square, the ordinary-induction rule and the first worked proof. Then inspect the missing-base and failed-step cases. Return to strong induction after you can state exactly what the induction hypothesis permits. The explanation of why the rule works and the equivalence of its two forms can be a second reading.

P(n) is one instance; the theorem quantifies over n

For the square claim, let P(n) mean “1 + 3 + 5 + … + (2n − 1) = n²”. Here n is a positive integer, so the sum has exactly n terms. P(1) is the statement 1 = 1². P(3) is the statement 1 + 3 + 5 = 3². The theorem says P(n) is true for every integer n ≥ 1.

Do not put “for every n” inside P(n) and then assume that whole theorem as the induction hypothesis. The hypothesis will be a single instance P(k), or a precisely specified finite range of instances in strong induction. It is not the desired universal conclusion.

In this lesson ℤ means the integers. A domain n ∈ ℤ, n ≥ n₀, specifies all integer indices from n₀ onwards. We choose n₀ ≥ 0 and always state it explicitly; conventions for whether the symbol ℕ begins at 0 or 1 therefore cause no ambiguity. Induction here concerns these consecutive integer indices, not every real value between them.

Some claims begin at 0, others at 1 or a later index. The starting index is part of the theorem. A proof beginning at 4 proves nothing about indices 0 through 3 unless those cases are separately covered. Expressions in P(n) must also be defined throughout its stated domain.

Verify the base and prove the arbitrary successor step

To prove P(n) for every integer n ≥ n₀, first prove P(n₀). This is the base case: it starts the chain. Next choose an arbitrary integer k ≥ n₀ and assume P(k). Using that induction hypothesis and established facts, derive P(k + 1). This proves the conditional P(k) ⇒ P(k + 1) for every such k.

Conclude by mathematical induction that P(n) holds for every integer n ≥ n₀. Both requirements matter. A start without a general step only checks an initial case. A valid step without a true start may have nothing from which to move.

The hypothesis P(k) is local to the proof of the conditional. You are not assuming that it is already true for every k, nor assuming P(k + 1). After the base and conditional are proved, induction licenses P(n₀ + 1), then P(n₀ + 2), and each later instance. Every chosen finite target needs only finitely many links.

A staircase with a reachable first step and a rule for reaching each next step is a useful analogy. It does not prove either mathematical requirement. State and justify the actual proposition, base and general successor calculation.

The growing-square identity gives a complete proof

Prove P(n): 1 + 3 + … + (2n − 1) = n² for all integers n ≥ 1. Base n = 1: the single term is 1, and 1² = 1. Thus P(1) is true.

For the step, take an arbitrary integer k ≥ 1 and assume 1 + 3 + … + (2k − 1) = k². The first k + 1 odd terms consist of these first k terms and the new term 2(k + 1) − 1 = 2k + 1.

Substitute the induction hypothesis, then expand the square: 1 + 3 + … + (2k − 1) + (2k + 1) = k² + 2k + 1 = (k + 1)². This is exactly P(k + 1). The old sum was replaced by k² because of P(k), not because we had assumed the theorem for every index.

The verified base and arbitrary successor step prove the identity for every integer n ≥ 1. The drawing shows the same added layer without double-counting. It is a finite illustration of the general algebra, not a reason to restrict the theorem to the pictured sizes.

A first failure would contradict a verified step

Another explanation uses the least-element property: every nonempty set of nonnegative integers has a least member. Suppose the base and successor step are established but some permitted index fails. The nonnegative offsets n − n₀ of failing indices would have a least value, giving a first failing index m.

The base is true, so m > n₀. Since m is the first failure, P(m − 1) is true. The verified step at k = m − 1, which is still at least n₀, then gives P(m). This contradicts the supposed failure. Therefore no permitted index fails.

This explains the induction rule using the least-element property; it does not replace the need to prove a theorem’s particular base and step. Proof by contradiction is further preparation for this explanation. The ordinary-induction proof above can be followed without first learning that separate proof technique.

A later base keeps an inequality’s step valid

Consider P(n): 2^n ≥ n² for integers n ≥ 4. At n = 4, both sides are 16, so the base includes equality. At n = 3, 8 < 9; the theorem with a start at 3 would be false.

Let k ≥ 4 be an arbitrary integer and assume 2^k ≥ k². Multiplying by positive 2 preserves the inequality: 2^(k + 1) = 2 × 2^k ≥ 2k². To reach the desired (k + 1)², establish 2k² ≥ (k + 1)².

Their difference is 2k² − (k + 1)² = k² − 2k − 1 = k(k − 2) − 1. For k ≥ 4, k ≥ 4 and k − 2 ≥ 2, so the nonnegative-factor bounds give k(k − 2) − 1 ≥ 4 × 2 − 1 = 7 > 0. Therefore 2^(k + 1) ≥ (k + 1)².

Induction proves the non-strict claim for all integers n ≥ 4. It does not say that it fails at every earlier index: n = 0, 1 and 2 also satisfy it, while 3 does not. A correct domain and a true lower bound do not have to be the only true inputs.

Strong induction allows the whole earlier range

Sometimes the proof of the next case needs an earlier case other than the immediate predecessor. In strong induction, take an arbitrary integer k ≥ n₀ and assume P(j) for every integer j with n₀ ≤ j ≤ k. Derive P(k + 1). Together with P(n₀), that establishes every P(n) for integer n ≥ n₀.

The hypothesis is a complete earlier range, including its endpoints. It does not include P(k + 1) and does not permit an index below n₀. Before using P(k − 2), for example, check n₀ ≤ k − 2 ≤ k.

A step may become usable only after several initial cases. If you prove P(n₀), …, P(b) separately and prove the strong conditional for every integer k ≥ b, the initial block plus that step covers all n ≥ n₀. Do not prove only P(n₀) when your first legal dependency lies further ahead.

Ordinary induction assumes only P(k) in its step. Strong induction permits more earlier instances as hypotheses, which can make the proof easier to write. These forms prove the same class of indexed theorems; “strong” describes the available step hypothesis, not greater logical power.

Three initial totals make every later target reachable

Prove that every integer n ≥ 12 can be written n = 3a + 5b with nonnegative integers a and b. Think of tokens worth 3 and 5 units. The units are abstract counts, and no negative or fractional number of tokens is allowed. The bound 12 is sufficient; we are not claiming it is the smallest possible starting bound.

Prove three initial cases: 12 = 3 × 4 + 5 × 0, 13 = 3 × 1 + 5 × 2, and 14 = 3 × 3 + 5 × 1. All the token counts are nonnegative integers.

For the strong step, choose an arbitrary integer k ≥ 14 and assume every integer j from 12 through k has such a representation. The next target is k + 1. Its predecessor k − 2 = (k + 1) − 3 satisfies 12 ≤ k − 2 ≤ k. Therefore the hypothesis supplies k − 2 = 3a + 5b for some nonnegative integers a and b.

Add one 3-unit token: k + 1 = (k − 2) + 3 = 3(a + 1) + 5b. The new counts a + 1 and b remain nonnegative integers. This proves the next case, so the initial block and strong induction cover every integer n ≥ 12.

The drawing arranges totals in three columns according to their remainder after division by 3. Arrows add 3, rather than jumping to the next numerical index. The bases 12, 13 and 14 start all three columns. In the strong proof, all smaller permitted totals are available, so the chosen predecessor is justified regardless of its column.

A bundled proposition converts the strong rule to the ordinary rule

A strong-induction hypothesis includes P(k), so any ordinary successor proof can be used inside a strong proof. To see the reverse direction, bundle the earlier instances into Q(k): “P(j) holds for every integer j with n₀ ≤ j ≤ k”.

Suppose the strong base and conditional are established. Q(n₀) is exactly P(n₀), so it is true. Assume Q(k) for arbitrary k ≥ n₀. The strong conditional gives P(k + 1), while Q(k) retains every earlier P(j). Combining them gives Q(k + 1). Ordinary induction applied to Q therefore proves every Q(k), and hence every P(k).

For an initial block through b, begin this bundled proof at Q(b), which the verified block supplies. Its conclusion covers the earlier block as well as every later case. Thus multiple initial cases and earlier dependencies still use a precise start and a step covering each new target.

Three different faults can break an induction argument

Missing base: let P(n) mean n² ≥ 5 on integers n ≥ 2. For k ≥ 2, the conditional P(k) ⇒ P(k + 1) is valid because (k + 1)² ≥ k². But P(2) is false: 4 < 5. A true conditional from a false antecedent does not create a true first case. Starting at 3 would repair this theorem, but would change its stated domain.

Failed step: let P(n) mean (n − 1)(n − 2)(n − 3)(n − 4) = 0 for integers n ≥ 1. The first four instances are true, but P(5) is false because the product is 24. The link P(4) ⇒ P(5) is false. Four successful checks do not prove the arbitrary successor step.

Coverage gap: P(n) meaning “n is even” has a true base at 0 and a valid step from n to n + 2. Those links reach only the even nonnegative integers. They do not prove P(n) for every n ≥ 0; n = 1 is a counterexample. A jump of 2 is not the ordinary successor step of 1.

A jump of 2 can cover all nonnegative integers if both residue classes have true starts and valid links. For example, n² ≥ 0 is true at 0 and 1, and the step n → n + 2 preserves it. The two interleaved chains then cover all n ≥ 0. This easy theorem needs no induction in practice; the diagram is useful for distinguishing coverage from truth.

Use a finite model to check a proof, then write the general argument

A finite table gives exact truth values for exactly the indices it lists. One false permitted instance refutes a universal claim. Several true instances cannot establish all infinitely many instances or certify a conditional for every k. Reachability marks in these diagrams concern only the displayed bases and displayed links.

In Growing squares, predict how many dots the new row and column add, then compare their count with 2k + 1. In Base, step and coverage, distinguish the actual truth T or F from whether the pictured proof chain reaches that node. A conditional with a false antecedent can be true while its arrow carries no established instance.

In Earlier totals, choose a target and locate its predecessor three less. Check both endpoints of the earlier range, the nonnegative token counts and the three initial bases before revealing the exact representation. The computed witnesses illustrate the construction; the arbitrary-index strong proof covers every later integer.

A complete written induction proof states its theorem and domain, verifies every needed initial case, names an arbitrary permitted step index, records exactly the allowed induction hypothesis and derives the next instance with reasons. Its final sentence uses induction to reach the whole stated domain, rather than merely announcing that a numerical pattern continues.

Worked examples

Try it yourself

1. Let P(n) mean 1 + 3 + … + (2n − 1) = n² on integers n ≥ 1. State P(4), the induction hypothesis at k and the target at k + 1.

   Show the answer and reasoning

   P(4): 1 + 3 + 5 + 7 = 16. Hypothesis: the first k odd terms sum to k². Target: the first k + 1 odd terms sum to (k + 1)².

   P(k) is one equality at an arbitrary positive integer k. It is not the assertion that every P(n) has already been proved. The new term in the target is 2k + 1.

2. Prove 1 + 2 + … + n = n(n + 1)/2 for all integers n ≥ 1.

   Show the answer and reasoning

   Base 1: 1 = 1 × 2/2. Assume the sum through k is k(k + 1)/2. Adding k + 1 gives (k + 1)(k + 2)/2. Thus the formula holds for all n ≥ 1 by induction.

   Choose arbitrary integer k ≥ 1. The next sum is k(k + 1)/2 + (k + 1) = (k + 1)(k/2 + 1) = (k + 1)(k + 2)/2. The fixed denominator 2 is nonzero; the factorisation derives the required next formula from the hypothesis.

3. An argument proves P(k) ⇒ P(k + 1) for P(n): n² ≥ 5 on integers n ≥ 2, then concludes all P(n). What is missing, and what domain repair works?

   Show the answer and reasoning

   P(2) is false because 4 < 5, so the chain has no verified start. Changing the theorem to n ≥ 3 gives the true base 9 ≥ 5 and a valid step.

   For k ≥ 2, (k + 1)² − k² = 2k + 1 > 0, so a true P(k) would imply P(k + 1). That conditional does not make P(2) true. A repaired lower bound changes the original universal claim.

4. The product (n − 1)(n − 2)(n − 3)(n − 4) is zero at n = 1, 2, 3, 4. Which first successor link refutes a claim that it is zero for all integers n ≥ 1?

   Show the answer and reasoning

   The link 4 → 5 fails: P(4) is true but P(5) is false, since 4 × 3 × 2 × 1 = 24.

   Earlier samples satisfy the claim because one factor is zero. At 5 every factor is nonzero. One false permitted instance refutes the universal theorem and exposes a false induction conditional.

5. A theorem on all integers n ≥ 0 has only the true base P(0) and the step P(k) ⇒ P(k + 2) for every k ≥ 0. Which indices are reached, and what extra start would be needed for full coverage?

   Show the answer and reasoning

   Only 0, 2, 4, … are reached. A separately proved P(1), with the same valid step, starts 1, 3, 5, … and completes coverage.

   A jump of 2 preserves parity, so one base cannot reach both remainder classes. This is a coverage requirement; the extra base must actually be true. For P(n): n is even, P(1) is false and the full-domain theorem cannot be repaired just by naming it a base.

6. In the 3/5-token proof with bases 12, 13, 14, consider target 23. State k, its earlier predecessor, the legal hypothesis range and an exact representation.

   Show the answer and reasoning

   k = 22; predecessor 20 belongs to 12 ≤ j ≤ 22. Since 20 = 3 × 5 + 5 × 1, adding one 3 gives 23 = 3 × 6 + 5 × 1.

   The strong hypothesis concerns every integer through k, not only k. The predecessor is target − 3 = k − 2, which is at least 12 for every target at least 15. Both token counts remain nonnegative integers.

7. Improve the token theorem to all integers n ≥ 8. Give a sufficient initial block and the strong step; check that the preceding index is legal.

   Show the answer and reasoning

   Bases: 8 = 3 + 5, 9 = 3 × 3, 10 = 5 × 2. For k ≥ 10, the target k + 1 uses k − 2 ≥ 8; add one 3-unit token to its representation.

   The three bases cover the add-3 remainder classes. For arbitrary k ≥ 10, assume all representations from 8 through k. Then 8 ≤ k − 2 ≤ k, so the step is licensed. Induction gives every n ≥ 8. Also 7 is impossible: zero 5-tokens leave 7, not a multiple of 3; one leaves 2; two already exceed 7. Thus 8 is the least starting bound for a theorem covering every later nonnegative integer.

8. For a theorem on integers n ≥ n₀, may a strong-induction step assume P(k + 1)? Explain how its allowed hypothesis can instead be bundled for ordinary induction.

   Show the answer and reasoning

   No. It may assume only P(j) for n₀ ≤ j ≤ k. Bundle those instances as Q(k); the strong step proves the new P(k + 1), so Q(k + 1) follows from Q(k).

   The bundle preserves earlier proved instances and appends exactly one new instance. Its base Q(n₀) is P(n₀). Ordinary induction then proves every bundle and hence every P(n), establishing equivalence without assuming the conclusion of a step.

What to carry forward

• State an indexed proposition and the exact consecutive integer domain before proving it.
• Ordinary induction needs a true base and P(k) ⇒ P(k + 1) for every permitted step index.
• Strong induction permits the entire stated earlier range; every dependency must lie within it.
• Multiple starts are needed when a delayed step or a jump would otherwise leave cases uncovered.
• Finite checks can reveal a counterexample, but the general base-and-step argument proves all later instances.
• Ordinary and strong induction have equivalent logical power; choose the form that makes the dependencies clear.