In 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.
The way you do this (I'll illustrate for a degree 3 polynomial) is to let y=P(x) be given by
Then, plug each of the (x,y) pairs into this equation in turn, giving you four linear equations in a, b, c, and d. Solve these using a matrix method such as Cramer's Rule, and you've got your coefficients.
In the case where you have a sequence, and you want to find its polynomial formula, there's a more practical method...
If you have a sequence that has a polynomial formula, then by taking the differences as you did, and then taking the differences of the differences, and then repeating this process until you get a constant... you will be able to find the highest degree coefficient of the polynomial.
If you take n successive differences before you get a constant difference, then the degree of the polynomial is n, and the coefficient of the xn term is that constant difference divided by n! (that is, n factorial).
In your example, you took successive differences twice, and arrived at a constant difference of 2. So the degree of the polynomial is 2, and the highest degree coefficient is 2/2! = 1.
Once you have the highest degree coefficient nailed, you can subtract it from the unknown polynomial, leaving you with a polynomial of degree n-1.
In your example, the highest degree term is x2, which is 1, 4, 9, 16, 25, ...
You can subtract it from your sequence, leaving you with 2, 4, 6, 8, 10, ...
Then, follow the same procedure to find the highest degree coefficient of this new sequence. In this way, you will build up all the coefficients of the polynomial function of the original sequence.
Following 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.
|Topic:||algebra (1 of 16), Read 32 times|
|Date:||Thursday, August 17, 2000 09:52 PM|
simplify the following.
|Topic:||algebra (2 of 16), Read 22 times|
|Date:||Friday, August 18, 2000 04:02 AM|
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
|Topic:||algebra (3 of 16), Read 26 times|
|Date:||Friday, August 18, 2000 10:09 AM|
medaline, here's a more interesting solution
there's a formula that states:
"the sum of the series
12 + 22 + 32 +42 +...+k2=k(k+1)(2k+1)/6"
so now let's look at your question, according to the formula above,
k(k+1)(2k+1)/6 = 12 + 22 + 32 + ... + k2
k(k+1)(2k+1)/6 + (k+1)2=
12 + 22 + 32 + ... + k2 + (k+1)2
now we can apply the formula again!
12 + 22 + 32 + ... + (k+1)2=
(k+1) ((k+1)+1) (2(k+1)+1)/6=
|Topic:||algebra (4 of 16), Read 31 times|
|Date:||Friday, August 18, 2000 11:36 AM|
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?
|Topic:||algebra (5 of 16), Read 20 times|
|Date:||Monday, August 21, 2000 12:08 AM|
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
=1/4 * n2 (n+1)2 + (n+1)3 = (n+1)2 * ( (n2)/4 +n+1)
=1/4* (n+1)2 * (n2+4n+4) = 1/4 * (n+1)2 * (n+2)^
= [1/2 * (n+1) ( (n+1)+1 )]2 which means the statement is also true for n+1
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=
[(n+1)5 -1 -n]/5 - n(n+1)(3n2 +7n +5)/6
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
|Topic:||algebra (6 of 16), Read 10 times|
|Date:||Monday, August 21, 2000 07:38 PM|
Here is the polynomial (unfactored) form of the sums of 0th powers through 8th powers:
The sum of n numbers of the form
1 is n
k is (n2+n)/2
k2 is (2n3+3n2+n)/6
k3 is (n4+2n3+n2)/4
k4 is (6n5+15n4+10n3-n)/30
k5 is (2n6+6n5+5n4-n2)/12
k6 is (6n7+21n6+21n5-7n3+n)/42
k7 is (3n8+12n7+14n6-7n4+2n2)/24
k8 is (10n9+45n8+60n7-42n5+20n3-3n)/90
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.
|Topic:||algebra (11 of 16), Read 8 times|
|Date:||Monday, August 21, 2000 11:55 PM|
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
|Topic:||algebra (12 of 16), Read 8 times|
|Date:||Tuesday, August 22, 2000 02:26 AM|
Here's an example.
Find the first 10 sums of k6, where k=1 to n.
(This is an seventh order polynomial, but we don't know what its coefficients are!)
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:
approx. sum of k6 - (1/7)n7
|1||1||- (1/7)n7||= 1|
|2||65||- (1/7)n7||= 47|
|3||794||- (1/7)n7||= 482|
|4||4890||- (1/7)n7||= 2549|
|5||20515||- (1/7)n7||= 9354|
|6||67171||- (1/7)n7||= 27180|
|7||184820||- (1/7)n7||= 67171|
|8||446964||- (1/7)n7||= 147371|
|9||978405||- (1/7)n7||= 295124|
|10||1978405||- (1/7)n7||= 549834|
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
(6n7 + 21n6 + 21n5 - 7n3 + n)/42
I used a common denominator of 42 to simplify the presentation of the polynomial.
|Topic:||algebra (14 of 14), Read 8 times|
|Date:||Tuesday, August 22, 2000 11:02 AM|
On 8/22/00 10:51:55 AM, J J wrote:
>but wait a sec, when you subtract
>"Now subtract (1/7)n7 from
>the sums, above, like this:
>n sum of k6 - (1/7)n7
>how did you get those
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
>coefficient of n6, do you
>subtract (1/2)n6 from the
>1,65,794,4890,20515... ?? or
>you subtract from
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
>notation stuffs is even simpler than this... but i
>personally think this method is really cooool, so i'd love to learn it.
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
|Topic:||algebra (16 of 16), Read 2 times|
|Date:||Tuesday, August 22, 2000 11:44 AM|
On 8/22/00 11:22:55 AM, J J wrote:
>okie, cool, I understand completely now. thank you very much
>i have microsoft excel at home, but I can't use it in
>any math contests, that's the problem.
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:
Let f(x) = ax4 + 17x3 - 42x2 + 11
f(11) - 4f(12) + 6f(13) - 4f(14) + f(15) = 12
What is the value of a?
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.
ax4 + bx3 + cx2 + dx + e
Too bad they're not all this easy!
-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
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
-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
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.
Eric Rowland, Rutgers University: Sums of Consecutive Like Powers
Finding Coefficients of formula for Sum of Squares - A method to find the sum of n³, or any higher power of n for that matter, as well as any other series that can be exactly fit by a polynomial of finite order.
Find the equation of an order n polynomial that passes through n points
Academic Decathlon State Competition Question 06 -- How many squares are on a checkerboard?
The webmaster and author of this Math Help site is Graeme McRae.