The Moessner Miracle - Holiday Forum

Date: 19/07/2021 21:30:48

From: SCIENCE

ID: 1767325

Subject: re: The Moessner Miracle

Welcome to another Mathologer video.
It’s been an absolutely insane first half of the year in my part of the world.
Busy, busy, busy.
Luckily I can see the light at the end of the tunnel and so I am looking forward to a lot more Mathologer action in the coming months.
Anyway, let’s have some fun today :) Have you heard of Moessner’s miracle?
No?
Not many people have which is a real shame.
Well, today’s mission is to do something about this sorry state of affairs :) As usual, we’ll start with an easy warm-up, and most of you will be very familiar with this one.
We’ll begin by adding up the odd numbers.
There is 1, plus 3 is 4, plus 5 is 9, plus 7 is 16, plus 9 is 25, and there 36.
So adding the odd numbers gives the squares.
A very pleasant surprise when you first encounter this famous mathematical gem.
Okay, but how can we be sure that this pattern really continues forever and ever after?
Well, there is also a famous and beautiful visual proof, that goes back to at least the time of Pythagoras.
It may even be due to Pythagoras himself or one of the members of his fan club, the Pythagoreans.
Proof time, here we go.
Okay, odd numbers.
Let’s add them again.
1 plus 3 is 4.
Aha :) plus 5 is 9.
All clear now, right? :) Very, very nice :) People have been in love with this proof and some related proofs for thousands of years.
And, for the longest time pretty much everybody was under the impression that there was nothing left to discover in this respect.
That is until about 70 years ago when Alfred Moessner, the guy you’ve never heard of, discovered a truly miraculous extension of our odds into squares result.
Moessner’s discovery was first published in 1951 in the Sitzungsberichte … That’s it over there, just one page.
And not hard to make sense of (if you happen to speak German :), so let’s just go for it.
We’ll start by reframing our classic odd numbers theorem in a special way.
Start with ALL the positive integers.
Now, highlight every second number.
Now let’s add all the numbers that are not highlighted, that’s just the odd numbers again, right.
There the squares again.
Now Moesser’s idea was to start this process in a slightly different way.
Instead of highlighting every second number he highlights every third number.
Now he adds all the numbers that are not highlighted.
Okay so 1 plus 2 is 3, skip the highlighted 3.
So plus 4 is 7, plus 5 is 12, skip the 6.
plus 7 is 19, and so on.
Hmm, okay but now what?
Those new numbers don’t look that special.
Well we are not finished yet.
Now we highlight every second among the new numbers.Highlighting done.
And now we add up again.
1, skip, plus 7 is 8 skip, plus 19 is 27.
1, 8, 27, do you see the pattern?
Yep, those are the cubes :) Amazing isn’t it.
How on Earth do we end up generating the cubes this way?
Also, there is more, much more :) And now that I’ve announced that there is more, can you guess what the more is?
Can you see where we are heading?
I’ll bet plenty of you have got it.
To begin, highlighting every second integer and then adding up gives the squares.
Then, highlighting every third integer and adding up, followed by a second step of adding and highlighting, gives the cubes.
So what about skipping every forth integer or every fifth integer?
Let’s be brave and go for every fifth integer.
Add up all the greys.
Highlight every fourth, add up, highlight every third, and so on.
Yep, there are the fifth powers.
And, in general, what Moessner discovered was that if we start by highlighting every nth integer, we end up with the nth powers of the integers.
Amazingly cool, isn’t it?
Having fun so far? :) OK, this is Mathologer, so on with the proof right?
And we must be close.
After all, Moessner’s paper was just one page, so it should be quick and we’ll be done.
This could be our shortest ever Mathologer video.
Well, it’s not that simple that one-page write-up of Moessner’s miracle actually did not include a proof.
The first published proof was by the math professor Oscar Perron, one of Moessner’s acquaintances.
I could not find a photo of Moessner but there that’s Perron over there with his proof.
So, plan B, let’s go through Perron’s proof, ok?
First we’ll take a quick look.
Okay, maybe not.
Perron’s proof is pretty much impossible to explain here on Mathologer in a nice visual and accessible way.
How about a different proof?
Nope.
Plans C, D and E are also doomed to fail.
A number of other algebraic proofs have appeared over the past 70 years, and also don’t lend themselves to Mathologerization.
So, Plan F it is.
And plan F is to give up?
Of course not!
Mathologerers never give up.
When we cannot find a proof in the literature that can be nicely Mathologerised, we often try to customise and prove things ourselves.
So, let’s give up on the algebra.
How about a visual proof for Moessner’s theorem?
Maybe something that generalises the Pythagorean gem?
Well, I gave it a go an it turns out there IS actually something there.
The classic proof for odd numbers relies upon turning one square into the next larger one by adding an L-shaped shell.
Like this.
The Pythagoreans had a special name for these very handy L- shapes.
They called them GNOMONS.
For what we have in mind, the first thing to notice is that there are also Gnomons for 3d cubes.
From the other side, this shell looks like a hexagon.
And the number of little cubies in this shell is 37.
Aha! :) There that’s 37 up there, great :) And what about the number of cubies in the other shells?
Yep, as we would hope, 19, 7 and 1.
Very promising.
It’s also possible to spot the remaining grey numbers in those shells.
To see these numbers note that the brown dots marking the cubies can be separated into hexagons like this.
Now, let’s count.
There is the 1.
Let’s highlight 2 dots on the smallest hexagon.
Then there are 4 dots remaining in this hexagon.
Here are 5 dots on the next larger hexagon.
And there are 7 dots remaining in this hexagon.
And so on.
Pretty obvious that this pattern will continue forever.
Now, to prove that Moessner’s method always gives cubes we can argue visually as follows.The shells stack together to form real 3d cubes.
So, to show that Moessner’s process produces integer cubes, we just have to show that the grey numbers in the second row are indeed the numbers of cubies in the different shells.
But having prepared our hexagons earlier, that’s now easy.
There is the one.
To get the next shell, take a copy of the 1 and add a 2 and a 4 to it.
To get 19, take a copy of the 7 and add a 5 and a 7 to it, and so on.
And all this amounts to a visual proof that Moessner miracle really produces all cubes.
Very pretty, isn’t it?
And as I said, as far as I know we’re dealing with a brand new proof here.
Very cool. :) But of course there is more to Moessner’s miracle than just the cubes.
How would you go about trying to prove that we are always getting the fifth powers up there?
Well, if you are a 5-dimensional creature that’s a no-brainer.
Just start by considering 5d shells of 5- d cubes :) In fact, when you do this you’ll find that these numbers here are just the numbers of cubies in these 5 d shells.
Promising, but now what?
Also, 5d cubes are a bit hard for us mere 3d creatures to visualise.
So, if we want a visual proof that works in our 3d world for all powers, we need a different approach.
Luckily there IS a totally different but still super nice proof.
I’ll show you this proof at the end fo the video.
But before that, there are some other beautiful Moessner-like discoveries that I really must show you.OK, here is a new trick.
Highlight the 1, skip 1 and highlight again.
Now skip 2 and highlight.
Skip 3 and highlight, 4, and so on.
Now do the Moessner summing, with as many steps as you need for the larger gaps.Do those numbers we end up with look familiar?
Looks like the factorials, doesn’t it.
There, 1×2×3×4=24 that 4!.
That’s very cool but there is more.
Have a look at this.
Interesting 1+2 turns into 1×2, 1+2+3 turns into 1×2×3 and so on.
+ turns into x.
This is not a coincidence.Have another look at the cubes.
So here 1×3 turns into 1^3, 2×3 turns into 2^3, and so on.
So what is going on here?
In general, the question is, given a sequence of highlighted integers, what sequence will be produced by Moessner’s method, and how are the two sequences related?
Here is one of the crazy answers to this question.
Pick a few non-negative integers a, b, c, d, however many you want (one has to be positive).
Then make up a highlighted sequence from these numbers like this.
Now, hold on to your hats.
The sequence generated is this.
So again sums have turned into products, and multiples into powers?
Feels familiar, doesn’t it?
It’s a logarithm-exponential kind of thing.
Here are some examples of this remarkable relationship in action.
If a is non-zero and b, c, d, e, etc.
are all zero, we get this.
That’s Moessner’s original result.
a =3 gives the cubes, a=5 gives the fifth powers, and so on.
Another example.
Make a, b, c, d, etc.
all equal to a.
Then we get…
If we then choose a to be equal to 1, that’s the factorial example again.
And, you probably guessed it, there is more.
For example, given two input sequences with these output sequences, then the sum of the two input sequences gives the product of the two output sequences.
As well, if we avoid some predictable hiccups, the output of the difference sequence will be the Quotient sequence.
And, there is plenty more.
But that’s probably enough new stuff for today.
I’ll include some links in the description of this video for those of you who want to delve a bit deeper.
Challenge for you: If the input sequence is the sequence of squares what is the simple formula for the output sequence?
To finish off let me show you a Mathologerisation of a very nice graph-theoretic proof of Moessner’s original nth power miracle.
This proof was published by Karel Post in 1990.
A real treat for you mathematical gourmets.
Of course, we’re getting into the real thing here.
So, this is a good time to grab a cup of coffee and buckle your mathematical seat belts.
Ready?
Well, then here we go.
We first show that we’ll get all fifth powers by using Moessner’s method.
All other instances of Mossner’s miracle can then be proved in the same way.
To start with, have a look at the triangle of numbers on the left Does this look familiar?
No?
Maybe tilt your computers 45 degrees?
No, wait, bad idea.
I’ll help you.
Still does not ring a bell?
How about if I add this string of 1s on the right?
Now you’ve go it.
Right?
This is just the tip of Pascal’s triangle which I’m sure you’ve all seen before.
Clearly something is going on there, so let’s rotate back and add a top row of 1s to Moessner’s set up.
Like this.
That’s looking very nice.
And that extra row actually meshes in seamlessly with the original scheme.
Just watch.
Let’s get to Moessnering.
So, start adding: 1 plus 1 is 2 plus 1 is 3 plus 1 is 4 plus 1 is 5, and so on.
So, we have seamlessly slotted Pascals’ triangle into our Moessner tableaux.
But how does this help?
Well, Pascal’s triangle is special in many ways, but for us what is important is the way it grows.
The left and right sides of Pascal’s triangle consists of 1s.
Then, any two side-by-side numbers add to give the number below.
So, starting with the 1s we get this: 1+1 = 2 1+2 =3 2+1 =3 3+1=4 and so on Here is a related property of Pascals triangle.
Replace every number by a circle, make the top circle blue, and connect every circle to the two circles directly below, like this.
Turn any one of the green circles into an orange circle.
Now, how many different journeys following the arrows are there from the blue circle to the orange circle?
Do you know this?
It turns out that the number of journeys from the blue top to the orange circle is just the Pascal number in that orange circle.
Let’s check that this is true for the example there.
Here is one journey, two, three.
So, that one’s fine.
And why does this work in general?
Well for trips down the sides of Pascal’s triangle it’s all obvious.
There’s just one way to keep going down the edge, and therefore we also have 1s all the way down.
Now, what about an orange circle in the middle somewhere?
Well, to get to this orange circle, we have to travel via one of the two circles directly above it, the pink or the the purple guys there.
But that means, however many ways there are to travel to the pink guy, and similarly the purple guy, the sum of these will be the number of ways to get to the orange circle.
And, of course, that’s exactly how the Pascal numbers are generated.
So, the numbers of travel paths start the same way and build the same way as the Pascal numbers, and so must always equal the Pascal numbers.
Easy peasey.
What about the other triangles?
How are they built?
Well, let’s have a look at the second triangle.
So, it’s still a Pascal-ish triangle right?
The numbers on the left edge aren’t all 1s any more, but the numbers in the middle are all produced by the same addition rule.
There 6 plus 1 equals 7.
16 + 7 equals 23 and so on.
And now that we know what we know, it’s not hard to check that not only do the numbers in the first triangle count the numbers of journeys from the blue circle, but that indeed all the numbers count the numbers of journeys in this bigger arrow diagram.
Either take my word for it or convince yourself that this is true.
Really easy.
Anyway, as an example, to get to this circle labelled 6 we have to pass via one of these two circles.
And of course, 5+1 = 6.
Works.
Another one.
Down there 32 + 211 = 243, and so on.
Super duper nifty:) Now comes the key trick.
Reverse all the arrows.
Now, all the reversed paths are heading to the blue target circle at the top.
So what do the numbers now indicate?
Yep, they tell us the number of journeys from that circle to the target circle at the top.
OK, the stage is all set.
Remember, we’re trying to show that Moessner’s summing method results in successive fifth powers at the bottom circles of the triangles.
So what we have to prove is that from here there is exactly one journey to the blue target (pretty obvious really :).
Then we have to show that from here there are 32 journeys to the target.
That from here there are 243.
and so on.
…
Okay, let’s start from the red circle.
Then it’s completely obvious that there is only one way to get from the red circle to any of the circles right above.
Right?
Let’s move the red circle to the right.
How about the number of journey from this red circle to the blue target circle?
Let’s count them from scratch.
Well, first, going straight up, it’s all 1s again.
What about this circle?
Well, there is only one arrow leading to it and it originates in a 1.
This means that the circle in question also has to be a 1.
In other words, there is only one journey from red to this new circle.
And obviously the same is true for all these circles.
Now 1+1 is 2.
The same for all these circles 2+2 is 4 and so the next diagonal is all 4s.
Next is 8 16 32 And there we have it, the 32 we were hunting for.
And, a very nice power-of-2 pattern in the triangle on the left to get there.
You can sense how this is working right?
Let’s start the next count.
Then, because of the repeating pattern, our count again starts like this.
Arguing as before we get this transfer of numbers.
Now let’s just fill in the rest.
Okay, 243 in the blue circle as expected.
great.
But why?
We’ll get to the explanation in a moment, promise.
Let’s just do one more count first.
As before we get this transfer of numbers, and so on.
Time for some pattern spotting.
For this we’ll scan things from the right to the left.
Watch.
Powers wherever you look.
Hmm.
Let’s go again.
There the powers of 1 turn into the powers of 2, the powers of 2 turn into the powers of 3, and so on.
Very, very pretty how all the pieces fall into place.
So that has to be it.
Right?
If we can prove this pattern, that in general, the powers of n on the right side of a triangle are converted into the powers of (n+1) on the left side of the triangle, then we will have proved Moessner’s miracle.
All clear?
Okay, to figure out what’s going on, let’s see how the powers of 3 on the right combine into the powers of 4 on the left.
Let’s focus on this entry here.
Obviously, the only powers of 3 on the right that can contribute to this entry are the bottom four.
So, with just a bit of algebra autopilot we get this.
Aha.
What are those coefficients in front of the powers of 3?
1 3 3 1.
They’re very familiar, right?
Well, for example the 3 in front of 3^1 is equal to the three different journeys from the 3^1 circle to the orange.
And similarly with the other coefficients in the sum.
What this means is that those coefficients 1 3 3 1 are just the numbers in the fourth row of Pascal’s triangle.
And that means that our sum amounts to an instance of the binomial formula, one of those distant things from high school and the encapsulation of Pascal’s triangle.
Remember it now?
And setting a=1 and b=3, you get our power of 4 sprouting from our powers of 3.
Nice :) And this all easily generalises to produce all the other powers of 4 on the left.
And that’s how Karel Post proved Moessner’s miracle.
A very pretty and ingenious proof, don’t you think.
Made my day the first time I encountered it.
Well, and that’s it for today.
Until next time :)

Reply Quote