Nonstandard proofs for simple theorems
Moderators: gmalivuk, Moderators General, Prelates
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}  n^{3}. You're encouraged to share any other nonstandard proofs as well.
 phlip
 Restorer of Worlds
 Posts: 7453
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: Nonstandard proofs for simple theorems
How about geometrically?
Consider a 1x1x1 cube stacked on top of the rearleft quarter of a 2x2x1 cuboid, which is stacked on top of the rearleft corner of a 3x3x1 cuboid, etc, up to nxnx1. Stacked such that the heights of each point, viewed from above, should be:
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 rearleft corner. This pyramid has volume 1/3 n^{3}. 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(n1)/2 1x1x1 cubes on the front and n(n1)/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 pyramidshaped 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 n^{3}/3 + n(n1)/2 + 2n/3  expanding these and simplifying shows it's equal to n(n+1)(2n+1)/6.
Consider a 1x1x1 cube stacked on top of the rearleft quarter of a 2x2x1 cuboid, which is stacked on top of the rearleft 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
. .321
3333321
2222221
1111111
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 rearleft corner. This pyramid has volume 1/3 n^{3}. 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(n1)/2 1x1x1 cubes on the front and n(n1)/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 pyramidshaped 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 n^{3}/3 + n(n1)/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)⚠);}

 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.cuttheknot.org/proofs/Furstenberg.shtml , since Wikipedia is going away in a day or so.)
