Finding Coefficients using the Method of Successive Differences

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
y=ax³+bx²+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ⁿ 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 x², 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.

Method of Successive Differences

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.

simplify the following.
k(k+1)(2k+1)/6 +(k+1)²
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² + 3² +4² +...+k²=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² + 3² + ... + k²

therefore,

k(k+1)(2k+1)/6 + (k+1)²=

1² + 2² + 3² + ... + k² + (k+1)²

now we can apply the formula again!

1² + 2² + 3² + ... + (k+1)²=

(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³ + 2³ + 3³ + ... + n³ = (n(n+1)/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³ + 2³ + 3³ + ... + n³ + (n+1)³ = (n(n+1)/2)² + (n+1)³
=1/4 * n² (n+1)² + (n+1)³ = (n+1)² * ( (n²)/4 +n+1)
=1/4* (n+1)² * (n²+4n+4) = 1/4 * (n+1)² * (n+2)^
= [1/2 * (n+1) ( (n+1)+1 )]² which means the statement is also true for n+1

therefore, the formula 1³ + 2³ + 3³ + ... + n³ = (n(n+1)/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⁴ + 2⁴ + 3⁴ + 4⁴ + ... + n⁴=
[(n+1)⁵ -1 -n]/5 - n(n+1)(3n² +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²+n)/2
k² is (2n³+3n²+n)/6
k³ is (n⁴+2n³+n²)/4
k⁴ is (6n⁵+15n⁴+10n³-n)/30
k⁵ is (2n⁶+6n⁵+5n⁴-n²)/12
k⁶ is (6n⁷+21n⁶+21n⁵-7n³+n)/42
k⁷ is (3n⁸+12n⁷+14n⁶-7n⁴+2n²)/24
k⁸ is (10n⁹+45n⁸+60n⁷-42n⁵+20n³-3n)/90

where 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 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 4n³ 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³ from a series with the form of

 1ⁿ+2ⁿ+3ⁿ+...+kⁿ ...

-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⁶, 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⁷ coefficient is 720/7!, or 1/7.

Now subtract (1/7)n⁷ from the sums, above, like this:
 

n	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)n⁶ 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⁶, where k runs from 1 to n is

(6n⁷ + 21n⁶ + 21n⁵ - 7n³ + 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⁷ from
>the sums, above, like this:
>
>n sum of k⁶ - (1/7)n⁷
>1 1-(1/7)n⁷=1
>2 65-(1/7)n⁷=47
>3 794-(1/7)n⁷=482
>...
>how did you get those
>1,47,482,...numbers??

They're not exact; rounded to the nearest integer 1-(1/7)n⁷ 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⁶, do you
>subtract (1/2)n⁶ 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⁴, 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)=n⁴+...

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⁴ + 17x³ - 42x² + 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⁴ 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⁴+bx³+cx²+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)

ax⁴ + bx³ + cx² + dx + e

Too bad they're not all this easy!

-4f(x + 1)

-4(a(x + 1)⁴ + b(x + 1)³ + c(x + 1)² + d(x + 1) + e)

-4(a(x⁴ + 4x³ + 6x² + 4x + 1) + b(x³ + 3x² + 3x + 1) + c(x² + 2x + 1) + d(x + 1) + e)

-4ax⁴ - 16ax³ - 24ax² - 16ax - 4a - 4bx³ - 12bx² - 12bx - 4b - 4cx² - 8cx - 4c - 4dx - 4d - 4e

6f(x + 2)

6(a(x + 2)⁴ + b(x + 2)³ + c(x + 2)² + d(x + 2) + e)

6(a(x⁴ + 8x³ + 24x² + 32x + 16) + b(x³ + 6x² + 12x + 8) + c(x² + 4x + 4) + d(x + 2) + e)

6ax⁴ + 48ax³ + 144ax² + 192ax + 96a + 6bx³ + 36bx² + 72bx + 48b + 6cx² + 24cx + 24c + 6dx + 12d + 6e

-4f(x + 3)

-4(a(x + 3)⁴ + b(x + 3)³ + c(x + 3)² + d(x + 3) + e)

-4(a(x⁴ + 12x³ + 54x² + 108x + 81) + b(x³ + 9x² + 27x + 27) + c(x² + 6x + 9) + d(x + 3) + e)

-4ax⁴ - 48ax³ - 216ax² - 432ax - 324a - 4bx³ - 36bx² - 108bx - 108b - 4cx² - 24cx - 36c - 4dx - 12d - 4e

f(x + 4)

a(x + 4)⁴ + b(x + 4)³ + c(x + 4)² + d(x + 4) + e

a(x⁴ + 16x³ + 96x² + 256x + 256) + b(x³ + 12x² + 48x + 64) + c(x² + 8x + 16) + d(x + 4) + e

ax⁴ + 16ax³ + 96ax² + 256ax + 256a + bx³ + 12bx² + 48bx + 64b + cx² + 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

Eric Rowland, Rutgers University: Sums of Consecutive Like Powers

Related pages in this website

Procedures

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.