My Math Forum Method of finding polynomial series coefficients?

 Number Theory Number Theory Math Forum

 December 9th, 2017, 09:24 PM #1 Senior Member     Joined: Jul 2012 From: DFW Area Posts: 635 Thanks: 96 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.
 June 17th, 2018, 11:58 AM #2 Senior Member     Joined: Jul 2012 From: DFW Area Posts: 635 Thanks: 96 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

 Tags coefficients, finding, method, polynomial, series

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Lior Salem Calculus 1 December 9th, 2015 01:44 AM biket Computer Science 1 January 20th, 2013 09:27 AM domaPL Real Analysis 1 January 12th, 2008 10:28 AM domaPL Number Theory 0 December 31st, 1969 04:00 PM biket Algebra 0 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top