Different methods in divisibility proofs

divisibilityRules

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 | 8k+1−1

True for n=k ⇒ 7 | 8k−1

⇒ 7 | 8k+7×8k−1

⇒ 7 | 8k×8−1

⇒ 7 | 8k+1−1  ▇

Or this example:

To prove: 5 | (k+1)5−1

True for n=k ⇒ 5 | k5−k

⇒ 5 | k5+5k4+10k3+10k2+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 | 13k+1−6k+1

True for n=k ⇒ 7 | 13k−6k

⇒ 7 | 13×(13k)−13×(6k)

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

⇒ 7 | 13×(13k)−6×(6k)−7×(6k)

(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 | 13k+1−6k+1−7×(6k)

⇒ 7 | 13k+1)−6k+1  ▇

Another example:

To prove: 8 | 52(k+1)+1−32(k+1)+1

True for n=k ⇒ 8 | 52k+1−32k+1

⇒ 8 | 5×(52k+1)−5×(32k+1)

⇒ 8 | 52(k+1)+1−3×(32k+1)+8×(32k+1)

⇒ 8 | 52(k+1)+1−(32(k+1)+1)+8×(32k+1)

⇒ 8 | 52(k+1)+1−(32(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: xn−yn is divisible by x−y, for all n.

Proof: If x=y then xn−yn=0. Therefore (x−y) is a factor of xn−yn.  ▇

Two: x2n−1+y2n−1 is divisible by x+y, for all n.

Proof: If x=−y then x2n−1+y2n−1=0. Therefore (x+y) is a factor of x2n−1+y2n−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)×7n−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: np−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).

necklace

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 np 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 np−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 np−n is a multiple of p.  ▇