My son is SUCH a geek (in a good way) :)
Back when Daniel was in 5th grade, his teacher Bob Whittemore taught a unit that he called "Patterns and Functions". The unit used sequences of numbers to introduce the students to the concept of polynomials and polynomial equations.
The core of the patterns and functions unit involves a mechanism that can be used to find the equation for any polynomial from the series generated by the polynomial.
For example, if you have the sequence:
| 1 | 79 |
| 2 | 561 |
| 3 | 2279 |
| 4 | 6445 |
| 5 | 14679 |
| 6 | 29009 |
you can find the polynomial that generated this sequence by subtracting item <n> from item <n+1>. In this case, you get:
| 1 | 79 | |
| 2 | 561 | 482 |
| 3 | 2279 | 1718 |
| 4 | 6445 | 4166 |
| 5 | 14679 | 8234 |
| 6 | 29009 | 14330 |
you repeat until the differences stabilize. Eventually you'll get something like:
| 1 | 79 | ||||
| 2 | 561 | 482 | |||
| 3 | 2279 | 1718 | 1236 | ||
| 4 | 6445 | 4166 | 2448 | 1212 | |
| 5 | 14679 | 8234 | 4068 | 1620 | 408 |
| 6 | 29009 | 14330 | 4096 | 4028 | 408 |
The sequence stabilizes after n iterations (in this case 4), that tells us the highest degree of the polynomial.
The coefficient of the x^n term is the stabilized difference divided by n! (factorial). In this case, the difference is 408, 408 / 4! = 17, which in fact is the first term of the equation.
Now that you know the highest order term, you go back to your original sequence of numbers and subtract the highest order term (17x^4th in this case) from the number which will give you a new series (this time you know it will stabilize after 3 iterations). Wash, rinse and repeat <n> times (one for each of the exponential terms), and you'll figure out that the original equation was: 17x^4+32*x^3+x^2+<something>. To find the value of <something>, simply solve the original equation for x=1 and you'll get 17+32+1=50. 79-50 = 29, so <something> = 29 and thus the original equation is:17x^4+32*x^3+x^2+29.
Anyway, Mr. Whittemore never knew the official name for this technique, he just knew it worked. Daniel's been trying to figure out what the "official" name of this was for years, he's asked every one of his math teachers over the years and none of them have ever known the answer.
Yesterday, he asked his math teacher from last year about it and he finally got the answer :) It turns out that this is officially called the "Method of Successive Differences". Live search points to a cached page (the original apparently isn't live).
I retried my search using google, and it turns out that Google has scanned a book from 1834 called "An Elementary treatise on algebra, theoretical and practical" which spells out the mechanism in detail.
So why did I entitle this post "My son is SUCH a geek (in a good way)"?
When Valorie picked Daniel up from school, he was bubbling that he'd found this information. He insisted that she drive to his old school right away so he could find Mr. Whittemore and let him know that he'd finally learned the official name for what Mr. Whittemore's been teaching for years. As Valorie drove away from the school, Daniel opened up the car window and shouted out to anyone who would listen: "I know what Patterns and Functions is called!". I don't know if I've ever seen him more excited.
So yeah, my son is SUCH a geek :).
And I love him :).
Edit: Fixed typo in the actual equation. Thanks Ben for checking my math.
Comments
Anonymous
November 07, 2007
Thanks for this. I had noticed this years ago and had been asking teachers why it worked. Most of the math teachers I brought this to had never noticed this particular pattern. It started for me when I found out that the difference in the simple sequences (e.g. 1, 4, 9, 16). I've been searching for years and finally someone found it. Thanks a ton.Anonymous
November 07, 2007
woah your son really is SUCH a geek! :)Anonymous
November 07, 2007
PingBack from http://msdnrss.thecoderblogs.com/2007/11/07/my-son-is-such-a-geek-in-a-good-way/Anonymous
November 07, 2007
You guys call yourself geeks, yet you weren't aware how Babbage's Difference Engine works???? For shame...Anonymous
November 07, 2007
Neat! The real fun comes in seeing how this algorithm falls out from our friend the derivative.Anonymous
November 07, 2007
Ben, he'll get that next year when he hits Calc 1. And yes, I'm very interested in seeing if he puts the pieces together.Anonymous
November 07, 2007
"To find the value of <something>, simply solve the original equation for x=1 and you'll get 17+32+1=50. 79-50 = 29, so <something> = 50 and thus the original equation is:17x^4+32*x^3+x^2+50." This shows that <something> = 29, not 50, so the the equation is actually y=17x^4+32x^3+x^2+29. :)Anonymous
November 07, 2007
Thanks Ben, I've fixed the error in the original (stupid typo)Anonymous
November 07, 2007
I had learned that from Martin Gardner's column, fortunately not in 1834. Of course the result is just the simplest (lowest order) polynomial that fits the data, not guaranteed to be the correct pattern. For example if the 6th row weren't shown then the number of columns would remain unchanged, and the number 408 would only appear once, but it would still yield the simplest polynomial. For another example if the 7th row were shown with a suitably chosen (or observed) data point in the first column, then maybe the two 408's would have a -97 below them, and you'd have to look one or two more columns to the right to find the simplest polynomial. Of course there are some functions in nature or computing where the actual fact isn't represented by any polynomial, but given any finite number of data points you can construct a polynomial that works just for the given points. Back to patterns, one way of constructing a neat (for some definition of neat) interesting (for some definition of interesting) puzzle is as follows. Construct some diagram with enough data points and fill in all except two of the data points in a manner that makes it look like there's some obvious (for some definition of obvious) pattern, and fill in one more data point which surprises the viewer by differing from that pattern. Usually the value is just 1 too large or 1 too small. The viewer has to figure out the second-most-obvious pattern and fill in the last data point. Of course it has to be designed so that the second-most-obvious (for some definition of second-most) isn't something dumb like the simplest polynomial. Now that's patterns for you.Anonymous
November 07, 2007
Nice! Has anyone ever tried putting this into code? I recently realized I need this kind of thing for a pet project of mine, and now I at least know how the technique is called :) Anyway, I'll try implementing this algorithm in C#. /me gets to work...Anonymous
November 07, 2007
I remember learning the n'th order part of this while in 6th form. Along with a lot of other approaches to finding underlying function from a sequence of numbers... but finally got stumped, turns out teacher was something of a joker, once in a while the sequence was random :-). Of course the remaining maths geek in me wants to avoid all that subtraction... so r'th order delta can be calculated "directly" via: <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:m="http://schemas.openxmlformats.org/officeDocument/2006/math"><mml:mi mathvariant="normal">Δ</mml:mi><mml:mi mathvariant="italic">^r f</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>)</mml:mo><mml:mo>=</mml:mo><mml:mo>∑</mml:mo><mml:mi>_</mml:mi><mml:mo>(</mml:mo><mml:mi>i</mml:mi><mml:mo>=</mml:mo><mml:mn>0</mml:mn><mml:mo>)</mml:mo><mml:mi mathvariant="italic">^r▒</mml:mi><mml:mo>(</mml:mo><mml:mo>(</mml:mo><mml:mo>-</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo><mml:mi mathvariant="italic">^i </mml:mi><mml:mo>(</mml:mo><mml:mi mathvariant="italic">r¦i</mml:mi><mml:mo>)</mml:mo><mml:mi>f</mml:mi><mml:mo>(</mml:mo><mml:mi>n</mml:mi><mml:mo>-</mml:mo><mml:mi>i</mml:mi><mml:mo>)</mml:mo><mml:mo>)</mml:mo><mml:mi> </mml:mi></mml:math> (For those with Word 2007.)Anonymous
November 07, 2007
Larry, the bottom row of your table is wrong. It should read 29009, 14330, 6096, 2028, 408Anonymous
November 08, 2007
Try it on 1, 2, 4, 8, 16, 32, ...Anonymous
November 08, 2007
The ability to create an infinite number of different polynomials which pass through a finite set of points is why I absolutely cannot ****ing stand those Mensa-style questions that say "Here is a sequence of numbers; which number comes next in the sequence?" I hate those questions and the people who ask them because they only accept one "correct" answer when in reality there are infinite correct answers. Pick a number and it is correct and you can generate a polynomial to prove it. The standard comeback from people who enjoy thinking they're clever because of Mensa-style tests is that you're expected to find the most simple or obvious answer but simplicity and obviousness are entirely subjective and have little to do with mathematics -- at least when it comes to judging something as correct or incorrect -- dag nammit. Personally, I'd find it more simple and obvious to apply the algorithm and find a polynomial than to attempt to work out what the person setting the question was thinking. </rant!>Anonymous
November 08, 2007
1 4 1 5 9 2 6 5 3 5 ...Anonymous
November 09, 2007
The comment has been removedAnonymous
November 11, 2007
@Leo Davidson I came here to post the same rant. Thanks for saving me the effort of typing!Anonymous
November 13, 2007
This following the foot steps of Ping of Death, now I'm afraid, very afraid.Anonymous
November 13, 2007
B.Y. Don't forget that Daniel was also the star of: http://blogs.msdn.com/larryosterman/archive/2004/05/07/128004.aspxAnonymous
November 18, 2007
> My son is SUCH a geek One down, one to go. Does he think? Oops, now you're going to disown him.Anonymous
November 21, 2007
I thought about this thing sometime ago... and I learned it have something to do with derivatives... now I finally know the name :) thxAnonymous
December 01, 2007
@Thursday, November 08, 2007 7:22 PM by Polly No Meal:
| | - 3 ?
- Anonymous
December 03, 2007
The question wasn't π - 3, the question was to find a polynomial which would evaluate to each number of a sequence. The answer was that there is no such polynomial. One proof was the individual digits of π - 3. Some computer geek already showed a powerful proof.