Two beautiful proofs

I'm currently in the middle of my annual summer re-read of GEB. It's such a great book and it teaches me something new every time I read it. One of the things I love about it is the regular forays into Number Theory and the occasional review of a classic proof.

So that got my thinking, what is my favourite Number Theory proof? Well, I couldn't decide, so you're going to get my two favourites.

They're from different ends of the spectrum, but they have one thing in common (like all good proofs). They take a problem that looks foreboding and offer up a solution that is so elegant and simple that it seems make you wonder why you were ever so puzzled.

Here's the first one:

Gauss' Sum of numbers from 1 to N

Gauss was an incredible mathematician and came up with many of the methods, proofs and theories that form the basis of modern mathematics. This particular proof is generally held to have been derived whilst Gauss was a mere scamp and still at school.

His teacher (feeling particularly lazy) had asked the boys in the class to add all of the numbers between 1 and 100, then write down the answer and bring it to him at his desk. When Gauss strolled up to the front after just a few minutes with a piece of paper reading 5050, the teacher was astonished (and daresay a little annoyed).

So how did Gauss do it? Well like all good mathematicians, Gauss generalised the problem and found a common solution, before applying his general solution to the initial question. In that lesson Gauss was able to fathom that the formula to tell you the sum, S(N), of the numbers between 1 and N was:

S(N) = (N/2)(N+1)

and that therefore the sum of numbers between 1 and 100 was:

S(100) = (100/2)(100+1) = 5050

The proof?

Take the numbers from 1 to N and pair them up against the numbers from N to 1. You'll notice that the sum of every pair is N+1 and that you have N pairs. So the sum of all the numbers in your two series is N(N+1). However, you doubled up your initial series, 1 to N, by pairing it up with N to 1 so you should divide this sum by two and you will have (N/2)(N+1).

Example:

                                                Sum
1 to 100:  1    2    3    4    5   ...  100     5050
100 to 1:  100  99   98   97   96  ...  1       5050
----------------------------------------------------------
Both:      101  101  101  101  101 ...  101     10100

I first saw Gauss' proof of that formula when I was at school and ever since it has remained one of mathematics little wonders to me. It felt like magic when I first saw it and it still does now.


The second result is a little more arcane, but the proof itself is no less magical than Gauss' above.

Cantor's Diagonal Proof

Cantor was a mathematician in the 19th century and he was really quite interested in infinite sets (to put it mildly...) He spent a lot of time trying to figure out a proper mathematical basis for infinity and in particular if their was more than one type of infinity.

He was able to definitively prove the existence of more than one infinity proving that there are fewer Natural Numbers (i.e. the numbers 1, 2, 3, 4, 5, ....) than there are Real Numbers (i.e. all numbers that can be represented by a decimal expansion like 0.1872459, 199.779, pi, e, ...), despite both sets clearly being infinite. His solution was ingenious and alarmingly simple.

First take all of the Real Numbers between 0 and 1 and map each of them to a Natural Number, hence:


R(1) = 0.13459872635...
R(2) = 0.23098175638...
R(3) = 0.58098903284...
R(4) = 0.98761834891...
....


(It is worth noting that the 'Reals' on the right must all be represented as their infinite decimal expansion).

Then he used this table to create a new number. From each of the original numbers he took the digit indexed by the Natural Number he had assigned to it (the bold ones from the diagram above):


T = 0.1306...


He then added 1 to each of these digits to obtain (cycling any 9's back round to 0):


T' = 0.2416...


Now, T' is definitely a Real between 0 and 1, but at the same time it can be seen that it does not correspond to any of the R(N) above, as:


The 1st digit is not the same as R(1)
The 2nd digit is not the same as R(2)
The 3rd digit is not the same as R(3)
...


So if we matched all of the Natural Numbers to a Real equivalent between 0 and 1 and found another Real that had not been matched then there must be more Reals between 0 and 1 than there are Natural Numbers. That is there must be an infinity that is bigger than the one you get by starting at 1 and counting up...


I love both of these proofs and I hope you enjoyed my (no doubt flawed) explanation of them. Do you love a different proof? Have a reason why these shouldn't be my top two? Let me know in the comments.