Lesson 4 of 7 · 18 min

Proving divisibility by induction

Prove that an expression is divisible by a given integer for every positive integer n, by writing the assumption as an equation with an integer multiple and substituting it.

What you will be able to do

  • Write "divisible by mm" as an equation: f(k)=mMf(k) = mM for some M∈ZM \in \mathbb{Z}.
  • Rewrite f(k+1)f(k + 1) so the assumption can be substituted, then factor out mm.
  • Prove divisibility results involving one power, a polynomial, or two different powers.

Work out 7n−17^n - 1 for the first few values of nn and divide each by 66:

7n−17^n - 1 is a multiple of 66 every time.
nn7n−17^n - 1÷ 6\div\, 6
116611
22484888
333423425757
4424002400400400
5516 80616\,80628012801

Five cases are evidence, not proof. To prove that 7n−17^n - 1 is divisible by 66 for every positive integer nn, you need induction, and the key is to turn "divisible by 66" into something you can calculate with.

Definition

Divisible

An integer aa is divisible by a non-zero integer mm when a=mMa = mM for some integer MM.

So "7k−17^k - 1 is divisible by 66" means 7k−1=6M7^k - 1 = 6M for some M∈ZM \in \mathbb{Z}, which rearranges to 7k=6M+17^k = 6M + 1. Note that 0=m×00 = m \times 0 is divisible by every mm.

In the inductive step, use the index laws to bring in the power from the assumption: 7k+1=7×7k7^{k+1} = 7 \times 7^k. Then substitute 7k=6M+17^k = 6M + 1 and factor out 66. Step through the same method on another statement first.

Interactive

Prove 5n+35^n + 3 is divisible by 44

The table shows 5n+35^n + 3 for the first few values of nn: 8,28,128,628,…8, 28, 128, 628, \ldots, each a multiple of 44.

Worked example

Prove 7n−17^n - 1 is divisible by 66

  • Simple familiar
  • Technology free

Prove by mathematical induction that 7n−17^n - 1 is divisible by 66 for all n∈Z+n \in \mathbb{Z}^+.

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Write the assumption as an equation, f(k)=mMf(k) = mM with M∈ZM \in \mathbb{Z}.

  2. Use index laws to write f(k+1)f(k+1) in terms of the power in f(k)f(k).

  3. Substitute the assumption.

  4. Factor out mm and say why the other factor is an integer.

Watch out for

  • Writing the assumption as 7k−1=6k7^k - 1 = 6k. The multiplier is an unknown integer MM, not kk.

  • Stopping at 42M+642M + 6 without factoring out 66 and saying that the bracket is an integer.

Substitute for the power

From the assumption, 7k=6M+17^k = 6M + 1:

7k+1−1=7×7k−1=7(6M+1)−1=42M+6=6(7M+1)7^{k+1} - 1 = 7 \times 7^k - 1 = 7(6M + 1) - 1 = 42M + 6 = 6(7M + 1)

Split off the old expression

Add and subtract to make 7k−17^k - 1 appear:

7k+1−1=7(7k−1)+7−1=7(6M)+6=6(7M+1)7^{k+1} - 1 = 7\left(7^k - 1\right) + 7 - 1 = 7(6M) + 6 = 6(7M + 1)

In a proof that 5n−15^n - 1 is divisible by 44, the assumption is 5k−1=4M5^k - 1 = 4M for some M∈ZM \in \mathbb{Z}. Express 5k+1−15^{k+1} - 1 in terms of MM.

5 k+1 - 1 =
Reads asYour answer shows here as maths.

When the expression is a polynomial in nn, there is no index law to use. Expand the expression for k+1k + 1 instead, and look for the expression from the assumption inside it.

Worked example

Prove n3+2nn^3 + 2n is divisible by 33

  • Complex familiar
  • Technology free

Prove by mathematical induction that n3+2nn^3 + 2n is divisible by 33 for all n∈Z+n \in \mathbb{Z}^+.

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Expand the expression for k+1k + 1.

  2. Group the terms that make up the expression for kk, and replace them by mMmM.

  3. Factor out mm from what is left and say why the bracket is an integer.

Watch out for

  • Expanding (k+1)3(k + 1)^3 as k3+1k^3 + 1. It is k3+3k2+3k+1k^3 + 3k^2 + 3k + 1.

  • Not grouping k3+2kk^3 + 2k together, so the assumption never gets used.

To prove that n3−nn^3 - n is divisible by 33, you need (k+1)3−(k+1)(k + 1)^3 - (k + 1) in terms of k3−kk^3 - k. Expand and simplify (k+1)3−(k+1)−(k3−k)(k + 1)^3 - (k + 1) - \left(k^3 - k\right).

Reads asYour answer shows here as maths.

With two different powers, such as 32n+4−22n3^{2n+4} - 2^{2n}, write each power for k+1k + 1 as a number times the power for kk. Then substitute for one of them using the assumption; the other power should combine into a multiple of the divisor.

Worked example

Prove 32n+4−22n3^{2n+4} - 2^{2n} is divisible by 55

  • Complex unfamiliar
  • Technology free

Prove by mathematical induction that 32n+4−22n3^{2n+4} - 2^{2n} is divisible by 55 for all n∈Z+n \in \mathbb{Z}^+.

6 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Rewrite each power for k+1k + 1 as a number times the power for kk.

  2. Replace one power using the assumption.

  3. Collect the other power: its coefficient should be a multiple of the divisor.

  4. Factor out the divisor and say why the bracket is an integer.

Watch out for

  • Writing 32(k+1)+43^{2(k+1)+4} as 32k+53^{2k+5}. The 22 multiplies all of k+1k + 1, so the power rises by 22.

  • Trying to substitute for both powers at once. Replace one and the other combines into a multiple of the divisor.

Which expression equals 32(k+1)−13^{2(k+1)} - 1?

Choose one answer

Common mistake

Common errors in divisibility proofs

  • Using kk as the multiplier. "7k−1=6k7^k - 1 = 6k" is false for k≥2k \geq 2. The multiplier is an unknown integer, MM.
  • Index law slips. 7k+1=7×7k7^{k+1} = 7 \times 7^k, not 7k+77^k + 7.
  • Stopping too early. 42M+642M + 6 is not the end. Factor out 66 and say why the bracket is an integer.

Exam tip

Say why the bracket is an integer

State the domain of MM in the assumption ("for some M∈ZM \in \mathbb{Z}"). After factoring, say why the other factor is an integer: "since MM and kk are integers, M+k2+k+1M + k^2 + k + 1 is an integer". That sentence is what turns the algebra into a divisibility argument.

Summary

  • Write the assumption as an equation: f(k)=mMf(k) = mM, M∈ZM \in \mathbb{Z}.

  • With powers, use ak+1=a×aka^{k+1} = a \times a^k, substitute the assumption, then factor out mm.

  • With polynomials, expand the expression for k+1k + 1 and group the expression from the assumption.

  • With two different powers, substitute for one; the other should combine into a multiple of mm.

  • Finish by saying why the remaining factor is an integer, then write the conclusion.

Finished the lesson?

Try the 3 quick checks above and the lesson completes itself, or mark it complete now.

Lesson 4 of 70% read

Save your progress with a free account