Nonstandard proofs for simple theorems

[Blatm]

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)³ - n³. You're encouraged to share any other nonstandard proofs as well.

[phlip]

How about geometrically?
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
.  .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 rear-left corner. This pyramid has volume 1/3 n³. 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 n³/3 + n(n-1)/2 + 2n/3 - expanding these and simplifying shows it's equal to n(n+1)(2n+1)/6.

[tomtom2357]

What would constitute a *simple* proof?

[Proginoskes]

(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]

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, \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 r-choose-j, 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)(n-1)/6 = n(n+1)(2n+1)/6.

[antonfire]

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 ) = 0² + 2² + 4² + ... + (2(m-1))² = 4(0² + 1² + ... + (m-1)²).

So, 0² + 1² + ... + (m-1)² = 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 0² + 1² + ... + (m-1)² 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.

[tomtom2357]

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₁(x)=x(x+1)/2, f₂(x)=x(x+1)(2x+1)/6, and so on, but is there a rule for the factors? And at f₄(x), a quadratic term appears, so I shall call the largest (factor of highest degree) g_k(x). g₄(x)=3x²+3x-1, g₅(x)=2x²+2x-1, g₆(x)=3x⁴+6x³-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?

[dissonant]

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

[tomtom2357]

That is a cool proof!

[antonfire]

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 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.

[tomtom2357]

At what point do the roots become complex?

[dissonant]

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]

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]

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 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 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.

[skeptical scientist]

(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 p₁...p_n are the only primes. Let f: N -> Nⁿ be the function mapping a natural number to the exponents in its prime factorization. Clearly f is injective. If x≤2^k, then every component of f(x) is at most k, so f|_[1,2k] is an injective function from a set of size 2^k into the set [0,k]ⁿ of size (k+1)ⁿ.

[tomtom2357]

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!

[vadsomhelst]

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:
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 "Street-Fighting Mathematics" by Sanjoy (freely, legally available online as pdf).

[Xanthir]

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 p₁...p_n are the only primes. Let f: N -> Nⁿ be the function mapping a natural number to the exponents in its prime factorization. Clearly f is injective. If x≤2^k, then every component of f(x) is at most k, so f|_[1,2k] is an injective function from a set of size 2^k into the set [0,k]ⁿ of size (k+1)ⁿ.

That one is really awesome. I love it!

[Blatm]

[...]

This is a really neat trick. Thanks very much.

[skeptical scientist]

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 p₁...p_n are the only primes. Let f: N -> Nⁿ be the function mapping a natural number to the exponents in its prime factorization. Clearly f is injective. If x≤2^k, then every component of f(x) is at most k, so f|_[1,2k] is an injective function from a set of size 2^k into the set [0,k]ⁿ of size (k+1)ⁿ.

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₂ n (rather than n/log_e n), but I can't seem to remember how it went.

[tomtom2357]

I have a nonstandard proof that pi/4=sum(-1ⁿ/(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ⁿ/(2n+1), n>=0), QED.

[Talith]

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]

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]

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)ⁿ = 2. Then:
pⁿ/qⁿ = 2
pⁿ = 2qⁿ
qⁿ + qⁿ = pⁿ
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.

[tomtom2357]

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)ⁿ = 2. Then:
pⁿ/qⁿ = 2
pⁿ = 2qⁿ
qⁿ + qⁿ = pⁿ
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

[phlip]

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.

[Hopper]

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]

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]

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

[z4lis]

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 \pi^2/6, which is irrational.

[Meteoric]

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

[phlip]

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).

[tomtom2357]

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 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.