Further proof

What further proof covers

One method, applied to three kinds of statement. Mathematical induction establishes a first case, shows that each case forces the next, and concludes that the whole line follows. It is Core Pure content, so it is examinable on both compulsory papers of 9FM0 and every Further Mathematics candidate sits it. The unit is two lessons long and marked line by line.

The main ideas

• The principle itself: verify the base case, assume the statement at k, and deduce it at k + 1.
• Sum formulae, where the step is the same each time: add the next term to the assumed total, then tidy into the target shape.
• Divisibility results, where the k + 1 expression is rearranged around the assumed one plus a visible multiple of the divisor.
• Formulae for the nth power of a matrix, proved by one multiplication written out entry by entry.
• Naming the hypothesis with a letter, so that the final factorisation can be checked rather than asserted.
• The conclusion sentence, naming the base case, the inheritance from k to k + 1, and induction itself.

The results it turns on

verify P(1), assume P(k), then deduce P(k + 1)

the shape every proof in this unit takes

the sum to k + 1 terms = the assumed sum to k terms + the (k + 1)th term

the inductive step for a series

8^k+1 − 1 = 8(8^k − 1) + 7

the rearrangement a divisibility step is built on

A^k+1 = A^kA

the inductive step for a matrix power, shown for all four entries

Where it usually goes wrong

• Writing that a statement is true for n = 1 without evaluating both sides verifies nothing, and the base case carries its own mark.
• A bare assumption that the statement holds for k is worth little. The assumption has to be written out in full, with the letter that later makes the factorisation checkable.
• In a divisibility proof the final bracket may not look like a multiple of the divisor. Factor the divisor out explicitly and say that you have.

Where to start

Sums and series first, since the step is the most mechanical of the three and the layout is the one every later proof reuses. Divisibility and matrices second, and take it after matrix multiplication is fluent, because the matrix flavour is one product written carefully.