Favourite Proofs

pickslides · #1 $Old$ October 21st, 2009, 05:26 PM

I have decided to make a thread that everyone can come to and post their favourite proof(s).

I have always found them interesting regardless which branch of Mathematics they belong to.

My favourite proof is:

Prove $1+2+3+\dots+(n-2) +(n-1)+n = \frac{n(n+1)}{2}$

I know this can be done using induction but I prefer a more unorthodox method shown by Euler.

Firstly we make

$1+2+3+\dots+(n-2)+(n-1)+n = S$ lets call it (1)

Then taking the expression on the left hand side and reversing the order we get

$n+(n-1)+(n-2)+\dots+3+2+1 = S$ lets call that (2)

Now adding (1) + (2) term by term we get

$\underbrace{(n+1)+(n+1) +\dots+(n+1) +(n+1)}_{\text{n times}} = 2S$

therefore

$n(n+1) = 2S$

and finally

$S = \frac{n(n+1)}{2} \Rightarrow 1+2+3+\dots+(n-2) +(n-1)+n = \frac{n(n+1)}{2}$

QED

Please post your favourite proofs

Bruno J. · #2 $Old$ October 24th, 2009, 05:55 PM

The proof you gave is due to Gauss, not Euler. The story says he was 8 years old when he came up with it!

Here is an even less orthodox method, due to myself. It's much longer!

First we take the geometric series

$1+x+x^2+...+x^n=\frac{x^{n+1}-1}{x-1}$

and differentiate both sides :

$1+2x+3x^2+...+nx^{n-1}=\frac{(n+1)x^{n}(x-1)-(x^{n+1}-1)}{(x-1)^2}$

and we take the limit of both sides as $x\rightarrow 1$ , applying de l'Hôpital's rule twice on the right side, and (after some very messy calculations) we get

$1+2+...+n=\frac{n(n+1)}{2}$ .

I'd love to see somebody prove it in an even more indirect way! Gauss's proof is much better, the above is just for fun.

Another proof is by Pascal's triangle. It's easy to prove that ${n \choose j} = \frac{n!}{j!(n-j)!}$ , and that ${n+1 \choose 2} = 1+2+...+n$ . So

$1+2+...+n = {n+1 \choose 2} = \frac{(n+1)!}{2!(n-1)!} = \frac{n(n+1)}{2}$ .

Prove It · #3 $Old$ October 24th, 2009, 09:06 PM

Here is one of my favourite proofs - the proof that $\sqrt{2}$ is irrational. It is a favourite of mine because of its superb use of logic.

Before I do this though, first it is necessary to prove that if the square of a number is even, then the number must have been even.

Using the contrapositive, this statement is the same as it is necessary to prove that if a number is odd, then its square is odd.

Define an odd number $x = 2n + 1$ .

Proof:

$x^2 = (2n + 1)^2$

$= 4n^2 + 4n + 1$

$= 2(2n^2 + 2n) + 1$ , another odd number.

Since the square of any odd number is odd, this implies that if the square of a number is even, the number must have been even.

Q.E.D.

Assume that $\sqrt{2}$ is rational.

All rational numbers can be written of the form $\frac{a}{b}$ , where $a$ and $b$ are integers. All rational numbers can also be reduced to its simplest form, where there are not any common factors between $a$ and $b$ .

So since we are assuming that $\sqrt{2}$ is rational, we will assume it can be written as an irreducible fraction of integers $\frac{a}{b}$ .

Proof:

$\sqrt{2} = \frac{a}{b}$

$2 = \left(\frac{a}{b}\right)^2$

$2 = \frac{a^2}{b^2}$

$a^2 = 2b^2$ .

This means that $a^2$ is even, and thus $a$ is even.

So we will write $a = 2c$ .

$(2c)^2 = 2b^2$

$4c^2 = 2b^2$

$b^2 = 2c^2$ .

This means that $b^2$ is even, and thus $b$ is even.

But since $a$ and $b$ are both even, there is a common factor of $2$ , which means this fraction is reducible.

This contradicts our original statement that would allow $\sqrt{2}$ to be rational.

Thus $\sqrt{2}$ is IRRATIONAL.

Q.E.D.

Another favourite of mine is the proof that there are infinitely many prime numbers, once again because of the sheer brilliance of the logic that is used.

Proof:

Assume that there are a finite number of prime numbers. Therefore there would be some number $P$ which is the largest prime number.

Let us define a number $N$ as the product of all the known primes.

