My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
December 9th, 2017, 09:24 PM   #1
jks
Senior Member
 
jks's Avatar
 
Joined: Jul 2012
From: DFW Area

Posts: 625
Thanks: 88

Math Focus: Electrical Engineering Applications
Method of finding polynomial series coefficients?

Recently, at work, an application came up where I had a series that I suspected was generated by successive terms of a polynomial and I needed to find the coefficients of that polynomial, similar to the problem in this thread (Reference 1). I give another sample calculation in Reference 1, with a little bit more explanation than presented below relating to the coefficients of the numbers raised to a power.

I was aware of taking the differences until a constant is reached (due to previous posts on this forum), which gives the order of the polynomial. I did this and used the linear equations to get the result (there was a cubic term and a linear term).

Then I started playing around and I think I found a way to get the coefficients from the difference triangle. The method relies on two properties of Pascal's Triangle (PT), which I ask about here (Reference 2).

While I am not certain of these properties of PT for all rows, I have calculated them to be true up to row 100 (for the values that I am interested in) for the purposes of the method that I am about to describe. This is a lot higher than any practical polynomial degree that I would need to solve.

Anyway, I would like to attempt to describe the method and show by a fourth order polynomial why it just might work.

---------------------------------

So, suppose we have the following series given by row 0, and the differences:

$\displaystyle \large {\begin{array}{c c}
& n & 1 & & 2 & & 3 & & 4 & & 5 & & 6 \\
row \\
0 & & 28 & & 101 & & 320 & & 823 & & 1796 & & 3473 \\
1 & & & 73 & & 219 & & 503 & & 973 & & 1677 \\
2 & & & & 146 & & 284 & & 470 & & 704 \\
3 & & & & & 138 & & 186 & & 234 \\
4 & & & & & & 48 & & 48 \\
\end{array}}$

We can see that we have a fourth order polynomial since 4 subtractions were needed to get a constant term (I would take more terms just to be sure in a series that I was not familiar with). So we are looking for:

$\displaystyle \large a \cdot n^4 + b \cdot n^3 + c \cdot n^2 + d \cdot n +
e$

I am going to go term by term to get to the first (left-most) constant of 48, and honestly, you can probably skip on down to where you start seeing braces inside $\LaTeX$.

----------

$\displaystyle \large {\begin{align*} 973 &= a \cdot 5^4 + b \cdot 5^3 + c \cdot 5^2 +d \cdot 5 +e - \left (a \cdot 4^4 + b \cdot 4^3 + c \cdot 4^2 +d \cdot 4 +e \right) \\
&= a (5^4 - 4^4) + b (5^3-4^3)+c(5^2-4^2)+d
\end{align*}}$

----------

$\displaystyle \large 503 = a (4^4 - 3^4) + b (4^3-3^3)+c(4^2-3^2)+d$

----------

$\displaystyle \large 470 = a (5^4 - 2 \cdot 4^4 + 3^4) + b (5^3 - 2 \cdot 4^3 + 3^3)+c(5^2 - 2 \cdot 4^2 + 3^2)$

----------

$\displaystyle \large 219 = a (3^4 - 2^4) + b (3^3-2^3)+c(3^2-2^2)+d$

----------

$\displaystyle \large 284 = a (4^4 - 2 \cdot 3^4 + 2^4) + b (4^3 - 2 \cdot 3^3 + 2^3)+c(4^2 - 2 \cdot 3^2 + 2^2)$

----------

$\displaystyle \large 186 = a (5^4 - 3 \cdot 4^4 + 3 \cdot 3^4 - 2^4) + b (5^3 - 3 \cdot 4^3 + 3 \cdot 3^3 - 2^3)+c(5^2 - 3 \cdot 4^2 + 3 \cdot 3^2 - 2^2)$

----------

$\displaystyle \large 73 = a (2^4 - 1^4) + b (2^3-1^3)+c(2^2-1^2)+d$

----------

$\displaystyle \large 146 = a (3^4 - 2 \cdot 2^4 + 1^4) + b (3^3 - 2 \cdot 2^3 + 1^3)+c(3^2 - 2 \cdot 2^2 + 1^2)$

----------

$\displaystyle \large 138 = a (4^4 - 3 \cdot 3^4 + 3 \cdot 2^4 - 1^4) + b (4^3 - 3 \cdot 3^3 + 3 \cdot 2^3 - 1^3)+c(4^2 - 3 \cdot 3^2 + 3 \cdot 2^2 - 1^2)$

--------------------

