
In general, if you have n+1 points on the xy 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
y=ax^{3}+bx^{2}+cx+d
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.
Here's how.
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 x^{n} 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 n1.
In your example, the highest degree term is x^{2}, 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 algebraonline.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 
Conf:  Math Help 
From:  Medaline Lee 
Date:  Thursday, August 17, 2000 09:52 PM 
simplify the following.
k(k+1)(2k+1)/6 +(k+1)^{2}
please help!
Topic:  algebra (2 of 16), Read 22 times 
Conf:  Math Help 
From:  Edwin McCravy 
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 
Conf:  Math Help 
From:  J J 
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
1^{2} + 2^{2} + 3^{2} +4^{2} +...+k^{2}=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 = 1^{2 }+ 2^{2 }+ 3^{2 }+ ... + k^{2}
therefore,
k(k+1)(2k+1)/6 + (k+1)^{2}=
1^{2 }+ 2^{2} + 3^{2} + ... + k^{2 }+ (k+1)^{2}
now we can apply the formula again!
1^{2 }+ 2^{2 }+ 3^{2 }+ ... + (k+1)^{2}=
(k+1) ((k+1)+1) (2(k+1)+1)/6=
(k+1)(k+2)(2k+3)/6
jj
Topic:  algebra (4 of 16), Read 31 times 
Conf:  Math Help 
From:  Graeme McRae 
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? n^{th}?
Topic:  algebra (5 of 16), Read 20 times 
Conf:  Math Help 
From:  J J 
Date:  Monday, August 21, 2000 12:08 AM 
Hi Graeme:
I know that there's a formula for the sum of cubes, which is :
1^{3 }+ 2^{3 }+ 3^{3 }+ ... + n^{3 }= (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:
1^{3 }+ 2^{3 }+ 3^{3 }+ ... + n^{3
}+ (n+1)^{3 }= (n(n+1)/2)^{2} + (n+1)^{3}
=1/4 * n^{2} (n+1)^{2} + (n+1)^{3 }= (n+1)^{2} * ( (n^{2})/4 +n+1)
=1/4* (n+1)^{2} * (n^{2}+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 1^{3 }+ 2^{3 }+ 3^{3 }+ ... + n^{3 }= (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 :
1^{4 }+ 2^{4 }+ 3^{4 }+ 4^{4 }+
... + n^{4}=
[(n+1)^{5} 1 n]/5  n(n+1)(3n^{2} +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
jj
Topic:  algebra (6 of 16), Read 10 times 
Conf:  Math Help 
From:  Graeme McRae 
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 (n^{2}+n)/2
k^{2} is (2n^{3}+3n^{2}+n)/6
k^{3} is (n^{4}+2n^{3}+n^{2})/4
k^{4} is (6n^{5}+15n^{4}+10n^{3}n)/30
k^{5} is (2n^{6}+6n^{5}+5n^{4}n^{2})/12
k^{6} is (6n^{7}+21n^{6}+21n^{5}7n^{3}+n)/42
k^{7} is (3n^{8}+12n^{7}+14n^{6}7n^{4}+2n^{2})/24
k^{8} is (10n^{9}+45n^{8}+60n^{7}42n^{5}+20n^{3}3n)/90where k=1,2,…,n
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 secondorder differences, the thirdorder, 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 4n^{3} 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 
Conf:  Math Help 
From:  J J 
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 4n^{3} from a series with the form of
1^{n}+2^{n}+3^{n}+...+k^{n} ...
jj
Topic:  algebra (12 of 16), Read 8 times 
Conf:  Math Help 
From:  Graeme McRae 
Date:  Tuesday, August 22, 2000 02:26 AM 
Here's an example.
Find the first 10 sums of k^{6}, where k=1 to n.
(This is an seventh order polynomial, but we don't know what its coefficients are!)
n  sum 
1  1 
2  65 
3  794 
4  4890 
5  20515 
6  67171 
7  184820 
8  446964 
9  978405 
10  1978405 
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 n^{7} coefficient is 720/7!, or 1/7.
Now subtract (1/7)n^{7} from the sums, above, like this:
n 
approx. sum of k^{6}  (1/7)n^{7}  
1  1   (1/7)n^{7}  = 1 
2  65   (1/7)n^{7}  = 47 
3  794   (1/7)n^{7}  = 482 
4  4890   (1/7)n^{7}  = 2549 
5  20515   (1/7)n^{7}  = 9354 
6  67171   (1/7)n^{7}  = 27180 
7  184820   (1/7)n^{7}  = 67171 
8  446964   (1/7)n^{7}  = 147371 
9  978405   (1/7)n^{7}  = 295124 
10  1978405   (1/7)n^{7}  = 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)n^{6} 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 k^{6}, where k runs from 1 to n is
(6n^{7} + 21n^{6} + 21n^{5}  7n^{3} + n)/42
I used a common denominator of 42 to simplify the presentation of the polynomial.
Topic:  algebra (14 of 14), Read 8 times 
Conf:  Math Help 
From:  Graeme McRae 
Date:  Tuesday, August 22, 2000 11:02 AM 
On 8/22/00 10:51:55 AM, J J wrote:
>awesome...
>but wait a sec, when you subtract
>"Now subtract (1/7)n^{7} from
>the sums, above, like this:
>
>n sum of k^{6}  (1/7)n^{7}
>1 1(1/7)n^{7}=1
>2 65(1/7)n^{7}=47
>3 794(1/7)n^{7}=482
>...
>how did you get those
>1,47,482,...numbers??
They're not exact; rounded to the nearest integer 1(1/7)n^{7} 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 n^{6}, do you
>subtract (1/2)n^{6} from the
>original
>1,65,794,4890,20515... ?? or
>you subtract from
>1,47,482,2549,9354...??
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
>jj
You're welcome!
Topic:  algebra (16 of 16), Read 2 times 
Conf:  Math Help 
From:  Graeme McRae 
Date:  Tuesday, August 22, 2000 11:44 AM 
On 8/22/00 11:22:55 AM, J J wrote:
>Graeme,
>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 7n^{4}, 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 onelowerorder 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)=n^{4}+...
Now calculate the magic sum
f(1)4*f(2)+6*f(3)4*f(4)+f(5)
You'll see it's 4!, or 24.
Calculate the magic sum
f(11)4*f(12)+6*f(13)4*f(14)+f(15)
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) = ax^{4 }+ 17x^{3 } 42x^{2 }+ 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 14^{4} 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)=ax^{4}+bx^{3}+cx^{2}+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.
ax^{4 }+ bx^{3 }+ cx^{2 }+ 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(x^{4} + 4x^{3} + 6x^{2} + 4x + 1) + b(x^{3} + 3x^{2} + 3x + 1) + c(x^{2} + 2x + 1) + d(x + 1) + e)
4ax^{4}  16ax^{3}  24ax^{2}  16ax  4a  4bx^{3}  12bx^{2}  12bx  4b  4cx^{2}  8cx  4c  4dx  4d  4e
6(a(x + 2)^{4} + b(x + 2)^{3} + c(x + 2)^{2} + d(x + 2) + e)
6(a(x^{4} + 8x^{3} + 24x^{2} + 32x + 16) + b(x^{3} + 6x^{2} + 12x + 8) + c(x^{2} + 4x + 4) + d(x + 2) + e)
6ax^{4} + 48ax^{3} + 144ax^{2} + 192ax + 96a + 6bx^{3} + 36bx^{2} + 72bx + 48b + 6cx^{2} + 24cx + 24c + 6dx + 12d + 6e
4(a(x + 3)^{4} + b(x + 3)^{3} + c(x + 3)^{2} + d(x + 3) + e)
4(a(x^{4} + 12x^{3} + 54x^{2} + 108x + 81) + b(x^{3} + 9x^{2} + 27x + 27) + c(x^{2} + 6x + 9) + d(x + 3) + e)
4ax^{4}  48ax^{3}  216ax^{2}  432ax  324a  4bx^{3}  36bx^{2}  108bx  108b  4cx^{2}  24cx  36c  4dx  12d  4e
a(x + 4)^{4} + b(x + 4)^{3} + c(x + 4)^{2} + d(x + 4) + e
a(x^{4} + 16x^{3} + 96x^{2} + 256x + 256) + b(x^{3} + 12x^{2} + 48x + 64) + c(x^{2} + 8x + 16) + d(x + 4) + e
ax^{4} + 16ax^{3} + 96ax^{2} + 256ax + 256a + bx^{3} + 12bx^{2} + 48bx + 64b + cx^{2} + 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.