Optional course topic. You may skip it on the main route. Use the square of a sum and arithmetic sequences.

Tiles can form a square: one tile, then three more, then five. Mathematical induction proves a claim for every natural-number step by establishing a first case and a reliable passage to the next. Checking a hundred examples cannot replace that passage.

State the claim precisely

Here natural numbers mean integers n≥1. Our statement P(n) is:

1 + 3 + ⋯ + (2n − 1) = (n)^(2) (n = 1,2,3,…).

It sums the first n odd numbers; the last term is 2n−1. For n=3: 1+3+5=9.

Base case: somewhere to start

At n=1 the left side is 1 and the right side 1²=1. Thus P(1) holds. Without a base, the chain might have no established link.

Hypothesis: one arbitrary step

Take any integer k≥1 and assume P(k):

1 + 3 + ⋯ + (2k − 1) = (k)^(2).

We are not declaring the formula already true for all k. We prove a conditional connection: if it holds at this step, it holds at the next.

Step: add the next odd number

After 2k−1 comes 2k+1. Use the hypothesis to replace the preceding sum by k², then the square-of-a-sum identity:

1 + 3 + ⋯ + (2k − 1) + (2k + 1) = (k)^(2) + 2k + 1 = ((k + 1))^(2).

This is exactly P(k+1). The calculation works for every k≥1. The base and step imply P(n) for all n≥1 by induction. Principle and justification, MIT, p. 3.

From 3² to 4²

3² + (2·3+1) = 4²
9 old + 7 new = 16. Solid outlines mark the old square; dashes and color mark the new border. One cell is one unit; only step 3→4 is pictured.

The picture shows 3²+7=4²: the new border has 3+3+1 tiles. It explains the added 2k+1; the arbitrary-k argument above proves generality.

Breaking a supposed proof

False claim: all positive integers are odd. Base: 1 is odd. If k is odd, k+2 is odd too. Why is this invalid? It skips numbers: the base reaches 1,3,5,… but never 2. The number 2 is a counterexample.

A consecutive route needs k→k+1. A +2 step can cover all integers only with separate suitable bases for both parities; here base 2 already fails. Nor may we use P(k+1) as known during the step: that would be circular.

Check a finished proof for a clear domain, a base within it, one hypothesis P(k), a passage to the next case without unproved extra conditions, and the induction conclusion.