Proof by Induction: Summing 1 to n

Checking is not proving

Suppose a formula works for n = 1, 2, 3 and 4. That does not show it works for every n. The expression n² + n + 41 gives a prime number for every n from 0 to 39, and then at n = 40 it gives 1600 + 40 + 41 = 1681 = 41 × 41, which is not prime. Checking cases one at a time can never cover every whole number, because there are infinitely many of them.

Proof by induction covers them all with two steps. Think of a long line of dominoes. If the first domino falls, and each domino knocks over the next one when it falls, then every domino falls, however long the line is.

The claim is true at 1, and each true case forces the next: 1 forces 2, 2 forces 3, and so on along the whole line.

The claim and the base case

Here is the claim to prove: 1 + 2 + … + n = n(n + 1)/2 for every positive whole number n.

The first step is the base case, which checks the first domino. At n = 1 the left side is just 1, and the right side is 1 × 2/2 = 1. They agree, so the claim is true for n = 1.

The second step is the inductive step. Assume that the claim is true for some number n. This assumption is called the induction hypothesis. Then show that the claim must also be true for the next number, n + 1. This does not assume what we are trying to prove: it assumes one case and uses it to prove the next.

From n to n + 1

The sum up to n + 1 is the sum up to n with one more term, n + 1, added on. By the induction hypothesis the sum up to n is n(n + 1)/2, so the sum up to n + 1 is n(n + 1)/2 + (n + 1).

Both parts contain n + 1. The first part is n/2 lots of (n + 1), and the second part is 1 lot of (n + 1). Together they make n/2 + 1 lots of (n + 1), which is (n + 1)(n/2 + 1). Since n/2 + 1 = (n + 2)/2, the sum up to n + 1 is (n + 1)(n + 2)/2.

That is the claim with n + 1 in place of n: replace every n in n(n + 1)/2 by n + 1 and you get (n + 1)(n + 2)/2. So if the claim is true for n, it is true for n + 1. For example, from n = 3 to n = 4: 6 + 4 = 10, and 4 × 5/2 = 10.

$2 (1 + 2 + \dots + 3) = 3 \times 4 = 12 \Rightarrow 1 + 2 + \dots + 3 = \frac{3 \times 4}{2} = 6$

two staircases make an 3 × 4 rectangle of 3 × 4 blocks, so one staircase is half: n(n + 1)/2 = 6

Set n = 6 and slide the second staircase in

Two staircases of 1 + 2 + … + n fill an n by (n + 1) rectangle, so one staircase is n(n + 1)/2. Raise n one step at a time to 6: each staircase gains a new step of n + 1 blocks, and the two still fill the rectangle.

Every n

Now put the two steps together. The claim is true for 1 by the base case. The inductive step with n = 1 makes it true for 2. The inductive step with n = 2 makes it true for 3, and so on without end. Every positive whole number is reached, so the claim is true for every n.

A proof by induction ends by saying this: the claim is true for n = 1, and whenever it is true for n it is true for n + 1, so by induction it is true for every positive whole number n.

Both steps are needed. Without the base case, nothing starts the chain. Without the inductive step, only the cases you checked are known to be true, as n² + n + 41 showed.

Odd numbers make squares

The next problem proves that 1 + 3 + 5 + … + (2n − 1) = n². It writes k for the number in the induction hypothesis, where this lesson wrote n. Its inductive step adds the next odd number, 2k + 1, to k², and needs k² + 2k + 1 = (k + 1)².

A square of tiles shows why. A k by k square holds k² tiles. To turn it into a (k + 1) by (k + 1) square, add a row of k tiles, a column of k tiles and one tile in the corner. That is k + k + 1 = 2k + 1 tiles, in an L-shape. So k² + 2k + 1 = (k + 1)².

A 4 by 4 square of 16 tiles and an L-shaped border of 4 + 4 + 1 = 9 tiles make a 5 by 5 square: 16 + 9 = 25.

Worked example: A Square Patio Laid in L-Shaped Rings of Tiles, and the Tiles Needed to Enlarge It

Question A square patio is laid from square tiles, one ring at a time. Ring 1 is a single tile. Each new ring is an L-shaped band along two sides that turns the square into the next larger square, so ring k uses (2k − 1) tiles. (a) Prove by induction that 1 + 3 + 5 + … + (2n − 1) = n² for every positive whole number n. (b) A patio has 12 rings. It is to be enlarged to 20 rings. How many more tiles are needed?

1.Let P(n) be the statement 1 + 3 + … + (2n − 1) = n². Base case, n = 1: the left side is 1 and the right side is 1² = 1, so P(1) is true.

Base case: ring 1 is one tile, and 1 = 1².
2.Inductive step: assume that P(k) is true for some positive whole number k, that is, 1 + 3 + … + (2k − 1) = k².

Assume the first k rings make a k by k square of k² tiles.
3.Ring k + 1 uses 2(k + 1) − 1 = 2k + 1 tiles. So 1 + 3 + … + (2k − 1) + (2k + 1) = k² + 2k + 1 = (k + 1)², which is the statement P(k + 1).

Ring k + 1 adds 2k + 1 tiles: k² + 2k + 1 = (k + 1)².
4.(a) P(1) is true, and whenever P(k) is true, P(k + 1) is true. So by induction, 1 + 3 + … + (2n − 1) = n² for every positive whole number n: the first n rings use n² tiles.

(a) The base case and the inductive step prove 1 + 3 + … + (2n − 1) = n² for every n.
5.(b) Twenty rings use 20² = 400 tiles and twelve rings use 12² = 144 tiles, so rings 13 to 20 need 400 − 144 = 256 more tiles. Check the first new ring: ring 13 uses 2 × 13 − 1 = 25 tiles, and 12² + 25 = 169 = 13².

(b) Rings 13 to 20 are the gold band: 20² − 12² = 400 − 144 = 256 tiles.

Answer: (a) 1 + 3 + … + (2n − 1) = n² for every positive whole number n; (b) 400 − 144 = 256 more tiles

Common mistakes

Checking the formula for n = 1, 2, 3 and stopping there. A few cases do not prove it for every n; the inductive step is what carries it from each case to the next.
Adding 2k − 1 in the inductive step. That is ring k, which is already in the sum; the new ring is ring k + 1, with 2(k + 1) − 1 = 2k + 1 tiles.

More sequences and series problems, worked step by step →