$\displaystyle \large { \begin{align*}48 &= a \ \underbrace{(5^4 - 4 \cdot 4^4 + 6 \cdot 3^4 - 4 \cdot 2^4 + 1^4)}_{4! \text{ per Reference 2}} \\
&+ b \ \underbrace{(5^3 - 4 \cdot 4^3 + 6 \cdot 3^3 - 4 \cdot 2^3 + 1^3)}_{0 \text{ per Reference 2}} \\
&+c \ \underbrace{(5^2 - 4 \cdot 4^2 + 6 \cdot 3^2 - 4 \cdot 2^2 + 1^2)}_{0 \text{ per Reference 2}} \end{align*}}$

So:

$\displaystyle a=\frac{48}{4!}=2$

--------------------

Back to 138 with $a=2$:

$\displaystyle \large { \begin{align*} 138 &= \underbrace{2(4^4 - 3 \cdot 3^4 + 3 \cdot 2^4 - 1^4)}_{120} \\
&+ b \ \underbrace{(4^3 - 3 \cdot 3^3 + 3 \cdot 2^3 - 1^3)}_{3! \text{ per Reference 2}} \\
&+ c \ \underbrace{(4^2 - 3 \cdot 3^2 + 3 \cdot 2^2 - 1^2)}_{0 \text{ per Reference 2}}
\end{align*}}$

So to get $b$:

$\displaystyle \large b=\frac{138-120}{3!}=3$

--------------------

Back to 146 with $a=2$ and $b=3$:

$\displaystyle \large { \begin{align*} 146 &= \underbrace{2(3^4 - 2 \cdot 2^4 + 1^4) + 3(3^3 - 2 \cdot 2^3 + 1^3)}_{136} \\
&+ c \ \underbrace{(3^2 - 2 \cdot 2^2 + 1^2)}_{2! \text{ per Reference 2}}
\end{align*}}$

So to get $c$:

$\displaystyle \large c=\frac{146-136}{2!}=5$

--------------------

$\displaystyle \large 73 = 2(2^4 - 1^4) + 3(2^3-1^3)+5(2^2-1^2)+d$

$\displaystyle \large d=7$

--------------------

$\displaystyle \large 28 = 2+3+5+7+e$

$\displaystyle \large e=11$

---------------------------------

So the generating polynomial is:

$\displaystyle 2 \cdot n^4 + 3 \cdot n^3 + 5 \cdot n^2 + 7 \cdot n + 11$

which is easily verified.
jks is offline  
 
June 17th, 2018, 11:58 AM   #2
jks
Senior Member
 
jks's Avatar
 
Joined: Jul 2012
From: DFW Area

Posts: 625
Thanks: 88

Math Focus: Electrical Engineering Applications
Update: I now think that finding the unknown coefficients of a polynomial generated sequence is quite easy - basically all that is required is to construct the difference triangle and then use a look-up table, available on the OEIS, with some simple calculations. I wrote a paper on it but as I state in the paper, I am an engineer, not a mathematician, and I will leave it to others who are more experienced and capable to review and formalize the method (if indeed it is correct). In the meantime, I feel quite comfortable in employing the method, as results may always be checked.

The method uses a diagonal of the difference triangle and either OEIS A019538 or OEIS A028246 (go down to the "EXAMPLE" section for each sequence to see the sequence as a table in order to use the method), depending upon whether the sequence is generated starting at 0 or 1. As will be demonstrated (but certainly not proven), the method may be extended to sequences with an arbitrary starting number (including integers other than 0 or 1) and an arbitrary differential.

For a little background on using other methods to determine the generating polynomial, please refer to this thread and for a taste of the math involved in using the method described below please refer to this other thread. (The paper reference above goes into more detail).

I would like to demonstrate the ease of using the method here. Let's consider the sequence generated by:

$\displaystyle 2.0x^5+7.0x^4+1.0x^3+8.0x^2+2.0x+8.0, \ x \in 0..6$

(I added the ".0" to each coefficient to make it clear that the coefficients need not be integers - but it is easier to demonstrate the method with integer coefficients).

The difference triangle is:

\begin{array}{cccccccccccccc}
0 & & 1 & & 2 & & 3 & & 4 & & 5 & & 6 & \leftarrow x \\
8 & & 28 & & 228 & & 1166 & & 4048 & & 10968 & & 25148 & \text{row } 0 \\
& 20 & & 200 & & 938 & & 2882 & & 6920 & & 14180 \\
& & 180 & & 738 & & 1944 & & 4038 & & 7260 \\
& & & 558 & & 1206 & & 2094 & & 3222 \\
& & & & 648 & & 888 & & 1128 \\
& & & & & 240 & & 240 & & & & & & \text{row } 5
\end{array}

