Proof by mathematical induction

Proof by mathematical induction

Spec 1.1 · Edexcel A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • Induction has four parts: basis (P(1)P(1) true), assumption (P(k)P(k) true), inductive step (P(k+1)P(k+1) true using P(k)P(k)) and conclusion.
  • For a sum, the inductive step adds the next term: ∑r=1k+1ur=∑r=1kur+uk+1\sum_{r=1}^{k+1}u_r=\sum_{r=1}^{k}u_r+u_{k+1}, then factorise.
  • For divisibility, show f(k+1)−f(k)\mathrm{f}(k+1)-\mathrm{f}(k) is a multiple of dd, or substitute the assumed form.
  • For matrix powers, test n=1n=1, then calculate Mk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M} and check every entry.
  • The full conclusion names the basis, the implication and the range of nn.

The structure of a proof

Induction proves P(n) for every positive integer n: show it is true for n = 1, then that truth for k forces truth for k + 1.

Each of the four parts earns marks. The basis substitutes n=1n=1 into both sides. The assumption is that P(k)P(k) is true for some positive integer kk. The inductive step must use the assumption; proving P(k+1)P(k+1) from scratch is not induction.

  1. 1

    Basis

    show P(1)P(1) is true

  2. 2

    Assumption

    assume P(k)P(k) is true

  3. 3

    Inductive step

    show P(k+1)P(k+1) is true using P(k)P(k)

  4. 4

    Conclusion

    true for all positive integers nn

The four parts of an induction proof

Which part of the proof is missing if you only show that P(k)P(k) true implies P(k+1)P(k+1) true?

Summation of series

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

The same method proves ∑r3=14n2(n+1)2\sum r^3=\frac14n^2(n+1)^2: add (k+1)3(k+1)^3 and factorise out 14(k+1)2\frac14(k+1)^2 to get 14(k+1)2(k+2)2\frac14(k+1)^2(k+2)^2.

0.511.522.533.544.555.550100150200250nsum1936100225¼n²(n+1)²
Σr³ from 1 to n equals ¼n²(n+1)²: values 1, 9, 36, 100, 225.
  • Sum to k+1k+1 terms∑r=1kur+uk+1\sum_{r=1}^{k}u_r+u_{k+1}

Worked example

Prove ∑r=1nr(r+1)=n(n+1)(n+2)3\sum_{r=1}^{n}r(r+1)=\frac{n(n+1)(n+2)}{3}.

Going from kk to k+1k+1 terms in ∑r3\sum r^3, which term do you add?

Divisibility

Show f(1) is a multiple of d, assume f(k) is a multiple, then write f(k+1) as a multiple of d.

Two reliable routes: form f(k+1)−f(k)\mathrm{f}(k+1)-\mathrm{f}(k) (or f(k+1)−a f(k)\mathrm{f}(k+1)-a\,\mathrm{f}(k)) and show it is a multiple of dd; or substitute the assumed form, e.g. 7k=6m−57^k=6m-5, directly into f(k+1)\mathrm{f}(k+1).

  1. 1

    Basis

    f(1)\mathrm{f}(1) is a multiple of dd

  2. 2

    Assume

    f(k)=dm\mathrm{f}(k)=dm

  3. 3

    Difference

    f(k+1)−f(k)\mathrm{f}(k+1)-\mathrm{f}(k) is a multiple of dd

  4. 4

    Conclude

    f(k+1)\mathrm{f}(k+1) is a sum of two multiples of dd

Proving divisibility by d

Worked example

Prove that f(n)=32n+11\mathrm{f}(n)=3^{2n}+11 is divisible by 4.

If f(k+1)−f(k)\mathrm{f}(k+1)-\mathrm{f}(k) is a multiple of dd and f(k)\mathrm{f}(k) is a multiple of dd, what follows?

Powers of matrices

Test n = 1, assume the formula for k, then calculate M^k M and match every entry to the formula with k + 1.

Matrix multiplication is not commutative in general, but MkM=MMk\mathbf{M}^k\mathbf{M}=\mathbf{M}\mathbf{M}^k, so either order is acceptable here.

  1. 1

    Basis

    formula at n = 1 equals M

  2. 2

    Assume true for n = k

  3. 3

    Step

    M^(k+1) = M^k M, so the formula holds for k + 1

  4. 4

    Conclusion

    true for all positive integers n

Induction for matrix powers.
  • Basisformula at n=1n=1 equals M\mathbf{M}
  • StepMk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}

Worked example

For M=(3−41−1)\mathbf{M}=\begin{pmatrix}3&-4\\1&-1\end{pmatrix}, prove Mn=(2n+1−4nn1−2n)\mathbf{M}^n=\begin{pmatrix}2n+1&-4n\\ n&1-2n\end{pmatrix}.

What must the formula give when n=1n=1?

Writing the conclusion

A mark is awarded for naming the basis, the implication and the range of n.

A model sentence: 'The statement is true for n=1n=1, and if it is true for n=kn=k then it is true for n=k+1n=k+1. Therefore it is true for all positive integers nn by mathematical induction.'

In a 'show that' step, write the expression for k+1k+1, substitute the assumption, simplify, and state that this is the required form. If the question starts from n=0n=0 or another value, use that as the basis and amend the final sentence.

  1. 1

    Name the basis

    true for n = 1

  2. 2

    Name the implication

    true for n = k gives true for n = k + 1

  3. 3

    State the conclusion

    true for all positive integers n by mathematical induction

The structure of an induction conclusion.

Full conclusion

  • Names the basis
  • Names the implication
  • States all positive integers n

Not enough

  • 'So it is true for all n.'
  • 'Hence proved.'
  • No mention of the basis

Which conclusion earns the mark?

Try an exam question

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

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

What is the value of each side of the identity when n=1n=1?

1 mark, marked against the mark scheme

Revision notes