Induction for divisibility and matrix powers

Induction for divisibility and matrix powers

Spec A1 · AQA A-Level Further Maths: Revision notes

Studying this course? Keep your progress in one place.

Key facts

  • For divisibility, write the hypothesis as an equation: f(k)=dmf(k)=dm for some integer mm.
  • The step must end with f(k+1)=d×(an integer expression)f(k+1)=d\times(\text{an integer expression}).
  • Two methods: the difference f(k+1)−f(k)f(k+1)-f(k), or substituting for the power using the hypothesis.
  • For matrices, assume Mk\mathbf{M}^k equals the formula, then use Mk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M} and check every entry.
  • Never drop the full conclusion: basis, P(k)⇒P(k+1)P(k)\Rightarrow P(k+1), so true for all positive integers nn.

Setting up divisibility

Write the hypothesis as an equation with an unknown integer multiple, so you have something to substitute.

To prove f(n)f(n) is divisible by dd for all positive integers nn:

  • Basis: show f(1)f(1) is a multiple of dd.
  • Hypothesis: assume f(k)=dmf(k)=dm for some integer mm.
  • Step: show f(k+1)=d×(an integer expression)f(k+1)=d\times(\text{an integer expression}).

‘Assume f(k)f(k) is divisible by dd’ on its own gives you nothing to use. The multiple is an integer multiple, which may be any whole number.

  1. 1

    Basis

    f(1)f(1) is a multiple of dd

  2. 2

    Hypothesis

    f(k)=dmf(k)=dm, mm an integer

  3. 3

    Step

    f(k+1)=d×(integer expression)f(k+1)=d\times(\text{integer expression})

  4. 4

    Conclusion

    true for n=1n=1 and P(k)⇒P(k+1)P(k)\Rightarrow P(k+1), so true for all positive integers nn

Divisibility by induction

Assume f(k)=4k−1f(k)=4^k-1 is divisible by 33. Which hypothesis is correctly written?

Two ways to finish

Either show the difference f(k+1)−f(k)f(k+1)-f(k) is a multiple of dd, or substitute for the power from the hypothesis.

Method 1: the difference. Show f(k+1)−f(k)f(k+1)-f(k) is a multiple of dd. Then f(k+1)=dm+(multiple of d)f(k+1)=dm+(\text{multiple of }d).

Method 2: substitute. Rewrite the power using the hypothesis, for example 5k=4m−35^k=4m-3, so f(k+1)=5(4m−3)+3=4(5m−3)f(k+1)=5(4m-3)+3=4(5m-3).

Useful differences: 5k+1−5k=4×5k5^{k+1}-5^k=4\times5^k and 7k+1−7k=6×7k7^{k+1}-7^k=6\times7^k.

  1. 1

    Assume

    f(k)=dmf(k)=dm for some integer mm

  2. 2

    Method 1

    Show f(k+1)−f(k)f(k+1)-f(k) is a multiple of dd

  3. 3

    Method 2

    Substitute the power from the hypothesis

  4. 4

    Conclude

    f(k+1)=dimes(extinteger)f(k+1)=d imes( ext{integer})

The two ways to finish a divisibility induction step.

Difference

  • Find f(k+1)−f(k)f(k+1)-f(k)
  • Show it is a multiple of dd
  • Add to f(k)=dmf(k)=dm

Substitute

  • Rearrange the hypothesis for the power
  • Replace it in f(k+1)f(k+1)
  • Factorise out dd

Worked example

Prove that 7n−17^n-1 is divisible by 66 for all positive integers nn.

If 5k−1=4m5^k-1=4m, which expression equals 5k+1−15^{k+1}-1?

Polynomial expressions

Find f(k+1)−f(k)f(k+1)-f(k) and use the fact that the product of two consecutive integers is always even.

For g(n)=n3+11ng(n)=n^3+11n (divisible by 66): g(k+1)−g(k)=3k2+3k+12=3k(k+1)+12g(k+1)-g(k)=3k^2+3k+12=3k(k+1)+12.

The product k(k+1)k(k+1) of consecutive integers is always even, so k(k+1)=2jk(k+1)=2j and 3k(k+1)=6j3k(k+1)=6j.

Hence g(k+1)=6m+6j+12=6(m+j+2)g(k+1)=6m+6j+12=6(m+j+2).

State the reason k(k+1)k(k+1) is even: one of two consecutive integers is even.

05010015020025012123456ng(n)
Values of g(n) = n³ + 11n for n = 1 to 6: every one is a multiple of 6 (12 = 6×2, 30 = 6×5, 60 = 6×10, 108 = 6×18, 180 = 6×30, 276 = 6×46).
  • k(k+1)k(k+1)always even
  • g(k+1)−g(k)g(k+1)-g(k)3k(k+1)+123k(k+1)+12

Why is k(k+1)k(k+1) always even?

Powers of a matrix

Assume the formula for Mk\mathbf{M}^k, multiply by M\mathbf{M}, and show every entry matches the formula with n=k+1n=k+1.

To prove a formula for Mn\mathbf{M}^n, check n=1n=1, assume Mk\mathbf{M}^k equals the formula, then use Mk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M} and multiply the matrices.

Calculate M2\mathbf{M}^2 and M3\mathbf{M}^3 first to spot the pattern, then prove it. Show that every entry matches (for example 2k+2=2(k+1)2k+2=2(k+1)).

  1. 1

    Basis

    Check the formula gives M\mathbf{M} when n=1n=1

  2. 2

    Assume

    Mk\mathbf{M}^k equals the formula

  3. 3

    Multiply

    Mk+1=MkM\mathbf{M}^{k+1}=\mathbf{M}^k\mathbf{M}

  4. 4

    Match

    Every entry equals the formula with n=k+1n=k+1

Proving a formula for a matrix power by induction.
  • Mk+1\mathbf{M}^{k+1}Mk M\mathbf{M}^{k}\,\mathbf{M}

Worked example

M=(1201)\mathbf{M}=\begin{pmatrix}1&2\\ 0&1\end{pmatrix}. Prove that Mn=(12n01)\mathbf{M}^n=\begin{pmatrix}1&2n\\ 0&1\end{pmatrix}.

What is M2\mathbf{M}^2 for this matrix M\mathbf{M}?

Presenting the answer

Name the integer expression in a divisibility proof, match every matrix entry, and always give the full conclusion.

For divisibility, the last line must be f(k+1)=d×(integer)f(k+1)=d\times(\text{integer}), naming the integer expression.

For matrices, show that every entry matches the formula with n=k+1n=k+1 (for example 1+2(k+1)1+2(k+1), not just 3+2k3+2k).

Marks are lost for ‘so true for all nn’ without the basis and the inductive link.

  1. 1

    Basis step

    Show the result is true for n=1n=1

  2. 2

    Inductive step

    Name the integer expression, or match every entry

  3. 3

    Conclusion

    True for n=kn=k implies true for n=k+1n=k+1, so true for all positive integers nn

What the finished induction answer must contain.
  • Divisibility stepf(k+1)=d×(integer)f(k+1)=d\times(\text{integer})
  • Matrix stepevery entry matches n=k+1n=k+1

In a divisibility proof, what should the final line of the inductive step look like?

Try an exam question

Prove by induction that 5n+35^n+3 is divisible by 44 for all positive integers nn.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the value of f(3)f(3).

1 mark, marked against the mark scheme

Revision notes