By convention, the first row (the sequence values) is row 0 and the first difference row is row 1, etc. Since 5 rows of differences were taken before a (non-zero) constant was reached, we know that we are looking for a fifth order polynomial, $c_5x^5+c_4x^4+c_3x^3+c_2x^2+c_1x+c_0$. First, it is assumed (or perhaps we are given) that we start at $x=0$. Then we use the leftmost diagonal of the difference triangle and A019538 as given in the table below (with zeros for $n<k$):

\begin{array}{l|rrrrrrrrr}
n \downarrow \ \ k \rightarrow & \ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
2 & 1 & 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
3 & 1 & 6 & 6 & 0 & 0 & 0 & 0 & 0 & 0 \\
4 & 1 & 14 & 36 & 24 & 0 & 0 & 0 & 0 & 0 \\
5 & 1 & 30 & 150 & 240 & 120 & 0 & 0 & 0 & 0 \\
6 & 1 & 62 & 540 & 1560 & 1800 & 720 & 0 & 0 & 0 \\
7 & 1 & 126 & 1806 & 8400 & 16800 & 15120 & 5040 & 0 & 0 \\
8 & 1 & 254 & 5796 & 40824 & 126000 & 191520 & 141120 & 40320 & 0 \\
9 & 1 & 510 & 18150 & 186480 & 834120 & 1905120 & 2328480 & 1451520 & 362880 \\
\end{array}

We will start at row=5 in the difference triangle and column $k=5$ in A019538. We will move up each column in A019538, assigning the value for each $n \in 1..5$ in the $k^{th}$ column as a multiplier to $c_n$ and equate these to the leftmost value in row $k$ of the difference triangle. We will then move back to $k=4$ in A019538 and row=4 in the difference triangle, and so on until $k=\text{row}=1$. Along the way we easily calculate each $c_{n=k}$ as we go as these are the only unknowns. This is shown as follows, with the A019538 multipliers in parenthesis (multipliers of 0 are not shown):

\begin{array}{ccccccccccccccc}
240 & = & c_5(120) & & & & & & & & & \Rightarrow & c_5 & = & 2 \\
648 & = & 2(240) & + & c_4(24) & & & & & & & \Rightarrow & c_4 & = & 7 \\
558 & = & 2(150) & + & 7(36) & + & c_3(6) & & & & & \Rightarrow & c_3 & = & 1 \\
180 & = & 2(30) & + & 7(14) & + & 1(6) & + & c_2(2) & & & \Rightarrow & c_2 & = & 8 \\
20 & = & 2(1) & + & 7(1) & + & 1(1) & + & 8(1) & + & c_1(1) & \Rightarrow & c_1 & = & 2
\end{array}

Since we started with $x=0$, we know that $c_0=8$, which is the first value in row 0 of the difference triangle and the solution is complete. As can be seen, this process turns the rows of A019538 into columns, and the columns of A019538 into rows, when presented in the manner shown.



Next, let's suppose that we are given or assume that $x=1$ was used to generate the same sequence (imagine the leftmost diagonal in the difference triangle above is not there, as given below):

\begin{array}{cccccccccccc}
1 & & 2 & & 3 & & 4 & & 5 & & 6 & \leftarrow x \\
28 & & 228 & & 1166 & & 4048 & & 10968 & & 25148 & \text{row } 0 \\
& 200 & & 938 & & 2882 & & 6920 & & 14180 \\
& & 738 & & 1944 & & 4038 & & 7260 \\
& & & 1206 & & 2094 & & 3222 \\
& & & & 888 & & 1128 \\
& & & & & 240 & & & & & & \text{row } 5
\end{array}

Normally, of course, we would take at least one more element to verify the constant of 240, but in this case I will not since it was shown above. Since we started at $x=1$, we use A028246 along with the leftmost diagonal in the difference triangle. A028246 is shown in the table below (with zeros for $n<k$):

\begin{array}{l|rrrrrrrrr}
n \downarrow \ \ k \rightarrow & \ 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline
1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
2 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\
3 & 1 & 3 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\
4 & 1 & 7 & 12 & 6 & 0 & 0 & 0 & 0 & 0 \\
5 & 1 & 15 & 50 & 60 & 24 & 0 & 0 & 0 & 0 \\
6 & 1 & 31 & 180 & 390 & 360 & 120 & 0 & 0 & 0 \\
7 & 1 & 63 & 602 & 2100 & 3360 & 2520 & 720 & 0 & 0 \\
8 & 1 & 127 & 1932 & 10206 & 25200 & 31920 & 20160 & 5040 & 0 \\
9 & 1 & 255 & 6050 & 46620 & 166824 & 317520 & 332640 & 181440 & 40320 \\
\end{array}

