Why an induction proof reaches every integer

By UK A Level Further Mathematics · independent study · myAudience

Image: illustration, not a documentary photograph. Exact relationships follow the algebra; rendered diagram positions are illustrative. · Original generated project artwork; no source textbook or exam-board figures reused.

Why an induction proof reaches every integer

A pattern and a theorem are different kinds of claim. A diagram can suggest that adding successive odd numbers builds squares, and a numerical table can reinforce the conjecture, but neither exhausts the positive integers. Here the precise claim is 1 +3 +⋯+(2n−1)=n² for every integer n≥1. The integer domain and universal quantifier matter: a finite check cannot establish infinitely many cases, and the expression “the first n terms” needs n to be an allowed term count.

Induction proves a starting case and a successor implication. Think of the successor statement as a rule: whenever the claim holds at an arbitrary permitted k, it must also hold at k+1. It is not enough to demonstrate one transition, such as 3 to 4. The letter k must remain arbitrary, and each algebraic step must work for every k in the stipulated domain. A chain with no proved starting point may never start; a starting point with no valid successor gives no guarantee beyond that point.

The induction hypothesis is a conditional assumption used inside the successor argument. We may assume S(k)=k² to investigate S(k+1); we may not assume S(k+1)=(k+1)² and then pretend to derive it. Write the next sum as S(k)+(2k+1), substitute the permitted hypothesis once, and factor the resulting expression. This separation identifies which information comes from the definition of the next term and which comes from the hypothesis.

The least-counterexample explanation clarifies why the method reaches every positive integer. If any case failed, there would be a smallest failed positive integer. It could not be the base. Its preceding case would therefore be true, and the successor implication would force the supposed failure to be true as well. This reasoning depends on the well-ordering of positive integers. A proof over that domain cannot simply be relabelled as a statement about every real input.

Error diagnosis is part of proof, not an optional finishing flourish. A claimed proof starting at 3 establishes only cases 3 onward unless the smaller cases are separately checked. Replacing “suppose true at k” with “suppose true for all n” assumes the conclusion and is circular. Checking 1000 cases still supplies no arbitrary successor. Conversely, numerical evidence is useful for discovering that a conjecture is false: one permitted counterexample disproves a universal statement. Always match the method to the quantifier.

Prove that the first n positive odd integers sum to n² for n≥1. Explain why testing n=1,2,3 cannot establish the theorem. For n=1 the sum is 1 and the proposed expression is 1², so the base case holds. Suppose that for an arbitrary integer k≥1, the sum 1+3+⋯+(2k−1) equals k². This assumption is conditional, not an assertion that the whole theorem has already been proved. The sum through the next odd integer is k²+(2k+1). Factor the result as k²+2k+1=(k+1)². This is exactly the claimed expression with n replaced by k+1, so the induction step follows from the hypothesis. The base and step establish the identity for every positive integer. If a positive integer were the first failure, it could not be 1 because the base holds. Its predecessor would satisfy the identity, and the proved successor implication would make that alleged failure satisfy it too, a contradiction. Checking three inputs merely rules out failure at those three inputs; a formula could agree there and fail later. A numerical table is useful for forming the conjecture but supplies neither the arbitrary-k implication nor its domain. The proof does not apply to noninteger n, and an empty sum at n=0 would require an explicit additional domain convention. These distinctions turn an algebraic calculation into a justified infinite conclusion.

Prove that 7^n−1 is divisible by 6 for every integer n≥1; identify the induction hypothesis used. At n=1 the expression is 6. Assume 7^k−1=6m for an integer m. Then 7^(k+1)−1=7(7^k−1)+6=6(7m+1), an integer multiple of 6. Base and arbitrary successor imply the result for all n≥1. Checking residues at a few n is not the induction step.

The plate’s 3×3 square contains 9 cells and the 4×4 square contains 16. The gold border adds a top row of 4 and 3 further cells in the side column, giving 7 without counting the corner twice. This is the k=3 instance of adding 2k+1. Follow the three headings as a proof structure, not as a proof contained in the drawing. A separate challenge shows why the base matters: a claim P(n) that says n≥2 has a true successor implication for n≥1 but fails at 1. Therefore a successor rule alone cannot establish all positive cases.

Worked example: Prove that the first n positive odd integers sum to n² for n≥1. Explain why testing n=1,2,3 cannot establish the theorem.

Check n=1: the sum is 1=1².

Assume S(k)=k² for an arbitrary integer k≥1.

S(k+1)=S(k)+(2k+1)=k²+2k+1=(k+1)².

Base and arbitrary successor imply every positive integer; finite trials do not.

Answer: The odd sum equals n² for every integer n≥1; a valid base and arbitrary successor, not finite trials, prove it.

Check your understanding: Prove that 7^n−1 is divisible by 6 for every integer n≥1; identify the induction hypothesis used.

Answer: At n=1 the expression is 6. Assume 7^k−1=6m for an integer m. Then 7^(k+1)−1=7(7^k−1)+6=6(7m+1), an integer multiple of 6. Base and arbitrary successor imply the result for all n≥1. Checking residues at a few n is not the induction step.

Why: Credit exact equivalent derivations with the stated hypotheses, complete candidates and justified restrictions; a correct final value alone does not establish the full reasoning.