Proof by mathematical induction

Proof by mathematical induction

Spec 8.1 · Edexcel International A Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Four steps: basis, assumption, inductive step, conclusion.
  • Assume P(k)P(k) is true; you must prove P(k+1)P(k+1), not assume it.
  • For series, add the next term to the assumed sum and factorise.
  • For divisibility, find f(k+1)−a f(k)f(k+1)-a\,f(k) to cancel the power.
  • Always write the full conclusion sentence.

The four steps

Show P(1)P(1) is true, assume P(k)P(k), prove P(k+1)P(k+1), then conclude.

To prove a statement P(n)P(n) for all positive integers nn, follow four steps.

The idea is a chain: P(1)P(1) gives P(2)P(2), which gives P(3)P(3), and so on. The basis starts the chain; the step keeps it going. Without either, the proof is incomplete.

  1. 1

    Basis

    show P(1)P(1) is true, checking both sides of the statement

  2. 2

    Assumption

    assume P(k)P(k) is true for some positive integer kk

  3. 3

    Inductive step

    use the assumption to show P(k+1)P(k+1) is true

  4. 4

    Conclusion

    P(1)P(1) is true and P(k)⇒P(k+1)P(k)\Rightarrow P(k+1), so P(n)P(n) is true for all positive integers nn by mathematical induction

The four steps of an induction proof

What do you assume in the second step?

Summation of series

Add the next term to the assumed sum, then factorise to reach the formula with n=k+1n=k+1.

The step adds the next term to the assumed sum. In the step, factorise out common factors rather than expanding everything.

The same method proves ∑r=1nr3=n2(n+1)24\sum_{r=1}^{n}r^3=\frac{n^2(n+1)^2}{4}.

0.511.522.533.544.520406080100120nsum of cubes(1, 1)(2, 9)(3, 36)(4, 100)n²(n+1)²/4
Partial sums of cubes: the points 1, 9, 36, 100 lie on the curve n²(n+1)²/4
  • ∑r=1k+1\sum_{r=1}^{k+1}∑r=1k\sum_{r=1}^{k} + the (k+1)(k+1)th term

Worked example

Prove that ∑r=1nr(r+1)=n(n+1)(n+2)3\sum_{r=1}^{n}r(r+1)=\frac{n(n+1)(n+2)}{3} for all positive integers nn.

In proving a sum formula, what do you add to the assumed ∑r=1k\sum_{r=1}^{k}?

Divisibility

Show f(1)f(1) is divisible by mm, assume f(k)f(k) is, then write f(k+1)f(k+1) using f(k)f(k).

To prove f(n)f(n) is divisible by mm: show f(1)f(1) is divisible by mm, assume f(k)=m×integerf(k)=m\times\text{integer}, and then express f(k+1)f(k+1) using f(k)f(k).

Look for f(k+1)−a f(k)f(k+1)-a\,f(k) where aa is chosen to cancel the power; the remainder should be a constant multiple of mm.

  1. 1

    Basis

    show f(1) is divisible by m

  2. 2

    Assume

    f(k) = m × integer

  3. 3

    Step

    write f(k+1) − a f(k) to cancel the power; the remainder is a multiple of m

  4. 4

    Conclude

    true for n = 1, and for k+1 whenever true for k, so true for all positive integers n

The divisibility induction method
  • f(k+1)−9f(k)f(k+1)-9f(k)constant multiple of mm

Worked example

Prove that f(n)=32n+1+1f(n)=3^{2n+1}+1 is divisible by 44.

For f(k)=5k−1f(k)=5^k-1 divisible by 4, what is f(k+1)−5f(k)f(k+1)-5f(k)?

General terms of a sequence

Substitute the assumed formula for uku_k into the recurrence to get uk+1u_{k+1}.

If a sequence is defined by un+1=g(un)u_{n+1}=g(u_n) with u1u_1 given, a formula for unu_n is proved by induction.

The step always substitutes the assumed formula for uku_k in the recurrence.

  1. 1

    Basis

    check the formula against u1u_1

  2. 2

    Assume

    uku_k equals the formula

  3. 3

    Step

    put it into uk+1=g(uk)u_{k+1}=g(u_k)

  4. 4

    Conclude

    formula holds for n=k+1n=k+1

Proving a formula for a sequence

Worked example

un+1=3un+4u_{n+1}=3u_n+4 with u1=1u_1=1. Prove that un=3n−2u_n=3^n-2.

For un+1=2un+1u_{n+1}=2u_n+1 with u1=1u_1=1, what is unu_n claimed to be if un=2n−1u_n=2^n-1 at n=1n=1?

Matrix powers

Write Ak+1=AkA\mathbf A^{k+1}=\mathbf A^k\mathbf A and multiply, showing all four entries.

For a 2×22\times2 matrix A\mathbf A, a formula for An\mathbf A^n is proved by writing Ak+1=AkA\mathbf A^{k+1}=\mathbf A^k\mathbf A and multiplying.

Always show all four entries, and compare with the formula with nn replaced by k+1k+1.

OPQR(4, 1)(3, 1)
The unit square and its image under A³, a shear x → x + 3y (A = [[1,1],[0,1]])
  • Ak+1\mathbf A^{k+1}AkA\mathbf A^k\mathbf A

Worked example

A=(1101)\mathbf A=\begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix}. Prove that An=(1n01)\mathbf A^n=\begin{pmatrix} 1 & n \\ 0 & 1 \end{pmatrix}.

In the matrix induction step, which product do you evaluate?

Try an exam question

Prove by induction that ∑r=1nr2=n(n+1)(2n+1)6\sum_{r=1}^{n}r^2=\frac{n(n+1)(2n+1)}{6} for all positive integers nn.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

In the inductive step, the student assumes that the result is true for n=kn=k. What must the student then show?

1 mark, marked against the mark scheme

Revision notes