Further Maths Help.co.uk

Topics

Proof by induction

Prove the first case, then show that if a case is true, the next case must be true.

State the proposition P(n) and its integer range. Verify the base case directly. Assume P(k) for an arbitrary integer in the range, and use that assumption to prove P(k + 1). Together, the base case and this step prove P(n) for every integer in the stated range.

Do not assume the statement for k + 1 while trying to prove it. A few checked values establish examples, not the inductive step. If the claim starts at n = 2, the base case must match that starting index.

Worked example

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

  1. At n = 1, both sides equal 1.
  2. Assume the sum to k is k(k + 1)/2.
  3. Add k + 1: k(k + 1)/2 + k + 1 = (k + 1)(k + 2)/2.
  4. This is the required formula at k + 1, so the result follows for all integers n ≥ 1.

Answer: The formula holds for every integer n ≥ 1

Revise first: Expanding and factorising.

Practise proof by induction

Course mapping

These specification references show where the topic occurs. The questions cover only some parts of each topic.

Next practice: Arithmetic series.