Here is the proof for the A level style question puzzle. I am going to
talk about two approaches to this question which I enjoy. The first is proof by
induction and the second is modular arithmetic.
However, before we get on to those ideas we can make the puzzle simpler.
The expression n5-n can easily be factorised, by using the
differences of two squares as below.
n5-n = n(n4-1)
=n(n2+1)(n2-1)
=n(n+1)(n-1)(n2+1)
This already helps us a lot. We have to prove that expression always
divides by 30. Another way of doing that is proving that it always divides by
30’s prime factors, which are 2,3 and 5. This relies on composite numbers
having unique prime factorisation which we know is true. (That may be a good
topic for another post) In the expression n(n+1)(n-1)(n2+1) we have
three consecutive numbers making up terms. These are n-1 , n ,n+1. Every third
number divides by three and every second number divides by two. Therefore, if you
have a string of 3 consecutive number you know one of these will divide by three
and at least one will divide by two. This means the proof can now be reduced to
prove n5-n is divisible by 5.
Proof by Induction
Proof by induction is one of the most important tools in a mathematician’s
toolkit. The logical argument for a proof by induction is that if we
can prove something is true for all the numbers then it is true for the next
number n. if we have such an argument the fact it is true for the number 1
implies it is true for the numbers 1 and 2. Then the fact it is true for the
numbers 1 and 2 will imply it is true for the number 3 and so on indefinitely.
To conduct a proof by induction we need to prove two things: firstly, that the
assertion is true for the number 1 and secondly that if it is true for one it
is true for all integers. If we don’t have the first part the proof is not
valid, it is a strict if, then argument. We can then say the proof is true for all the
natural numbers.
Sadly, I couldn’t get the necessary symbols to type the proof up, so I have
provided a picture of my paper copy of the proof. I must first mention that the
notation, a|b, means that b divides into a and the arrow means if, then.
The first thing I did was establish f(1) was true. If you were wondering, strictly 5 does divide into 0, every number strictly does.
I then continue onto a lemma. This is pivotal because it tells us how to
get from f(n) to f(n+1) which we base the proof on. The statement f(n+1)-af(n)|5
(for some value a) is a standard result. It just means that f(n+1) take away
something times by f(n) will divide by 5. There will always be a value of a for this independent
of f(n). I then expand out the expression. On line 5 of the lemma I then
factorise the expression. This clearly shows that when a=6 f(n+1)-af(n)|5. We
can now move onto the main proof.
We are still working on an if, then statement so the proof goes if f(n)|5
then 6f(n)|5. This is allowed because, if a|b then xa|b for all integer values
of x. The third line down we can write from the lemma. Any number divisible by 5 add
another number divisible by 5 (which we got from the lemma) will still be
divisible by 5. This is generalised as if a|b and c|b then a+c|b. Clearly in
the proof the plus and minus 6f(n) cancel to leave the result, f(n+1) is divisible
by 5.
Therefore, we have proved the original statement that n5-n|30
for when n is a natural number.
Modular Arithmetic
At first modular arithmetic can seem quite an odd concept, but the range
of things we can solve using this way of thinking is remarkable. Modular arithmetic offers an alternative way
to look at our number system, instead of imagining numbers lying on a line, a
section of the number line is ‘rolled up’ to form a circle, much like a clock
face. Once the time reaches 12 o’clock, it becomes not 13 but 1 o’clock, and
continues around the cycle as before. Under this system, it could be said that
12 + 1 =13 is essentially the same as 1, or that both 2 + 48 = 50 and 4 + 10 =
14 are essentially the same as 2. In fact, many numbers could be said to be
essentially the same if the time of day doesn’t matter, If a number other than
12 is chosen, the same idea should follow, but the sets of equivalent numbers
are arranged differently. As shown below.
In mathematics this idea of many numbers occupying the same place on the
clock has been formalised and condensed into a more workable form by
introducing the concept of congruence
to take the place of numbers being effectively the same and naming the number
of hours on the clock as the modulus. I would encourage research on modular arithmetic, it can do some fascinating things but I will now explain its relevance to the
proof.
One law that arises from modular arithmetic is that, mod m, if two congruencies
of two different numbers are the same, when you take them away from each other
the result will always divide by m. Therefore, if we can show that n5 and
n are the same for 0,1,2,3,4,5, all the numbers up to 5 (mod 30) it proves that n5-n|5.
I produced the table below
r N5 n
0 0 0
1 1 1
2 2 2
3 3 3
4 4 4
5 5 5
Hence, we have now proved that n5-n|5. Therefore, we know
that n5-n|30
I hope you enjoyed that puzzle the next puzzle will be online soon. Thank you again for reading
I came to this page from Twitter link to your interview with Vicky Neale. There are some interesting things to read there! I’ll add a few comments on this post. Hope they’re useful! (I’ve had to post them as two separate comments as they’re too long to post as one comment!)
ReplyDeleteINDUCTION:
You're right to say that induction is pretty important. I've probably used it every day of my undergrad degree! You might want to be a little careful with how you phrase your description of how it works, though. Specifically, you've claimed that "The logical argument for a proof by induction is that if we can prove something is true for all the numbers then it is true for the next number n.” As written, that’s not quite right. Indeed, the point of an induction proof is to show that something is true for all the natural numbers n; so if we “can prove something is true for all the numbers” then we’re done already and no induction is needed!
A better way to describe how an induction proof works might be like this: We want to show a property holds for all the natural numbers. We find a way to show that (no matter which natural number n we choose), if the property holds for n, then it also holds for n+1. (This part of the proof is known as the inductive step.) Then we show that the property holds for a small value of n, say n=1. Since the property holds for n=1, and whenever it holds for n the property holds also for n+1, we conclude by induction that the property holds for all natural numbers.
If you want to spell out that last sentence, you might say something like:
“We have shown that the property is true for the number 1. The fact it’s true for 1 implies (by the inductive step) that it’s true also for 2. The fact that it’s true for 2 implies (by the inductive step) that it’s true also for 3… etc. So the property holds for all natural numbers.” (*)
It might be true in some sense that we use induction to show that “if it is true for one it is true for all integers”, but that description misses out the idea that induction works by showing that a property holds for all numbers because (it holds for n=1 and) whenever it holds for n it holds also for its successor n+1.
A remarkable thing about proving a statement like this is that you’re actually proving infinitely many different statements, one for each natural number. And yet you do this in one go, without using an infinite amount of paper. In the description marked (*) above, what we’re doing becomes obvious: the induction proof compresses the content of the ellipsis (“... etc.”) into the claim that a property holds for all natural numbers. The claim that induction is a valid form of proof might be thought of as the claim that this wrapping up all the claims in the “... etc.” constitutes a valid form of reasoning.
Come back to this after studying some set theory at university and you’ll probably feel this is to do with the fact that the natural numbers and induction are really two sides of the same coin: the natural numbers are exactly those objects reached immediately by induction.
Addendum: For clarity, I’ve described what’s known as ‘weak’ induction,, in which each inductive step proceeds from the truth of claim n to the truth of claim n+1. By contrast, a ‘strong’ form of induction proceeds in each inductive step from the truth of claims 1 through n to the truth of claim n+1. There’s no significant difference between these two forms.
(COMMENTS ON THE PROBLEM TO FOLLOW!)
THE PROBLEM:
ReplyDeleteWe want to show that the expression given is divisible by 30, for all natural numbers n. You rightly say that we can do this by showing that the expression is divisible by each of 2, 3, and 5. On the other hand (and this might have seemed too obvious to mention), this isn’t strictly immediate from the fact that 2, 3, 5 are the prime factors of 30. To see the point I’m trying to draw attention to, notice that it’s not enough to show that a number is divisible by 2 and 3 if we're trying to show it’s divisible by 12.
Finally, piggy-backing on your comments about modular arithmetic, here’s a shortcut that might be used to swiftly wrap up the problem. The factorization n(n-1)(n+1)(n^2+1) shows us immediately that the expression will be divisible by 2 and 3 (as you demonstrate well). It remains only to demonstrate divisibility by 5. Because of the terms n-1, n, and n+1, we know that the expression overall will be divisible by 5 when n is congruent to 1, 0, or 4 (mod 5). This means we only have to check the cases n=2 and n=3 (mod 5). And now we’re done, since then n^2+1 is either 2^2+1=5=0 (mod 5) or 3^2+1=10=0 (mod 5).
Keep up the good work!
Your comments are very helpful. I now see some steps I missed. Your comment has really clarified my knowledge of proof by induction.
DeleteThe point on modular arithmetic I was not aware of before, but now it seems so obvious. That is a helpful shortcut.
Thank you for your interest in my blog!