**Book method and my method**

For the step 2 of the proofs by induction that f(n) is divisible by some number m for all n, the textbook says you should always start by working out f(k+1)−f(k).

If f(k+1)−f(k) = something obviously divisible by m

then you’re done. *If* f(k) is divisible by m, *then* f(k+1) must be too, which is exactly what you want to prove in step 2.

The trouble with the book method is that quite often

f(k+1)−f(k) is *not* something *obviously* divisible by m

so you still need to do the “anti-simplifying” on the right-hand side to get

f(k+1)−f(k) = [something]×f(k) + something else obviously divisible by m

Working from f(k+1)−f(k) rather than directly from f(k+1) is just a pointless detour.

**Better method**

At the start of Step 2, write what you want to prove: m | f(k+1)

And then write: True for n=k ⇒ m | f(k)

**If you can add something divisible by m to f(k) to get f(k+1) (or something like it), do so.**

(These are the cases where the book method would work ok, but I think it is less hocus-pocus, and easier to see what you’re doing, if you write it out as in this example:)

To prove: 7 | 8^{k+1}−1

True for n=k ⇒ 7 | 8^{k}−1

⇒ 7 | 8^{k}+7×8^{k}−1

⇒ 7 | 8^{k}×8−1

⇒ 7 | 8^{k+1}−1 ▇

Or this example:

To prove: 5 | (k+1)^{5}−1

True for n=k ⇒ 5 | k^{5}−k

⇒ 5 | k^{5}+5k^{4}+10k^{3}+10k^{2}+5k−k

(you need to know what (k+1)^{5} multiplied out is to do this, but then it’s not unreasonable that you need to know what (k+1)^{5} multiplied out is in order to prove something about it)

⇒ 5 | (k+1)^{5}−1−k

⇒ 5 | (k+1)^{5}−(k+1) ▇

**If you can’t easily add something divisible by to f(k) to get something like f(k+1), then multiply f(k) by whatever number makes it into something like f(k+1). Example:**

To prove: 7 | 13^{k+1}−6^{k+1}

True for n=k ⇒ 7 | 13^{k}−6^{k}

⇒ 7 | 13×(13^{k})−13×(6^{k})

(Now fiddle around with the right-hand side to get *exactly* f(k+1))

⇒ 7 | 13×(13^{k})−6×(6^{k})−7×(6^{k})

(And if the thing you’re trying to prove is true, which it is, you’ll get on the right hand side f(k+1) plus or minus something *obviously* divisible by m

⇒ 7 | 13^{k+1}−6^{k+1}−7×(6^{k})

⇒ 7 | 13^{k+1})−6^{k+1} ▇

Another example:

To prove: 8 | 5^{2(k+1)+1}−3^{2(k+1)+1}

True for n=k ⇒ 8 | 5^{2k+1}−3^{2k+1}

⇒ 8 | 5×(5^{2k+1})−5×(3^{2k+1})

⇒ 8 | 5^{2(k+1)+1}−3×(3^{2k+1})+8×(3^{2k+1})

⇒ 8 | 5^{2(k+1)+1}−(3^{2(k+1)+1})+8×(3^{2k+1})

⇒ 8 | 5^{2(k+1)+1}−(3^{2(k+1)+1}) ▇

**Better ways to prove divisibility**

Don’t use these in the exam, or Edexcel will give you zero marks. But you want to learn real maths as well as how to jump Edexcel hurdles, don’t you?

**One:** x^{n}−y^{n} is divisible by x−y, for all n.

Proof: If x=y then x^{n}−y^{n}=0. Therefore (x−y) is a factor of x^{n}−y^{n}. ▇

**Two:** x^{2n−1}+y^{2n−1} is divisible by x+y, for all n.

Proof: If x=−y then x^{2n−1}+y^{2n−1}=0. Therefore (x+y) is a factor of x^{2n−1}+y^{2n−1}. ▇

**Three:** (2n+1)×(4m−1)^{n}−1 is divisible by 4 for all n.

(The example like this which you’ve come across, because it was used in a past paper, had m=2, so it was (2n+1)×7^{n}−1 being divisible by 4. By luck the book method works quite neatly with this type).

Proof: (4m−1)^{n} = terms with 4m, (4m)^{2}, (4m)^{3}, and so on in them… + 1 (if n even)… or −1 (if n odd)

Therefore (2n+1)×(4m−1)^{n} = terms divisible by 4… +2n+1 if n even… or −2n−1 if n odd

Therefore (2n+1)×(4m−1)^{n}−1 = terms divisible by 4… +2n if n even… or −2n−2 if n odd

Either way, (2n+1)×(4m−1)^{n}−1 = terms divisible by 4 plus 2×(an even number).

Therefore it is divisible by 4. ▇

**Four:** n^{p}−n is divisible by p for all n, so long as p is a prime number.

(This is actually a very important mathematical result, called Fermat’s little theorem).

Proof: Imagine n different colours of beads. Make necklaces of length p with those beads. For each position on the necklace, there are n choices of bead-colour, so there are n^{p} possible necklaces.

n of the necklaces are all-same-colour-bead necklaces.

Because the length of each necklace, p, is a prime number, it is impossible for any sub-sequence of colours to be repeated an exact number of times in any of the other (not all-same-colour-bead) necklaces.

The other n^{p}−n necklaces (the ones not all-same-colour-bead) can be collected into groups, each group being defined by a particular circle of beads and then all the p different choices of starting point round the circle. Each group contains p necklaces, all looking the same except that a different bead is named as “starting point”.

Therefore n^{p}−n is a multiple of p. ▇