|
|
|
|
|
Finding Coefficients using the Method of Successive DifferencesIn general, if you have n+1 points on the x-y plane, you can find a
polynomial y=P(x) of degree n that will pass through each of the points. Method of Successive DifferencesFollowing are excerpts from a bulletin board, called the mathboard on the algebra-online.com website. In this thread of conversation between myself and "J J", a Socratic dialog emerges, in which the method of finding the coefficients of an "black box" polynomial is revealed. By "black box", I mean that you have a polynomial function, or the first umpteen values of it, but you don't know or have access to the polynomial coefficients. I call this method the Method of Successive Differences. Its a method for finding the coefficients of a degree n polynomial, knowing only the values of any sequence of n+1 sequential values of the polynomial.
simplify the following.
k(k+1)(2k+1)/6 +(k+1)2
Write it:
k(k+1)(2k+1) (k+1)²
------------ + -------
6 1
The LCD is 6. The first
fraction already has a
denominator of 6. To make
the second also have a
denominator of 6,
multiply top and bottom
by 6
k(k+1)(2k+1) 6(k+1)²
------------ + -------
6 6
Write as one fraction
with denominator 6:
k(k+1)(2k+1) + 6(k+1)²
----------------------
6
Notice that (k+1) is a
common factor. Factor
it out.
(k+1)[k(2k+1) + 6(k+1)]
----------------------
6
(k+1)[2k² + k + 6k + 6]
----------------------
6
(k+1)[2k² + 7k + 6]
-------------------
6
Then, if you like,
factor the second
parentheses on top
(k+1)(2k+3)(k+2)
----------------
6
Edwin McCravy
Midlands Technical College
Columbia SC
medaline, here's a more interesting solution there's a formula that states:
so now let's look at your question, according to the formula above,
therefore,
now we can apply the formula again!
--jj
J J, that is interesting. In fact, the formula you used was proved inductively by Edwin McCravy in his answer! Now what is the sum of cubes? Prove that inductively. What is the sum of fourth powers? Fifth? nth?
Hi Graeme: I know that there's a formula for the sum of cubes, which is : 13 + 23 + 33 + ... + n3 = (n(n+1)/2)2 Here i'll prove it inductively: step A: obviously, when n=1, the statement is true step B: try to prove that if the statement is true for n, then it must be true for n+1:
13 + 23 + 33 + ... + n3
+ (n+1)3 = (n(n+1)/2)2 + (n+1)3 therefore, the formula 13 + 23 + 33 + ... + n3 = (n(n+1)/2)2 stands for all positive integer n i found the sum of the fourth powers using summation notation, but the proof is gonna be really messed up if i type it up on internet. so anyways, the formula for the fourth powers is :
14 + 24 + 34 + 44 +
... + n4= i haven't found a formula for the sum of the nth powers yet, i think that's a little too challenging for me. hehe --jj
Here is the polynomial (unfactored) form of the sums of 0th powers through 8th powers: The sum of n numbers of the form
There's no limit to the number of these that I can find using a fairly simple trick. If you have a function that you know is a polynomial, and you can calculate its value for n=1, 2, 3, etc. (or if someone has calculated them for you but is keeping secret from you the polynomial coefficients) then you can find the differences between successive values of the function, and then the second-order differences, the third-order, etc. until you come to a set of constant differences. Note the "order" of the differences that are constant. Divide that constant number by the order factorial to get the coefficient of that order. For example, if the third differences are 24, then divide 24 by 3!, which results in 4 -- then 4 is the third order coefficient of the polynomial you're studying. Now subtract 4n3 from the polynomial you're studying, and note that the second order differences are now constant. Repeat the process to find the second order coefficient, then the first order, and finally the constant term. Each time, subtracting the newly found polynomial term from the polynomial under study until you reach all zeros. This delightful approach can be used to find the polynomial that equals the sum of any series that you know in advance has a polynomial sum.
Graeme, thanx again, for the warm help. but sorry, i don't really get your explanation. i think the problem is that i dont understand what you mean by "order". and how can you subtract 4n3 from a series with the form of 1n+2n+3n+...+kn ... -jj
Here's an example.
Find the first 10 sums of k6, where k=1 to n.
Now take their first differences, then the second differences (which are the differences of the differences) etc. until you find constant differences. When you do that, you'll find the seventh differences are constant, and equal to 720. Now you know the n7 coefficient is 720/7!, or 1/7.
Now subtract (1/7)n7 from the sums, above, like this:
Now find differences of this new set of numbers, and you'll see constant sixth differences of 360. Divide 360/6!, and you'll get the sixth order coefficient, 1/2. Now, subtract (1/2)n6 from each of these numbers. The constant fifth differences are 60. 60/5! is 1/2. Repeating this procedure, we get -- one by one -- the coefficients of a polynomial, which when subtracted from the sums of seventh powers ultimately gives us the constant zeros. This is how we find the mystery polynomial. It sounds like an awful lot of computing, but if you use a spreadsheet, it doesn't take much time at all. The final result is that the sum of numbers k6, where k runs from 1 to n is
I used a common denominator of 42 to simplify the presentation of the polynomial.
On 8/22/00 10:51:55 AM, J J wrote: They're not exact; rounded to the nearest integer 1-(1/7)n7 is 6/7, which I rounded to 1. If you use a spreadsheet to do your calculations, the numbers are floating point numbers, so the rounding error is not very bad.
>and after you know the The second thing. You have an unknown polynomial of seventh order, from which you subtract the seventh order term once you know it. That leaves an unknown polynomial of sixth order. You repeat the process, subtracting both the seventh and sixth order terms (once you know them) leaving an unknown fifth order polynomial. Etcetera, etcetera.
>that IS an awful lot of computing...using summation I strongly recommend getting ahold of a spreadsheet. Microsoft Excel is good, but if you can't afford it, StarOffice is a free alternative -- check out www.sun.com. >thanx very very very... much You're welcome!
On 8/22/00 11:22:55 AM, J J wrote: Yes, I see. If the polynomial is order 3 or 4, you should be able to do the calculations with a simple calculator, which, presumably, you can use in math contests. To see for yourself why it works, make a table of cubes, then take first, second, and third differences. You'll see the third differences are 6, and 6 is 3!. Make a table of fourth powers, and take the first, second, third, and fourth differences. You'll see the fourth differences are 24, and 24 is 4! If you make a table of 7n4, you'll see that the fourth differences are (7)(4!). Any polynomial is a sum of such tables. The final, constant, differences are influenced only by the highest order term in the polynomial, so this method allows you to quickly find its coefficient. By subtracting this term from the numbers under study, you're left with a one-lower-order polynomial, with which you can repeat the process. Now here's something fun for you to try: Make a table of fourth powers, or use any polynomial f(n)=n4+... Now calculate the magic sum
You'll see it's 4!, or 24. Calculate the magic sum
Again, you'll see it's 24. Do you recognize the multipliers in this magic sum as the fourth order binomial coefficients? What you're doing here is calculating the fourth differences without first calculating the first, second, and third differences. This is the sort of puzzle that's likely to show up in a math competition. It'll be phrased like this, perhaps:
While your less knowledgeable classmates are struggling with 144 overflowing their calculators, you'll be dividing 12 by 24, and moving on to the next problem!
I feel compelled to show you that if f(x)=ax4+bx3+cx2+dx+e, then f(x)-4f(x+1)+6f(x+2)-4f(x+3)+f(x+4)=24a. It's a big mess at first, but everything -- I mean everything -- cancels, except 24a. Its an amazing sight to behold. Let's find f(x) - 4f(x+1) + 6f(x+2) - 4f(x+3) + f(x+4) First, I'll do each term separately.
f(x)ax4 + bx3 + cx2 + dx + e Too bad they're not all this easy!
-4f(x + 1)-4(a(x + 1)4 + b(x + 1)3 + c(x + 1)2 + d(x + 1) + e) -4(a(x4 + 4x3 + 6x2 + 4x + 1) + b(x3 + 3x2 + 3x + 1) + c(x2 + 2x + 1) + d(x + 1) + e) -4ax4 - 16ax3 - 24ax2 - 16ax - 4a - 4bx3 - 12bx2 - 12bx - 4b - 4cx2 - 8cx - 4c - 4dx - 4d - 4e
6f(x + 2)6(a(x + 2)4 + b(x + 2)3 + c(x + 2)2 + d(x + 2) + e) 6(a(x4 + 8x3 + 24x2 + 32x + 16) + b(x3 + 6x2 + 12x + 8) + c(x2 + 4x + 4) + d(x + 2) + e) 6ax4 + 48ax3 + 144ax2 + 192ax + 96a + 6bx3 + 36bx2 + 72bx + 48b + 6cx2 + 24cx + 24c + 6dx + 12d + 6e
-4f(x + 3)-4(a(x + 3)4 + b(x + 3)3 + c(x + 3)2 + d(x + 3) + e) -4(a(x4 + 12x3 + 54x2 + 108x + 81) + b(x3 + 9x2 + 27x + 27) + c(x2 + 6x + 9) + d(x + 3) + e) -4ax4 - 48ax3 - 216ax2 - 432ax - 324a - 4bx3 - 36bx2 - 108bx - 108b - 4cx2 - 24cx - 36c - 4dx - 12d - 4e
f(x + 4)a(x + 4)4 + b(x + 4)3 + c(x + 4)2 + d(x + 4) + e a(x4 + 16x3 + 96x2 + 256x + 256) + b(x3 + 12x2 + 48x + 64) + c(x2 + 8x + 16) + d(x + 4) + e ax4 + 16ax3 + 96ax2 + 256ax + 256a + bx3 + 12bx2 + 48bx + 64b + cx2 + 8cx + 16c + dx + 4d + e
Now I'll take the final expansion of each term, above, collect like terms and add them up:
It's pretty amazing to behold, don't you think? An exercise left to the reader: generalize this proof for polynomials of any order. Internet References
Related pages in this website
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
The webmaster and author of the Math
Help site is Graeme McRae.
|
