What is your favorite elegant/beautiful mathematical proof?

[bonanova]

Someone observed that a good trivia question links the familiar with the obsucure: a little-known fact regarding a familiar subject or vice-versa. Simple proofs of difficult conjectures exhibit a similar attractiveness, bordering on beauty. This forum is for sharing proofs that are beautiful to you.

My fav is the proof, using two colors, that the power set possesses a higher cardinality: has no bijection with the original set.
_________________
_{Vidi, vici, veni.}

[Trojan Horse]

The Bolzano-Weierstrass Theorem: every infinite sequence of real numbers has an infinite subsequence that is monotone (either nondecreasing or nonincreasing).

It's also known as the Spanish Hotel Theorem, due to proof #2 on this webpage.

I loved the proof so much, I used it in one of my classes a couple of years ago.

[Jedo the Jedi]

My favorite proof hasn't been proven yet...at least I'm not aware that it has.
_________________
Paragon Tally: 18 mafia, 3 SKs (1 twice), 1 cultist, numerous chat scum...and counting.

[Quailman]

1=2

[Jack_Ian]

Take a square uniform grid of arbitrary size and remove opposite corners. Is it possible to fill the resultant shape with domino tiles where each tile is a rectangle exactly 2 squares long.
It's quite complex until you think of it as a Mutilated Chessboard Problem

Essentially, if alternate squares are coloured like a chessboard, then the removed squares are always of the same colour, leaving one colour having more squares than the other. A domino tile, when placed, will always cover a single black square and a single white square, so it can never fill the mutilated board.

So simple you could explain it to a four-year-old.

[groza528]

I kind of like the classic inductive reasoning problem: In how many ways can you fill a 2 x N rectangle using N dominoes?

[Zag]

I'm fond of the proof that there is no highest prime. Some of the reason I like this proof has nothing to do with the math, but with events in my life.

I had explained the proof to my son (who posts here as Zahariel), when he was five years old. A couple of months later we were visiting my in-laws and I was in the living room, chatting, when suddenly my father-in-law burst in. He exclaimed, "MY grandson is soooo smart -- he knows a proof that there is no highest prime number!" He went on to describe the proof, but what he described was totally incorrect, badly confused.

I kept my mouth shut (thanks to previous painful experience) but later that day asked my son to describe the proof to me. He had it exactly correct.

[Death Mage]

Quail's got it almost right. The best proof is 1%=2 proof.
_________________
* These senseless ramblings brought to you by Insanity™. If you just can't figure the dang thing out, it must be Insanity™.
[YOUR AD HERE!]

[extro...*]

1) Godel's first incompleteness theorem.

2) Undecidability of the Halting Problem

3) Any recursively enumerable set of axioms in first order logic is equivalent to some recursive set. (equivalent in the sense that the same theorems can be derived)

[The Potter]

[Nsof]

