Back in high school I discovered this by accident (yes, I was really bored!). I suppose it's nothing new, but it turns out that this works for more than simple squares and cubes:
Given any sequence of numbers, keep finding differences of differences until you hit a constant; the number of iterations needed is the maximum exponent in the formula that produced the numbers. That is, this works even if there are other terms, regardless of whether any or all terms have coefficients other than 1.
This is obvious after you learn calculus. The "nth difference" corresponds to nth derivative (a sequence just looks at integer points of a real-valued function), so clearly a polynomial of degree n has constant nth derivative. It would be even more accurate to say that an nth antiderivative of a constant is precisely a degree n polynomial.
Iterated finite differences correspond to derivatives in some non-obvious way I can't remember (and can't be bothered to find out).
Notice that the result doesn't hold if the points aren't evenly spaced, so the solution must use this fact.
Differences and derivatives are not the same, though there is the obvious analogy. If you want to take derivatives and antiderivatives, you want to write in the x^k basis or the x^k/k! basis. If you want to take differences and sums, you want to write in the falling factorial basis or the x choose k basis.
If you get a non constant, yes. For a linear function, f(a+1) - f(a) = f'(a). Inductively you can then show that the nth one-step difference of a degree n polynomial f at a point a is f^(n)(a). But this doesn't work for anything but n. Thanks for pointing that out!
Ah, yes, that's a good point, because the leading coefficient be the same whether you use the x^k basis or the falling factorial basis.
Neither finite differences nor calculus are new to me, but I didn't pick up the correlation between the two until now, and it really is obvious.
This is why I love mathematics - there's always a trick hidden up the sleeve!
I agree that it's implied by working out the logic and finding that it doesn't apply elsewhere. I disagree that it is implied by the phrasing.
Given any sequence of numbers
doesn't seem to restrict it, and though I suppose
the number of iterations needed is the maximum exponent in the formula that produced the numbers
implies that there is a "maximum exponent in the formula" and with slightly more reasoning (a number of iterations isn't going to be fractional) that it must be a formula with a whole number maximum exponent, I don't see anything that precludes, for instance, x^2 + x^(1/2), which would also never go constant.
Sorry, I was using the weak "implies", and probably too much charity.
And I usually only look at this sort of thing in the context of algorithm analysis, so I'm used to thinking that x squared is pretty much equal to 5 x squared plus 2 log x plus square root of x plus 37.
None of this was really new content to me, and yet I enjoyed reading it immensely. It must be what going to church is sometimes like for a theist, the reassurance hearing a sermon on beautiful things you already know. :-)
But what was the bias to be overcome? Mathematical platonism?
Any sequence of numbers Ak = f(k), where f(k) is a polynomial of degree n, will have its nth differences a constant. This is the method of "finite differences"; in fact, taking the differences of a sequence of numbers is roughly analogous to differentiation, and taking partial sums is analogous to integration.
It's an interesting fact about the way mathematics has historically developed that the analogous statement about polynomials viewed as functions of real numbers seems much more obvious to most people that have some mathematical training.
I love math. It's the only reason I sometimes wish I'd stayed in school. When I get rich, I want to hire a mathematician to live in my basement and tutor me. I bet they can be had for cheap.
Pure math is potentially a perfect idea. Applied math; not so much. When you see that line of 2's, how do you know it continues forever? You don't. You're making an induction; a beautiful guess. It's only because you peeked at the real answer-- an answer you yourself created-- that you can confidently say that you "predicted" the sequence with your method.
I'm much more interested in sequences produced in a simple deterministic way that are extremely difficult to crack. The move from "it makes no sense" to "it's obvious" is a critical dynamic in human thought. I'd like to see you write about that.
As Polya would say, solving these problems is a heuristic process. The reason you think you find order when you dig down far enough is that you systematically ignore any situation where you don't find order. Your categories have order built into them. You are drawn to order. There are probably a host of biases influencing that: availability, ontology, instrumentalism, and hindsight among them.
There's lots of order to be found. There is also infinite amounts of disorder, unprovable order, and alternate plausible order. Occam's razor helps sort it out-- that's also a heuristic.
Thanks for the beauty, it feels good. Some thinking out loud. I can't help but feel that the key is in the successive layers of maps and territories : maths is (or contains) the map of which physics is the territory, physics is the map of which 'the real world' is the territory, 'the real world' is the map our brains create from the sensory input concerning the territory which is the 'play of energies' out there, while that in itself is another map. Antony Garrett Lisi's proposal, as an example, would be the most elegant meta-map yet. What these maps have in commmon is : being created by the human brain, a wet lump of nervous tissue comprising ad-hoc purpose specific modules. It has specific ways of making maps, so small wonder all these layers of maps are coherent. Now if the 'mathematics' layer of maps has unforeseen and self-consistent properties, it could be just a manifestation of the nature of our map-making modules : they are rules driven. So, is the Universe a geometric figure corresponding to a Lie E8 group, or does that just happen to be the way the human brain is built to interpret things ?
So... Should it be obvious that the nth difference is n factorial? I'm afraid I don't have intuitive knowledge of all the properties of the factorial function.
To go even further, if you take the sequence A[k] = k^n and, for each n, take differences until you reach a constant, then the list A[n] of those constants is n factorial (n!).
This reminds me of when I first started learning about topological spaces, and then we added a metric, suddenly all the theorems and lemmas we'd had to prove in fiddly ways with lots of epsilons and deltas in first year analysis were blindingly and beautifully obvious. The sheer glorious interconnectedness was so overwhelming that I very nearly orgasmed in the lecture theatre!
Josh, if you think about a picture like the one Eliezer drew (but in however many dimensions you like) it's kinda obvious that the leading term in the difference between two n-cubes consists of n (n-1)-cubes, one per dimension. So the leading term in the next difference is n(n-1) (n-2)-cubes, and so on. But that doesn't really give the n! thing at a glance. I'm not convinced that anything to do with nth differences can really be seen at a glance without some more symbolic reasoning intervening.
James Bach, I suspect that the really good mathematicians can't be had for cheap because doing mathematics is so important to them, and the quite good mathematicians can't be had for cheap because they've taken high-paying jobs in finance or software or other domains where a mathematical mind is useful. But maybe it depends on what you count as "cheap" and what fraction of the mathematician's time you want to take up with tutoring...
Isabel, I think perhaps differentiation really is easier in some sense than differencing, not least because the formulae are simpler. Maybe that stops being true if you take as your basic objects not n^k but n(n-1)...(n-k+1) or something, but it's hard to see the feeling that n^k is simpler than that as mere historical accident.
The beauty of it all never fails to shock me, and I'm very much a novice. 'The Road To Reality' is sitting on my shelves looking darkly at me, waiting to be attacked for the first time. I can only imagine what being at the cutting edge must be like.
But maybe it depends on what you count as "cheap" and what fraction of the mathematician's time you want to take up with tutoring...
Such a mathematician's answer.... ;)
Carl Linderholm notes in Mathematics Made Difficult that the next number in 1 2 4 8 16 ? has to be 31, based on just those differences.
Lautreamont on mathematical objects.
Quote from a friend: "Mathematicians are Platonists pretending to be formalists."
Words that ring true in every math department I've ever been to...
"To say that human beings "invented numbers" - or invented the structure implicit in numbers - seems like claiming that Neil Armstrong hand-crafted the Moon. The universe existed before there were any sentient beings to observe it, which implies that physics preceded physicists."
No, there's a conflation of two things here.
Have you ever really looked at a penny? I'm looking at a 1990 penny now. I know that if you look at the front and you see the bas-relief of Lincoln, and the date 1990, and it's a penny, then you can be sure that the back side will have a picture of the Lincoln memorial. It works! And you can find all sorts of connections. Like, there's a single "O" on the front, in the name GOD in the phrase IN GOD WE TRUST. And there's a single "O" on the back, in the phrase ONE CENT. One O on the front, one O on the back. A connection! You could make lots and lots of these interconnections between the front and the back of the penny, and draw conclusions about what it means. You could invent a discipline of Pennyology if only somebody would fund it.
Is it true that Pennyology is implicit in pennies? In a way. Certainly the pennies should exist before the Pennyology. But the pennies are only whatever they are. The existence of pennies doesn't tell us much about what the practitioners of the discipline of Pennyology will actually notice. They might never pay attention to the pair of O's. There could be a fold in Lincoln's coat that after the proper analysis provides a solution to the whole world crisis, and they may never pick up on it. While it's predictable that different independent attempts at Pennyology would have a whole lot in common since after all they all need to be compatible with the same pennies, still they might be very different in some respects. You can't necessarily predict the Pennyology from looking at the penny. And you can't predict what mathematics people will invent from observing reality.
You can predict some things. A mathematics that invents the same 2D plane we use and that proves a 3-color theorem has something wrong with it. But you can't predict which things will be found first or, to some extent, which things will be found at all.
If there's a reality that mathematics must conform to, still each individual version of human mathematics is invented by humans.
Similarly with physics. Our physics is invented. The reality the physics describes is real. We can imagine a platonic-ideal physics that fit the reality completely, but we don't have an example of that to point at. So for example before Townsend invented the laser, a number of great physicists claimed it was impossible. Townsend got the idea because lasers could be described using Maxwell's equations. But people thought that quantum mechanics provided no way to get that result. it turned out they were wrong.
Actual physics is invented. Certainly incorrect physics must be invented. There's nothing in reality that shows you how to do physics wrong.
I don't see how Pennyology proves your point: a pennyologist discovers that there's an O on the front and an O on the back. Perhaps he invents meaning to attach to this fact, but the fact was first discovered.
Or is that what you were saying: that we discover mathematical facts, but in fact what we call "mathematics" is the invention of meaning that we attach to certain favored facts?
"So... Should it be obvious that the nth difference is n factorial? I'm afraid I don't have intuitive knowledge of all the properties of the factorial function."
I don't remember writing this. Did somebody else write this using the same handle as me or did I write this and forget it?
"I don't remember writing this. Did somebody else write this using the same handle as me or did I write this and forget it?"
My son's name is also Bort.
Chris and Ben, we create axiom systems and we discover parts of "mathematics". There are probably only a finite number of theorems that can be stated with only 10 characters, or 20 characters, or 30 characters, provided we don't add new definitions. But the number of possible theorems quickly gets very very large. Will each independent group of mathematicians come up with the same theorems? Probably not. So we get different mathematics.
How different could alien mathematics be? I don't know. We could look at a variety of alien mathematics and see. Except, we don't have much of that. We presumably had different mathematical traditions in china, india, and europe, and we got some minor differences. But they were solving similar real-life problems and they could have been in communication. If you want trade in silk then you need a lot of it for it to make much difference. A very few mathematicians traveling could spread ideas easily.
It's easy to see alternate physics, and alternate technology is kind of arbitrary. I think alien math might be pretty different depending on which theorems they proved first. But I don't have good examples to demonstrate it.
The Pennyologist who notices the O's is not that different from the Pennyologist who notices there's one L on each side. A particular Pennyology might notice one of those, or the other one, or both. Out of the many relationships you could pick out from the penny, which ones will people pay attention to?
The differences method is of course strongly related to differential calculus. The first difference corresponds to the first derivative, etc. And just like in differences, the nth derivative of a x^n term is sure enough a constant.
Eliezer sometime ask something that I would now like to ask him: how would the world looks like if mathematics didn't precede mathematicians? And if it did?
Consider the sequence {1, 4, 9, 16, 25, ...} You recognize these as the square numbers, the sequence Ak = k2. Suppose you did not recognize this sequence at a first glance. Is there any way you could predict the next item in the sequence? Yes: You could take the first differences, and end up with:
{4 - 1, 9 - 4, 16 - 9, 25 - 16, ...} = {3, 5, 7, 9, ...}
And if you don't recognize these as successive odd numbers, you are still not defeated; if you produce a table of the second differences, you will find:
{5 - 3, 7 - 5, 9 - 7, ...} = {2, 2, 2, ...}
If you cannot recognize this as the number 2 repeating, then you're hopeless.
But if you predict that the next second difference is also 2, then you can see the next first difference must be 11, and the next item in the original sequence must be 36 - which, you soon find out, is correct.
Dig down far enough, and you discover hidden order, underlying structure, stable relations beneath changing surfaces.
The original sequence was generated by squaring successive numbers - yet we predicted it using what seems like a wholly different method, one that we could in principle use without ever realizing we were generating the squares. Can you prove the two methods are always equivalent? - for thus far we have not proven this, but only ventured an induction. Can you simplify the proof so that you can you see it at a glance? - as Polya was fond of asking.
This is a very simple example by modern standards, but it is a very simple example of the sort of thing that mathematicians spend their whole lives looking for.
The joy of mathematics is inventing mathematical objects, and then noticing that the mathematical objects that you just created have all sorts of wonderful properties that you never intentionally built into them. It is like building a toaster and then realizing that your invention also, for some unexplained reason, acts as a rocket jetpack and MP3 player.
Numbers, according to our best guess at history, have been invented and reinvented over the course of time. (Apparently some artifacts from 30,000 BC have marks cut that look suspiciously like tally marks.) But I doubt that a single one of the human beings who invented counting visualized the employment they would provide to generations of mathematicians. Or the excitement that would someday surround Fermat's Last Theorem, or the factoring problem in RSA cryptography... and yet these are as implicit in the definition of the natural numbers, as are the first and second difference tables implicit in the sequence of squares.
This is what creates the impression of a mathematical universe that is "out there" in Platonia, a universe which humans are exploring rather than creating. Our definitions teleport us to various locations in Platonia, but we don't create the surrounding environment. It seems this way, at least, because we don't remember creating all the wonderful things we find. The inventors of the natural numbers teleported to Countingland, but did not create it, and later mathematicians spent centuries exploring Countingland and discovering all sorts of things no one in 30,000 BC could begin to imagine.
To say that human beings "invented numbers" - or invented the structure implicit in numbers - seems like claiming that Neil Armstrong hand-crafted the Moon. The universe existed before there were any sentient beings to observe it, which implies that physics preceded physicists. This is a puzzle, I know; but if you claim the physicists came first, it is even more confusing because instantiating a physicist takes quite a lot of physics. Physics involves math, so math - or at least that portion of math which is contained in physics - must have preceded mathematicians. Otherwise, there would have no structured universe running long enough for innumerate organisms to evolve for the billions of years required to produce mathematicians.
The amazing thing is that math is a game without a designer, and yet it is eminently playable.
Oh, and to prove that the pattern in the difference tables always holds:
As for seeing it at a glance:
Think the square problem is too trivial to be worth your attention? Think there's nothing amazing about the tables of first and second differences? Think it's so obviously implicit in the squares as to not count as a separate discovery? Then consider the cubes:
Now, without calculating it directly, and without doing any algebra, can you see at a glance what the cubes' third differences must be?
And of course, when you know what the cubes' third difference is, you will realize that it could not possibly have been anything else...