How about Fürstenberg's proof of the infinitude of primes?
http://en.wikipedia.org/wiki/F%C3%BCrst ... _of_primes
(or http://www.cuttheknot.org/proofs/Furstenberg.shtml , since Wikipedia is going away in a day or so.)
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+⋯+(n1)+n) and one piece of (1+2+3+⋯+(n1)). 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 nsquare on the ground, stacking the (n1) square on top of it, the (n2) square on top of that, and on up to the 1square, 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 n1. Those tetrahedra have blockcounts, respectively, \sum_{i=2}^{n+1}{i \choose 2} and \sum_{i=2}^n{i\choose 2}.
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 rchoosej, that means \sum_{r=j}^{m}{r\choose j} = {m+1\choose j+1}.
For the case at hand, we get from this \sum_{i=2}^{n+1}{i\choose 2} = {n+2 \choose 3} and \sum_{i=2}^n{i\choose 2} = {n+1 \choose 3}. Adding these together for the total we want, of course, gives (n+2)(n+1)(n)/6 + (n+1)(n)(n1)/6 = n(n+1)(2n+1)/6.
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+⋯+(n1)+n) and one piece of (1+2+3+⋯+(n1)). 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 nsquare on the ground, stacking the (n1) square on top of it, the (n2) square on top of that, and on up to the 1square, 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 n1. Those tetrahedra have blockcounts, respectively, \sum_{i=2}^{n+1}{i \choose 2} and \sum_{i=2}^n{i\choose 2}.
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 rchoosej, that means \sum_{r=j}^{m}{r\choose j} = {m+1\choose j+1}.
For the case at hand, we get from this \sum_{i=2}^{n+1}{i\choose 2} = {n+2 \choose 3} and \sum_{i=2}^n{i\choose 2} = {n+1 \choose 3}. Adding these together for the total we want, of course, gives (n+2)(n+1)(n)/6 + (n+1)(n)(n1)/6 = n(n+1)(2n+1)/6.
wee free kings
Re: Nonstandard proofs for simple theorems
A fairly similar proof to the above is to note that n(n1)(n2)/6 = 0 + 0 + 1 + 3 + 6 + ... + (n1)(n2)/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(2m1)(2m2)/6 = (0+0) + (1+3) + (6+10) + ... + ( (2m2)(2m3)/2 + (2m1)(2m2)/2 ) = 0^{2} + 2^{2} + 4^{2} + ... + (2(m1))^{2} = 4(0^{2} + 1^{2} + ... + (m1)^{2}).
So, 0^{2} + 1^{2} + ... + (m1)^{2} = m(2m1)(m1)/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 reverseengineered this proof form the fact that the roots of g(m) = m(2m1)(m1)/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 0^{2} + 1^{2} + ... + (m1)^{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.
So, 0^{2} + 1^{2} + ... + (m1)^{2} = m(2m1)(m1)/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 reverseengineered this proof form the fact that the roots of g(m) = m(2m1)(m1)/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 0^{2} + 1^{2} + ... + (m1)^{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?

 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) f_{k}(x), f_{1}(x)=x(x+1)/2, f_{2}(x)=x(x+1)(2x+1)/6, and so on, but is there a rule for the factors? And at f_{4}(x), a quadratic term appears, so I shall call the largest (factor of highest degree) g_{k}(x). g_{4}(x)=3x^{2}+3x1, g_{5}(x)=2x^{2}+2x1, g_{6}(x)=3x^{4}+6x^{3}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.
Re: Nonstandard proofs for simple theorems
Here is a proof without words due to ManKeung Sui, http://hkumath.hku.hk/~mks/, which demonstrates the result.

 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.
Re: Nonstandard proofs for simple theorems
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 ellipseshaped 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.tomtom2357 wrote:What are the roots of the functions?
Something worth thinking about: if g_{k}(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?

 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.
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
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 nth powers.
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 nth powers.
Re: Nonstandard proofs for simple theorems
It may be of interest to note that the dotproduct of the nth row (counting from 1) of the Eulerian number triangle, with a lengthn 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 ndimensional hypercube of side length r into several ndimensional “pyramids” of side lengths n, n1, n2, …, n(r1).
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 sidelength 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:
Eulerian number triangle:
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 1\cdot{{r+1} \choose 4} + 4\cdot{{r+2} \choose 4} + 1\cdot{{r+3} \choose 4}. Expanding that out gives the appropriate Faulhaber polynomial, and we see,
To prove this works, it is sufficient to show that 1\cdot{r\choose 3} + 4\cdot{{r+1} \choose 3} + 1\cdot{{r+2} \choose 3} = r^3. 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 \sum_{i=1}^{n}i^3 = \left(\sum_{i=1}^{n}i\right)^2 = n^2(n+1)^2/4. That, incidentally, has a neat visual proof of its own.
By looking at cubes made of unitcube 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 0based, and for the Eulerian number triangle is 1based. I followed both those conventions, and I hope it was not too confusing.
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 ndimensional hypercube of side length r into several ndimensional “pyramids” of side lengths n, n1, n2, …, n(r1).
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 sidelength 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:
Eulerian number triangle:
Spoiler:
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 1\cdot{{r+1} \choose 4} + 4\cdot{{r+2} \choose 4} + 1\cdot{{r+3} \choose 4}. 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 1\cdot{r\choose 3} + 4\cdot{{r+1} \choose 3} + 1\cdot{{r+2} \choose 3} = r^3. 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 \sum_{i=1}^{n}i^3 = \left(\sum_{i=1}^{n}i\right)^2 = n^2(n+1)^2/4. That, incidentally, has a neat visual proof of its own.
By looking at cubes made of unitcube 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 0based, and for the Eulerian number triangle is 1based. I followed both those conventions, and I hope it was not too confusing.
wee free kings
 skeptical scientist
 closedminded 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.cuttheknot.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 kbit string into n log(k+1) bits, violating the pigeonhole principle.
Spoiler:
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
"With math, all things are possible." —Rebecca Watson

 Posts: 563
 Joined: Tue Jul 27, 2010 8:48 am UTC
Re: Nonstandard proofs for simple theorems
antonfire wrote: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 ellipseshaped 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.tomtom2357 wrote:What are the roots of the functions?
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^((n1)D)]*f(1) (be careful with the n1)
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^Did...............e^Did.........................e^Did
Now recall the taylor expansion of (e^x1)^1 and just transer it over to the (e^D1)^1 case and you get:
http://www.abload.de/img/emcsumrcvyd.png
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 "StreetFighting Mathematics" by Sanjoy (freely, legally available online as pdf).
 Xanthir
 My HERO!!!
 Posts: 4860
 Joined: Tue Feb 20, 2007 12:49 am UTC
 Location: The Googleplex
 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 kbit string into n log(k+1) bits, violating the pigeonhole principle.Spoiler:
That one is really awesome. I love it!
(defun fibs (n &optional (a 1) (b 1)) (take n (unfold '+ a b)))
Re: Nonstandard proofs for simple theorems
vadsomhelst wrote:[...]
This is a really neat trick. Thanks very much.
 skeptical scientist
 closedminded 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 kbit string into n log(k+1) bits, violating the pigeonhole principle.Spoiler:
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/log_{2} n (rather than n/log_{e} 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
"With math, all things are possible." —Rebecca Watson

 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(1^{n}/(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(1^{n}/(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.
Re: Nonstandard proofs for simple theorems
I'm not sure how nonstandard 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)
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: 7453
 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 nthroot 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:
p^{n}/q^{n} = 2
p^{n} = 2q^{n}
q^{n} + q^{n} = p^{n}
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.
Say there was a p/q, p and q both integers, such that (p/q)^{n} = 2. Then:
p^{n}/q^{n} = 2
p^{n} = 2q^{n}
q^{n} + q^{n} = p^{n}
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)⚠);}

 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 nthroot 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:
p^{n}/q^{n} = 2
p^{n} = 2q^{n}
q^{n} + q^{n} = p^{n}
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: 7453
 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)⚠);}
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.
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 noncircular argument.
Re: Nonstandard proofs for simple theorems
Another proof that there are infinitely many primes:
Spoiler:
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.
Re: Nonstandard proofs for simple theorems
The sum of the interior angles of an Ngon is 180(N2). This is usually (?) proven by showing that an Ngon can be cut into N2 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 Ngon forms N triangles, totaling 180N degrees, but then you need to subtract away the central angles, which total to 360. 180N360 is of course the same as the usual 180(N2), distributed through.
Probably less interesting than most of this thread, but a 7thgrader invented it, which I thought was pretty impressive
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 Ngon forms N triangles, totaling 180N degrees, but then you need to subtract away the central angles, which total to 360. 180N360 is of course the same as the usual 180(N2), distributed through.
Probably less interesting than most of this thread, but a 7thgrader 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: 7453
 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 starconvex 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 externalangle 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).
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 externalangle 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)⚠);}

 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 nonstandard proof of the infinitude of the prime numbers:
Using the fact that any factor of 2^{p}1 (for prime p) is of the form 2kp+1, every factor of 2^{p}1 must be bigger than p, therefore for every prime p, there is a prime greater than p.
Using the fact that any factor of 2^{p}1 (for prime p) is of the form 2kp+1, every factor of 2^{p}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.
Who is online
Users browsing this forum: Robert'); DROP TABLE *; and 1 guest