We will start at row=5 in the difference triangle and column $k=6$ in A028246. We will move up each column in A028246, assigning the value for each $n \in 1..6$ in the $k^{th}$ column as a multiplier to $c_{n-1}$ and equate these to the leftmost value in row $k-1$ of the difference triangle. We will then move back to $k=5$ in A028246 and row=4 in the difference triangle, and so on until $k=1$, row=0. Along the way we easily calculate each $c_{n-1=k-1}$ as we go as these are the only unknowns. This is shown as follows, with the A028246 multipliers in parenthesis (multipliers of 0 are not shown):

\begin{array}{ccccccccccccccccc}
240 & = & c_5(120) & & & & & & & & & & & \Rightarrow & c_5 & = & 2 \\
888 & = & 2(360) & + & c_4(24) & & & & & & & & & \Rightarrow & c_4 & = & 7 \\
1206 & = & 2(390) & + & 7(60) & + & c_3(6) & & & & & & & \Rightarrow & c_3 & = & 1 \\
738 & = & 2(180) & + & 7(50) & + & 1(12) & + & c_2(2) & & & & & \Rightarrow & c_2 & = & 8 \\
200 & = & 2(31) & + & 7(15) & + & 1(7) & + & 8(3) & + & c_1(1) & & & \Rightarrow & c_1 & = & 2 \\
28 & = & 2(1) & + & 7(1) & + & 1(1) & + & 8(1) & + & 2(1) & + & c_0(1) & \Rightarrow & c_0 & = & 8
\end{array}

And the solution is complete.



Finally, the method is extended to sequences with an arbitrary starting number and an arbitrary differential. Let's consider the sequence generated by:

$\displaystyle 3x^4+1x^3+4x^2+1x+6, \ x \in 3.3,3.4..3.8$

Let us assign $g(x)=10(x-3.3)$ and then construct the difference triangle:

\begin{array}{cccccccccccc}
3.3 & & 3.4 & & 3.5 & & 3.6 & & 3.7 & & 3.8 & \leftarrow x \\
0 & & 1 & & 2 & & 3 & & 4 & & 5 & \leftarrow g(x) \\
444.5733 & & 495.8448 & & 551.5625 & & 611.9808 & & 677.3613 & & 747.9728 \\
& 51.2715 & & 55.7177 & & 60.4183 & & 65.3805 & & 70.6115 \\
& & 4.4462 & & 4.7006 & & 4.9622 & & 5.231 \\
& & & 0.2544 & & 0.2616 & & 0.2688 \\
& & & & 0.0072 & & 0.0072
\end{array}

Since $g(x)$ starts at 0, we use A019538 and we get:

\begin{array}{ccccccccccccc}
0.0072 & = & c_4(24) & & & & & & & \Rightarrow & c_4 & = & 0.0003 \\
0.2544 & = & 0.0003(36) & + & c_3(6) & & & & & \Rightarrow & c_3 & = & 0.0406 \\
4.4462 & = & 0.0003(14) & + & 0.0406(6) & + & c_2(2) & & & \Rightarrow & c_2 & = & 2.0992 \\
51.2715 & = & 0.0003(1) & + & 0.0406(1) & + & 2.0992(1) & + & c_1(1) & \Rightarrow & c_1 & = & 49.1314 \\
\end{array}

And $c_0=444.5733$, the first element in row 0 of the difference triangle. We could compute the sequence values for other values of $x$ by computing $g(x)$ and using these coefficients. We could also symbolically evaluate:

$\displaystyle 0.0003(g(x))^4+0.0406(g(x))^3+2.0992(g(x))^2+49.13 14(g(x))+444.5733$

and get:

$\displaystyle 3x^4+1x^3+4x^2+1x+6$

(per W|A) to use the values of $x$ directly.

Obviously, the same method may be used for integer generated sequences with a starting integer value other than 0 or 1 by making a substitution of $g(x)=x-y$, with $y$ as the appropriate integer. The value of $y$ will depend upon whether A019538 or A028246 was used in the calculation, and upon the starting integer value of the sequence.
jks is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
coefficients, finding, method, polynomial, series



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Hey, need help finding series coefficients Lior Salem Calculus 1 December 9th, 2015 01:44 AM
Finding the coefficients of a polynomial - Octave biket Computer Science 1 January 20th, 2013 09:27 AM
Finding roots of Polynomial with real coefficients domaPL Real Analysis 1 January 12th, 2008 10:28 AM
Finding roots of Polynomial with real coefficients domaPL Number Theory 0 December 31st, 1969 04:00 PM
Finding the coefficients of a polynomial - Octave biket Algebra 0 December 31st, 1969 04:00 PM





Copyright © 2018 My Math Forum. All rights reserved.