proofs
- Irrationality of sqrt(2)
- Infinitude of primes
- Cantour's diagonalization (mentioned by bonanova)
- Halting problem (mentioned by extro. there is something similar between this and Godel's incompleteness theorem. i.e. finding a function, plugging it into itself and then watch it break down)
- Cook's theorem

like because of the result
- Green's theorem
- e^iT=1. (where T=2*PI)

[extro...*]

[Dented Ford]

1 = true
0 = false

[referee]

I like the proof that the sum of combinatorial numbers (n 0) + (n 1) + ... + (n n) equals 2^n, because the final step is the more elegant ever: 1 + 1 = 2.
_________________
Jan 21st, 2008: The pillaging continues.
Mar 4th, 2008: Rest in Peace, Gary Gygax. May your dice always roll a natural 20 wherever you are.

Be the Ultimate Ninja! Play Billy Vs. SNAKEMAN today!

[Zag]

From the post in extro's thread about proofs, I started looking into proofs surrounding perfect numbers, and now I want to add Theorem of Even Perfect Numbers to this list. What a pretty proof! Part of what I liked about it was that I understood it in the amount of time I was willing to give to it -- about 10 minutes -- a crucial element that has evaded me for a few of the proofs others have posted here.

[Amb]

[Thok]

[referee]

Also the proof that when an inhabitant of the island of Knights and Knaves say "If I am a knight, then X", then we know for sure that he is a knight, and X is true. It's like a triple loop!
_________________
Jan 21st, 2008: The pillaging continues.
Mar 4th, 2008: Rest in Peace, Gary Gygax. May your dice always roll a natural 20 wherever you are.

Be the Ultimate Ninja! Play Billy Vs. SNAKEMAN today!

[extropalopakettle]

The Pólya conjecture is that for any natural number n, there are at least as many natural numbers <n with an odd number of prime factors as with an even number (repeated prime factors are counted, so 8 has 3 prime factors, 2*2*2).

Proved false. Proof: 906,150,257 (the smallest counterexample)

[Nsof]

[Zag]

That went so far over my head that I didn't even feel inclined to duck.

[extropalopakettle]

[Nsof]

[esme]

[extropalopakettle]

[Zag]

[Thok]

A proof that e is irrational:

Recall e = 1/0! +1/1! +1/2! +1/3! +....

Suppose e=p/q, for some integer q which we can assume is >0. Then e(q!) = p(q-1)! is an integer.

e(q!) = (q!/0!+q!/1!+...+q!/q!)+q!/(q+1)!+q!/(q+2)!+...

Now e(q!) is an integer, and so is (q!/0!+q!/1!+...+q!/q!). Therefore so is the difference e(q!)-(q!/0!+q!/1!+...+q!/q!) = q!/(q+1)!+q!/(q+2)!+...
= 1/(q+1)+1/(q+1)(q+2)+1/(q+1)(q+2)(q+3)+....

But the last expression is strictly bigger than 0, and it is strictly less than 1/2+1/2*1/2+1/2*1/2*1/2+... =1/2+1/4+1/8+... = 1. So it is an integer between 0 and 1, which is impossible. Hence one can not express e as p/q, aka e is not a rational number.

[Zag]

I'll buy that you proved the number defined by

x = 1/0! +1/1! +1/2! +1/3! +....

is irrational, but you haven't proved that it equals e (that is, the number for which the derivative of (it raised to the x) is the same value)

(e ^x ) ^d / _dx = e ^x

[Thok]

Fair enough. Proving e^x=1/0!+x/1!+x^2/2!+x^3/3!+... as functions isn't that much harder (the power series converges everywhere by the ratio test, equals it's own derivative, and equals e^x at x = 0, but verifying that taking derivatives of an absolutely convergent power series can be done term by term or that there is a unique function equal to its own derivative with f(0)=1 is starting to get on the long side). Then you can just plug in x = 1 on both sides.

Part of the point is that the proof that e is irrational is relatively accessible, especially compared to the proof that pi is irrational.

[bonanova]

A geometrical conjecture can be proved by simple physics: the points of tangency of a non-planar quadrilateral to a sphere are coplanar.

Place a point mass on each vertex of the quadrangle with value inversely proportional to the distance to its two associated points of tangency [they are equal] and the pairwise centers of mass at the ends of each side will be at the points of tangency. The center of mass of all four masses can be the combination of either of two different pairwise cm's. The four points describe two lines that intersect, and are thus coplanar. There is a geometrical proof as well.

BTW, the power set cardinality proof in post 1 is not the diagonal proof mentioned in post 11 but one that uses colors:

Assume a 1-1 correspondence of the elements of a set with its subsets has been established. Color an element blue if it's a member of its paired subset and red otherwise. The red elements comprise a subset that by definition cannot be paired with either a blue or a red element. Thus the power set has higher cardinality.
_________________
_{Vidi, vici, veni.}

[Nsof]

[esme]

It is even easier to prove that 1/e is irrational instead, because the tail estimate for an alternating series is just the next term instead of a majorisation with a geometric series.
_________________
Mundus vult decipi, ergo decipiatur.