So $N = 2 \times 3 \times 5 \times 7 \times 11 \times \dots \times P$ .

Adding $1$ to this number gives

$N + 1 = 2 \times 3 \times 5 \times 7 \times 11 \times \dots \times P + 1$ .

Notice that if you were to divide $N + 1$ by any of the prime numbers, you will have a remainder of $1$ .

Therefore there must either be some prime number $> P$ which is a factor of $N + 1$ , or $N + 1$ is itself a prime number.

Either way, this contradicts the statement that $P$ is the largest prime number.

Therefore, there are infinitely many prime numbers.

Q.E.D.

Chris L T521 · #4 $Old$ October 24th, 2009, 10:17 PM

One of my favorites (as of late) deals with the insolvability of degree 5 or higher polynomials.

Thm: A general polynomial of degree five or more cannot be solved using radicals.

Proof:

Let $f\!\left(x\right)$ be a general polynomial. Then $f\!\left(x\right)$ is solvable using radicals if its Galois Group is solvable.

Since the Galois group of $f\!\left(x\right)$ is $S_n$ , we see that $\forall\,\deg f\!\left(x\right)\geq 5,\,A_5\subset S_n$ .

Since $A_5$ is not solvable, then it follows that $S_n$ (the Galois Group) is not solvable, which now implies $f\!\left(x\right)$ cannot be solved by using radicals $.\qquad\square$

This proof is beautiful in the fact that its pretty short and sweet! This theorem applies to a polynomial over any field!! However, to fully understand the proof, you need many theorems and lemmas to get to this elegant result.

CaptainBlack · #5 $Old$ October 25th, 2009, 01:07 AM

Quote:

Originally Posted by Prove It $View Post$

Here is one of my favourite proofs - the proof that $\sqrt{2}$ is irrational. It is a favourite of mine because of its superb use of logic.

The proof of this that I like is that from the rational roots theorem.

If $x^2-2$ has a rational root it is $\pm 2$ . Direct checking shows that neither of these is a root, so $x^2-2$ has no (real) rational roots hence since Descartes rule of signs tell us that this does have one positive and one negative root, these must be irrational.

CB

jmoney90 · #6 $Old$ November 4th, 2009, 03:36 PM

I like the proof of Euler's Formula involving Taylor series. I think it's really clever

pickslides · #7 $Old$ November 4th, 2009, 06:04 PM

Quote:

Originally Posted by jmoney90 $View Post$

I like the proof of Euler's Formula involving Taylor series. I think it's really clever

Which one is that?

Prove It · #8 $Old$ November 4th, 2009, 07:07 PM

Quote:

Originally Posted by jmoney90 $View Post$

I like the proof of Euler's Formula involving Taylor series. I think it's really clever

I prefer using direct calculus...

Let $z = \cos{x} + i\sin{x}$ .

It is also important to note that when $x = 0, z = 1$ .

Then

$\frac{dz}{dx} = -\sin{x} + i\cos{x}$

$= i^2\sin{x} + i\cos{x}$

$= i(\cos{x} + i\sin{x})$

$= iz$ .

So $\frac{dz}{dx} = iz$ .

Rearranging and integrating gives

$\frac{1}{z}\,\frac{dz}{dx} = i$

$\int{\frac{1}{z}\,\frac{dz}{dx}\,dx} = \int{i\,dx}$

$\int{\frac{1}{z}\,dz} = ix + C_1$

$\ln{|z|} + C_2 = ix + C_1$

$\ln{|z|} = ix + C$ , where $C = C_1 - C_2$

$|z| = e^{ix + C}$

$|z| = e^Ce^{ix}$

$z = \pm e^C e^{ix}$

$z = Ae^{ix}$ .

Now to find the constant, recall that when $x = 0, z = 1$ .

So

$1 = Ae^{0i}$

$A = 1$ .

Therefore

$z = e^{ix}$ .

Thus this proves Euler's Formula:

$z = \cos{x} + i\sin{x} = e^{ix}$ .

jmoney90 · #9 $Old$ November 4th, 2009, 09:47 PM

Quote:

Originally Posted by pickslides $View Post$

Which one is that?

I originally saw it in this video. I don't have enough posts to post a video but youtube euler's identity taylor series

It's a bit flashy and you can skip the first half, but the second half contains what I think is the most simple proof of a deep result that I can actually understand lol.

Deadstar · #10 $Old$ November 5th, 2009, 09:22 AM

