Nonstandard proofs for simple theorems

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Nonstandard proofs for simple theorems

In an upcoming assignment I have to prove that the sum of consecutive squares is n(n+1)(2n+1)/6. The problem is definitely below the difficulty level of the course so I'd like to have some fun and present an uncommon proof of it. The two common ones I'm familiar with are by induction and summing (n+1)3 - n3. You're encouraged to share any other nonstandard proofs as well.

phlip
Restorer of Worlds
Posts: 7521
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Nonstandard proofs for simple theorems

Consider a 1x1x1 cube stacked on top of the rear-left quarter of a 2x2x1 cuboid, which is stacked on top of the rear-left corner of a 3x3x1 cuboid, etc, up to nxnx1. Stacked such that the heights of each point, viewed from above, should be:

Code: Select all

n...321..  321. . 321.  .321333332122222211111111

The volume of this shape is the sum we're looking for.

Now, this shape resembles a square pyramid - so consider a pyramid, with an n*n base at the bottom of the shape, and apex at the top in the rear-left corner. This pyramid has volume 1/3 n3. Also, the pyramid is contained entirely within our shape, so to find the volume of the shape, we just need to see what pieces of our shape protrude from that pyramid. Those pieces are: on the front and right sides of the shape, the "steps" up the shape all protrude out. There are n(n-1)/2 1x1x1 cubes on the front and n(n-1)/2 1x1x1 cubes on the right, each of which have half their volume protruding from the pyramid (they're cut in half along the diagonal by the side of the pyramid). And then there are n 1x1x1 cubes up the corner of the stairs, which each have a small pyramid-shaped piece removed, so they have 2/3 of their volume protruding from the pyramid.

Adding up all these volumes, we get that the total volume of the shape is n3/3 + n(n-1)/2 + 2n/3 - expanding these and simplifying shows it's equal to n(n+1)(2n+1)/6.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Nonstandard proofs for simple theorems

What would constitute a *simple* proof?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

Re: Nonstandard proofs for simple theorems

(I assume that other theorem are allowed here.)

How about Fürstenberg's proof of the infinitude of primes?

http://en.wikipedia.org/wiki/F%C3%BCrst ... _of_primes

(or http://www.cut-the-knot.org/proofs/Furstenberg.shtml , since Wikipedia is going away in a day or so.)

Qaanol
The Cheshirest Catamount
Posts: 2991
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Nonstandard proofs for simple theorems

I like the proof by decomposition into triangular numbers. It’s really a proof by picture, and works best when drawn visually, but I hope I can convey it in text.

By inspection we note that, for n>1, a grid of squares n×n (like a checkerboard) can be split into two “triangular” pieces, by cutting along a “staircase” next to the main diagonal. That is, you get one piece of (1+2+3+⋯+(n-1)+n) and one piece of (1+2+3+⋯+(n-1)). Those have, respectively, (n+1 Choose 2) and (n Choose 2) squares in them. For n=1 of course the formula for the larger triangle holds, and the smaller “triangle” simply has zero squares.

We can think of this n×n grid as being extruded into the third dimension, so it is made of blocks, each a little cube, still laid out in a square. We can then think putting the n-square on the ground, stacking the (n-1) square on top of it, the (n-2) square on top of that, and on up to the 1-square, a single block at the top of a pyramid.

Each layer of the pyramid decomposes into triangles, of size (k+1 Choose 2) and (k Choose 2), except the top layer which just has (1+1 Choose 2) = 1 block.

We can then stack up the larger triangles from each layer, to form a tetrahedron of base n, and the smaller triangles to form a second tetrahedron, of base n-1. Those tetrahedra have block-counts, respectively, [imath]\sum_{i=2}^{n+1}{i \choose 2}[/imath] and [imath]\sum_{i=2}^n{i\choose 2}[/imath].

By basic properties of Pascal’s triangle, however, the sum of the first m entries along a diagonal equals the entry on the next diagonal in, one row down from the last of the summed values. Since the entries along the jth diagonal of Pascal’s triangle are just the values of r-choose-j, that means [imath]\sum_{r=j}^{m}{r\choose j} = {m+1\choose j+1}[/imath].

For the case at hand, we get from this [imath]\sum_{i=2}^{n+1}{i\choose 2} = {n+2 \choose 3}[/imath] and [imath]\sum_{i=2}^n{i\choose 2} = {n+1 \choose 3}[/imath]. Adding these together for the total we want, of course, gives (n+2)(n+1)(n)/6 + (n+1)(n)(n-1)/6 = n(n+1)(2n+1)/6.
wee free kings

antonfire
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Nonstandard proofs for simple theorems

A fairly similar proof to the above is to note that n(n-1)(n-2)/6 = 0 + 0 + 1 + 3 + 6 + ... + (n-1)(n-2)/2. (This is easy to see by looking at n = 0, 1, 2, 3.) When the sum has 2m terms, we can group them into pairs: 2m(2m-1)(2m-2)/6 = (0+0) + (1+3) + (6+10) + ... + ( (2m-2)(2m-3)/2 + (2m-1)(2m-2)/2 ) = 02 + 22 + 42 + ... + (2(m-1))2 = 4(02 + 12 + ... + (m-1)2).

So, 02 + 12 + ... + (m-1)2 = m(2m-1)(m-1)/6.

Combinatorially, rather than cutting each square into two triangles and getting two sums of m consecutive triangular numbers, we first subdivide each square so that the grid is twice as fine, then cut those squares into two triangles. This gives us just one sum of 2m consecutive triangular numbers.

If you're curious, I reverse-engineered this proof form the fact that the roots of g(m) = m(2m-1)(m-1)/6 are 0, 1/2, and 1. It suggests that g(n/2), whose roots are integers, has a sensible interpretation, which in turn suggests splitting each term in 02 + 12 + ... + (m-1)2 into two. If you intend to emphasize the point that there are usually lots of proofs of a given fact, saying a few words about this sort of reverse engineering might be worthwhile.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Nonstandard proofs for simple theorems

Also, I know that faulhaber's formula is a formula for the sums of squares, cubes, etc, but is there a general way to factorise the formulas? For simplicity let us call this formula (sum of the first x kth powers) fk(x), f1(x)=x(x+1)/2, f2(x)=x(x+1)(2x+1)/6, and so on, but is there a rule for the factors? And at f4(x), a quadratic term appears, so I shall call the largest (factor of highest degree) gk(x). g4(x)=3x2+3x-1, g5(x)=2x2+2x-1, g6(x)=3x4+6x3-3x+1 (correct me if I'm wrong but I don't think this has any nice factors), anyone have a formula for that? What are the roots of the functions?
Last edited by tomtom2357 on Tue Jan 17, 2012 7:43 am UTC, edited 1 time in total.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

dissonant
Posts: 63
Joined: Sat Jan 24, 2009 10:33 am UTC

Re: Nonstandard proofs for simple theorems

Here is a proof without words due to Man-Keung Sui, http://hkumath.hku.hk/~mks/, which demonstrates the result.

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Nonstandard proofs for simple theorems

That is a cool proof!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

antonfire
Posts: 1771
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Nonstandard proofs for simple theorems

tomtom2357 wrote:What are the roots of the functions?
I plotted these for the first fifty functions or so once. If I recall correctly, for high k, they seem to trace out a vaguely ellipse-shaped curve in the complex plane. At the time, I didn't know how to interpret this, and I suppose I still don't. It would be interesting to try to work out a limiting distribution of the roots (you might need to rescale, or it might not exist), and think about what that distribution says about these sums, Bernoulli numbers, and so on.

Something worth thinking about: if gk(x) were the characteristic polynomial of some sensible operator, the roots would be its eigenvalues, which gives you a tool with which to analyze them.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Nonstandard proofs for simple theorems

At what point do the roots become complex?
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

dissonant
Posts: 63
Joined: Sat Jan 24, 2009 10:33 am UTC

Re: Nonstandard proofs for simple theorems

tomtom2357 wrote:At what point do the roots become complex?

Here is a hint.

http://en.wikipedia.org/wiki/Faulhaber's_formula
http://www.wolframalpha.com

fishfry
Posts: 135
Joined: Wed Dec 21, 2011 6:25 am UTC

Re: Nonstandard proofs for simple theorems

If you calculate a Riemann sum of x^2 over [0,1] by partitioning the unit interval into n equally spaced segments, the formula for the sum of the first n squares shows up.

I was hoping to use this to find a clever proof starting from the integral and working back to the sum formula, but I don't really see how to do it. Still, it's fun to see how the Riemann sums for x^2 reduce to the formula for the sum of the first n squares, and likewise the Riemann sums for x^n reduce to the formula for the first n n-th powers.

Qaanol
The Cheshirest Catamount
Posts: 2991
Joined: Sat May 09, 2009 11:55 pm UTC

Re: Nonstandard proofs for simple theorems

It may be of interest to note that the dot-product of the nth row (counting from 1) of the Eulerian number triangle, with a length-n section of the nth diagonal (counting from 0) of Pascal’s triangle beginning at row r (counting from 0), equals rⁿ. We take the stance that Pascal’s triangle is surrounded by 0’s going off to the left and right, so any values from “outside” the triangle are zeros.

By applying the same procedure to the (n+1)st diagonal of Pascal’s triangle beginning on row (r+1), we get the sum of the nth powers from 1 through r, that is 1ⁿ+2ⁿ+⋯+rⁿ. Conceptually, this means splitting the n-dimensional hypercube of side length r into several n-dimensional “pyramids” of side lengths n, n-1, n-2, …, n-(r-1).

Since it is simple to sum generalized triangular numbers (simplectic numbers?) by going one row down and one diagonal inward on Pascal’s triangle, this makes the calculation straightforward. The only tricky part is knowing how many simplices of each side-length to use. For the n=2 case, it is one of each, and involves merely splitting a square number into two triangular numbers as I described above.

Pascal’s triangle:
Spoiler:
$\begin{array}{ccccccccccccc} &&&&&&& \,1 &&&&&&& \,\\ &&&&&& \,1 && \,1 &&&&&& \,\\ &&&&& \,1 && \,2 && \,1 &&&&& \,\\ &&&& \,1 && \,3 && \,3 && \,1 &&&& \,\\ &&& \,1 && \,4 && \,6 && \,4 && \,1 &&& \,\\ && \,1 && \,5 && 10 && 10 && \,5 && \,1 && \,\\ &1 && \,6 && 15 && 20 && 15 && \,6 && \,1 & \\ ⋰ &&&&&&& ⋮ &&&&&&& ⋱ \\ \end{array}$

Eulerian number triangle:
Spoiler:
$\begin{array}{ccccccccccccc} &&&&&&& \;\;\;1 &&&&&&& \\ &&&&&& \;\;\;1 && \;\;\;1 &&&&&& \\ &&&&& \;\;\;1 && \;\;\;4 && \;\;\;1 &&&&& \\ &&&& \;\;\;1 && \;\;11 && \;\;11 && \;\;\;1 &&&& \\ &&& \;\;\;1 && \;\;26 && \;\;66 && \;\;26 && \;\;\;1 &&& \\ && \;\;\;1 && \;\;57 && \;302 && \;302 && \;\;57 && \;\;\;1 && \\ & \;\;\;1 && \;120 && 1191 && 2416 && 1191 && \;120 && \;\;\;1 & \\ \;\;\;⋰ &&&&&&& ⋮ &&&&&&& \;\;\;⋱ \\ \end{array}$

By way of example, to find the sum of the cubes from 1 to n, we look at the 3rd row of the Eulerian number triangle, which is “1, 4, 1”, and we look at the 4th diagonal of Pascal’s triangle, which begins with “1, 5, 15”. Now for any three consecutive entries on that diagonal, say on rows r+1, r+2, and r+3, their values are (r+1 Choose 4), (r+2 Choose 4), and (r+3 Choose 4), where we define (a Choose b) = 0 when 0≤a<b. Dotting those with the Eulerian entries gives [imath]1\cdot{{r+1} \choose 4} + 4\cdot{{r+2} \choose 4} + 1\cdot{{r+3} \choose 4}[/imath]. Expanding that out gives the appropriate Faulhaber polynomial, and we see,

$1\cdot{{r+1} \choose 4} + 4\cdot{{r+2} \choose 4} + 1\cdot{{r+3} \choose 4} = \sum_{i=1}^{r}i^3$

To prove this works, it is sufficient to show that [imath]1\cdot{r\choose 3} + 4\cdot{{r+1} \choose 3} + 1\cdot{{r+2} \choose 3} = r^3[/imath]. And that is straightforward to prove, just by expanding and simplifying. Pascal’s triangle and the formulæ for summing its diagonals take care of the rest.

The recursive rule for the Eulerian number triangle is similar to that for Pascal’s triangle. Calling the two entries above a given entry its “parents”, in Pascal’s triangle you just add the parents together for the value of the child. With the Eulerian number triangle, you first multiply each parent by the index of the diagonal it and the child are both on (counting from 1). That is, the edge diagonals have index 1, the next diagonals in have index 2, then 3 and so forth. So the child of 57 and 302 is 5•57+3•302=1191.

If we want the sum of the cubes from 1 to 3, we have 1•1 + 4•5 + 1•15 = 36 = 1+8+27. If we want the sum of the cubes from 1 to 10, we have 1•(11×10×9×8)/24 + 4•(12×11×10×9)/24 + 1•(13×12×11×10)/24 = (55)(6+36+13) = 55². Of course, we could’ve gotten those particular result more quickly by noting [imath]\sum_{i=1}^{n}i^3 = \left(\sum_{i=1}^{n}i\right)^2 = n^2(n+1)^2/4[/imath]. That, incidentally, has a neat visual proof of its own.

By looking at cubes made of unit-cube blocks, we can slice the n×n×n cube into n square of n×n each. Those squares can be arranged in an “L” pattern. If n is odd then the length of the legs of the L are equal, and if n is even then the last square is cut in half into two rectangles, one of which goes to each leg of the L so the legs of the L are still equal. Those L grids nest together, and when you put the L’s from i=1,2,3,…,n together, they fit perfectly to make a square of side length 1+2+3+⋯+n.

Finally, I apologize for all the “counting from 0” and “counting from 1” stuff. It seems the standard practice for numbering Pascal’s triangle’s entries is 0-based, and for the Eulerian number triangle is 1-based. I followed both those conventions, and I hope it was not too confusing.
wee free kings

skeptical scientist
closed-minded spiritualist
Posts: 6139
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Nonstandard proofs for simple theorems

Proginoskes wrote:(I assume that other theorem are allowed here.)

How about Fürstenberg's proof of the infinitude of primes?

http://en.wikipedia.org/wiki/F%C3%BCrst ... _of_primes

(or http://www.cut-the-knot.org/proofs/Furstenberg.shtml , since Wikipedia is going away in a day or so.)

Here's another proof that there are infinitely many primes, using ideas of compression. The basic idea is if there were only n primes, we could use prime factorization to compress every k-bit string into n log(k+1) bits, violating the pigeonhole principle.
Spoiler:
Suppose p1...pn are the only primes. Let f: N -> Nn be the function mapping a natural number to the exponents in its prime factorization. Clearly f is injective. If x≤2k, then every component of f(x) is at most k, so f|[1,2k] is an injective function from a set of size 2k into the set [0,k]n of size (k+1)n.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Nonstandard proofs for simple theorems

antonfire wrote:
tomtom2357 wrote:What are the roots of the functions?
I plotted these for the first fifty functions or so once. If I recall correctly, for high k, they seem to trace out a vaguely ellipse-shaped curve in the complex plane. At the time, I didn't know how to interpret this, and I suppose I still don't. It would be interesting to try to work out a limiting distribution of the roots (you might need to rescale, or it might not exist), and think about what that distribution says about these sums, Bernoulli numbers, and so on.

Interesting, an ellipse is formed, I wonder why. Also, I figured out how to circumvent the wikipedia blackout! You go to the page, but as soon as the page comes up, you stop the loading of the page, and the blackout screen never comes up!
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Posts: 1
Joined: Wed Jan 18, 2012 2:59 pm UTC

Re: Nonstandard proofs for simple theorems

Blatm wrote:In an upcoming assignment I have to prove that the sum of consecutive squares is n(n+1)(2n+1)/6.

The book "Concrete Mathematics" by Knuth/Patashnik/Graham has about 10 neat different proofs for this, so maybe you should have a look at it.
I'll add my personal weird proof (very sloppily written and all, but it can also be done rigorous, just that the fun is then lost to me):

Let D be the differentiation operator and look at what the operator e^D (defined as a taylor series, e^D=id+D+D^2 /2!...) does to functions:
(e^D)x=x+1
(e^D)x^2=x^2+2x+1=(x+1)^2
and so forth. Obviously this holds for all polynomials, and a lot of functions can be expanded into polynomials. Hence e^D takes f(x) to f(x+1).

if we want to sum f(1)+f(2)+...+f(n) then that is obviously equivalent to [1+e^D+e^(2D)+...+e^((n-1)D)]*f(1) (be careful with the n-1)
We interpret this new operator as a geometric series with common factor e^D and hence use the common result for geometric series

e^(nD)-id..............1...............................1
----------- * f(1) = ----------*(e^(nD)*f(1)-f(1)) =--------*(f(n+1)-f(1))
e^D-id...............e^D-id.........................e^D-id

Now recall the taylor expansion of (e^x-1)^-1 and just transer it over to the (e^D-1)^-1 case and you get:

Now you just use f(x)=x^2 and determine all the terms, noticing that there are not infinitely many of them as the third derivative is already zero (hence we have exact summation). Once you have all the terms, you can factorise them to get the desired result (n)(n+1)(2n+1)/6. Also, you now have a formula to sum any f(x)=x^integer, approximate sums with integrals and correction terms, know where the bernoulli numbers come from etc.. hence a lot of motivation to look into similar matters.

Sorry for the horrible typesetting. Also, if you want a nicer derivation, look up "Street-Fighting Mathematics" by Sanjoy (freely, legally available online as pdf).

Xanthir
My HERO!!!
Posts: 5058
Joined: Tue Feb 20, 2007 12:49 am UTC
Contact:

Re: Nonstandard proofs for simple theorems

skeptical scientist wrote:Here's another proof that there are infinitely many primes, using ideas of compression. The basic idea is if there were only n primes, we could use prime factorization to compress every k-bit string into n log(k+1) bits, violating the pigeonhole principle.
Spoiler:
Suppose p1...pn are the only primes. Let f: N -> Nn be the function mapping a natural number to the exponents in its prime factorization. Clearly f is injective. If x≤2k, then every component of f(x) is at most k, so f|[1,2k] is an injective function from a set of size 2k into the set [0,k]n of size (k+1)n.

That one is really awesome. I love it!
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))

Blatm
Posts: 638
Joined: Mon Jun 04, 2007 1:43 am UTC

Re: Nonstandard proofs for simple theorems

This is a really neat trick. Thanks very much.

skeptical scientist
closed-minded spiritualist
Posts: 6139
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

Re: Nonstandard proofs for simple theorems

Xanthir wrote:
skeptical scientist wrote:Here's another proof that there are infinitely many primes, using ideas of compression. The basic idea is if there were only n primes, we could use prime factorization to compress every k-bit string into n log(k+1) bits, violating the pigeonhole principle.
Spoiler:
Suppose p1...pn are the only primes. Let f: N -> Nn be the function mapping a natural number to the exponents in its prime factorization. Clearly f is injective. If x≤2k, then every component of f(x) is at most k, so f|[1,2k] is an injective function from a set of size 2k into the set [0,k]n of size (k+1)n.

That one is really awesome. I love it!

I seem to recall there being a way to use this idea to get rather close to the prime number theorem, maybe proving that π(n)≥n/log2 n (rather than n/loge n), but I can't seem to remember how it went.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Nonstandard proofs for simple theorems

I have a nonstandard proof that pi/4=sum(-1n/(2n+1), n>=0), it goes as follows: Let f(x)={-1 if -pi<x<=0, 1 if 0<x<=pi}, f(x+2*pi)=f(x), now the Fourier series of f(x)=(4/pi)*sum(sin((2n+1)*x)/2n+1, n>=0). Now, (4/pi)*sum(sin((2n+1)*(pi/2))/2n+1, n>=0)=f(pi/2)=1, so pi/4=sum(sin((2n+1)*(pi/2)), n>=0)=sum(-1n/(2n+1), n>=0), QED.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Nonstandard proofs for simple theorems

I'm pretty sure that's one of the standard proofs. Or at least, this is the proof that I'm familiar with, as opposed to the one on wiki using the integral form of arctan.

LaserGuy
Posts: 4207
Joined: Thu Jan 15, 2009 5:33 pm UTC

Re: Nonstandard proofs for simple theorems

I'm not sure how non-standard it is, but I like this little proof for Euler's formula, rather than the Taylor series one that is typically shown to freshmen students:

Let f(x) = cos(x) + isin(x)
Note that f(0) = 1

Then df/dx = -sin(x) + icos(x)
df/dx = i(cos(x) + isin(x)) = if(x)
df/f = idx
ln f = ix + C
f(x) = Ce^(ix)

From BC we get

f(x) = e^(ix) and therefore e^(ix) = cos(x) + isin(x)

phlip
Restorer of Worlds
Posts: 7521
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Nonstandard proofs for simple theorems

I remember one I read in another thread on here a while back: A proof that the nth-root of 2 is irrational for n>2:

Say there was a p/q, p and q both integers, such that (p/q)n = 2. Then:
pn/qn = 2
pn = 2qn
qn + qn = pn
However, this violates Fermat's Last Theorem, and thus has no solutions.

The proof of the statement for n=2 is left as an exercise for the reader.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Nonstandard proofs for simple theorems

phlip wrote:I remember one I read in another thread on here a while back: A proof that the nth-root of 2 is irrational for n>2:

Say there was a p/q, p and q both integers, such that (p/q)n = 2. Then:
pn/qn = 2
pn = 2qn
qn + qn = pn
However, this violates Fermat's Last Theorem, and thus has no solutions.

The proof of the statement for n=2 is left as an exercise for the reader.

This is possibly a circular proof, because fermat's last theorem could rely on this
Last edited by tomtom2357 on Tue Feb 21, 2012 11:17 am UTC, edited 1 time in total.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.

phlip
Restorer of Worlds
Posts: 7521
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Nonstandard proofs for simple theorems

Regardless - even if the proof of Fermat's Last Theorem relies on that fact at some point, which is entirely possible, it's still a valid proof. It's just one that's redundant, as it's proving something you'd need to already have accepted in order to accept the premises of the proof.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Hopper
Posts: 8
Joined: Thu Nov 01, 2007 1:13 am UTC

Re: Nonstandard proofs for simple theorems

tomtom2357 wrote:This is possibly a circular proof, because fermat's last theorem could rely on this

It almost certainly does not. Though I'm pretty sure it uses the fact that the integers are integrally closed, which immediately implies nth roots of 2 are irrational.

gfauxpas
Posts: 97
Joined: Sun Oct 09, 2011 11:24 pm UTC
Contact:

Re: Nonstandard proofs for simple theorems

Hopper wrote:
tomtom2357 wrote:This is possibly a circular proof, because fermat's last theorem could rely on this

It almost certainly does not. Though I'm pretty sure it uses the fact that the integers are integrally closed, which immediately implies nth roots of 2 are irrational.

Maybe Fermat's proof relied on it (if he had one).

Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Nonstandard proofs for simple theorems

You only need one proof to not rely on it for it to be a non-circular argument.

z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Nonstandard proofs for simple theorems

Another proof that there are infinitely many primes:

Spoiler:
$\sum_{n=1}^\infty \frac{1}{n^2} = \prod_{\mbox{all primes p}} \bigg(1 - \frac{1}{p^2}\bigg)^{-1}$ by Euler. If there were only finitely many primes, the RHS would be rational, but the LHS is [imath]\pi^2/6[/imath], which is irrational.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

Meteoric
Posts: 264
Joined: Wed Nov 23, 2011 4:43 am UTC

Re: Nonstandard proofs for simple theorems

The sum of the interior angles of an N-gon is 180(N-2). This is usually (?) proven by showing that an N-gon can be cut into N-2 triangles, each containing 180 degrees.

A while back, I was tutoring a geometry student, and she was working on problems like these without knowing the theorem (and thus, fumbling blindly). I offered, "What if we cut the polygon into triangles?" but before I could draw a diagram to illustrate, she drew the triangles in the pentagon she was working with. However, unlike the "normal" method which would cut the pentagon into 3 triangles, she cut it into 5 triangles, with their vertices meeting in the middle like the spokes of a wheel. I was about to correct her when I realized this was a slight variation of the same proof: an N-gon forms N triangles, totaling 180N degrees, but then you need to subtract away the central angles, which total to 360. 180N-360 is of course the same as the usual 180(N-2), distributed through.

Probably less interesting than most of this thread, but a 7th-grader invented it, which I thought was pretty impressive
No, even in theory, you cannot build a rocket more massive than the visible universe.

phlip
Restorer of Worlds
Posts: 7521
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: Nonstandard proofs for simple theorems

Huh, I'd never heard of either of those proofs... though when you said "divided into triangles", I thought of the wheel layout first. However, I'll say that the wheel layout will only work directly if the polygon is a star-convex set - ie you can find a centre point such that all the vertices can connect to that centre point with a straight line that stays inside the shape. Whereas the other triangulation will work regardless, as any polygon can be triangulated in that way.

The proof I've heard is to extend all the edges of the polygon in, let's say, the clockwise direction, so what we instead have is a bunch of rays going off to infinity. Now, the exterior angles between each pair of rays at each corner of our polygon, will add up to 360 degrees (you can slide them all inward so they're all at the same point, and they stay congruent, and clearly add up to 360). And the internal angle of each point is 180 minus the external angle. So the internal angles must add up to 180n - 360.
This one only works for convex polygons, though. But both this and the wheel one can be adapted with special cases for the bits that don't work... basically by allowing negative angles (eg for the external-angle proof, for instance if one of the angles is 200 degrees, you can say that the external angle is -20 degrees, and everything still adds up).

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

tomtom2357
Posts: 563
Joined: Tue Jul 27, 2010 8:48 am UTC

Re: Nonstandard proofs for simple theorems

I discovered (on http://en.wikipedia.org/wiki/Mersenne_prime) a non-standard proof of the infinitude of the prime numbers:
Using the fact that any factor of 2p-1 (for prime p) is of the form 2kp+1, every factor of 2p-1 must be bigger than p, therefore for every prime p, there is a prime greater than p.
I have discovered a truly marvelous proof of this, which this margin is too narrow to contain.