Quote:

Originally Posted by Bruno J. $View Post$

The proof you gave is due to Gauss, not Euler. The story says he was 8 years old when he came up with it!

Here is an even less orthodox method, due to myself. It's much longer!

First we take the geometric series

$1+x+x^2+...+x^n=\frac{x^{n+1}-1}{x-1}$

and differentiate both sides :

$1+2x+3x^2+...+nx^{n-1}=\frac{(n+1)x^{n}(x-1)-(x^{n+1}-1)}{(x-1)^2}$

and we take the limit of both sides as $x\rightarrow 1$ , applying de l'Hôpital's rule twice on the right side, and (after some very messy calculations) we get

$1+2+...+n=\frac{n(n+1)}{2}$ .

I'd love to see somebody prove it in an even more indirect way! Gauss's proof is much better, the above is just for fun.

Another proof is by Pascal's triangle. It's easy to prove that ${n \choose j} = \frac{n!}{j!(n-j)!}$ , and that ${n+1 \choose 2} = 1+2+...+n$ . So

$1+2+...+n = {n+1 \choose 2} = \frac{(n+1)!}{2!(n-1)!} = \frac{n(n+1)}{2}$ .

We could probably fill this whole thread with proofs of $1 + 2 + \ldots + n = \frac{n(n+1)}{2}$ ...

Here's one I thought of after reading this thread.

Think of the graph of y=x. Notice that the area under the part x=0 to x=1 is 0.5,
the part from x=1 to x=2 is 1.5,
x=2 to x=3 is 2.5, etc...
This differs from the 1+2+3+...+n sequence by 0.5.

So! Change the graph to be y=x+0.5 and now from x=0 to x=1 you have area 1, x=1 to x=2 have area 2 etc...
Which now matches our sequence!
If you integrate this from 0 to n you will get...

$1 + 2 + \ldots + n = \int_0^1 x+0.5 dx + \int_1^2 x+0.5 dx + \ldots + \int_{n-1}^n x+0.5 dx = \int_0^n x + 0.5 dx =$ $\bigg{[}\frac{x^2}{2} + \frac{x}{2}\bigg{]}_0^n = \bigg{[}\frac{x(x+1)}{2}\bigg{]}_0^n = \frac{n(n+1)}{2}$ .

Don't know if I've explained this too well but hopefully you'll see where I'm coming from!

jmoney90 · #11 $Old$ November 5th, 2009, 04:24 PM

Quote:

Originally Posted by Deadstar $View Post$

We could probably fill this whole thread with proofs of $1 + 2 + \ldots + n = \frac{n(n+1)}{2}$ ...

Here's one I thought of after reading this thread.

Think of the graph of y=x. Notice that the area under the part x=0 to x=1 is 0.5,
the part from x=1 to x=2 is 1.5,
x=2 to x=3 is 2.5, etc...
This differs from the 1+2+3+...+n sequence by 0.5.

So! Change the graph to be y=x+0.5 and now from x=0 to x=1 you have area 1, x=1 to x=2 have area 2 etc...
Which now matches our sequence!
If you integrate this from 0 to n you will get...

$1 + 2 + \ldots + n = \int_0^1 x+0.5 dx + \int_1^2 x+0.5 dx + \ldots + \int_{n-1}^n x+0.5 dx = \int_0^n x + 0.5 dx =$ $\bigg{[}\frac{x^2}{2} + \frac{x}{2}\bigg{]}_0^n = \bigg{[}\frac{x(x+1)}{2}\bigg{]}_0^n = \frac{n(n+1)}{2}$ .

Don't know if I've explained this too well but hopefully you'll see where I'm coming from!

Ooh, that's clever! I like it

Focus · #12 $Old$ November 10th, 2009, 05:57 PM

Brownian motion is nowhere differentiable a.e.

For fixed t by normality we have
$\mathbb{P}\left \{\frac{B_{t+\frac{1}{n}}-B_t}{\frac{1}{n}}-x\leq \frac{1}{n}\right \}\leq C\frac{1}{n^2}$
where C is a constant (easy computation). As the sum of these probabilities (over n) is bdd, and this holds for each x, it follows that
$\sum \mathbb{P}\left \{\inf_{x\in\mathbb{R}}\frac{B_{t+\frac{1}{n}}-B_t}{\frac{1}{n}}-x\leq \frac{1}{n}\right \}<\infty$
and applying the Borel-Cantelli lemma gives the desired result.