 My Math Forum Method of finding polynomial series coefficients?
 User Name Remember Me? Password

 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 Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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

Copyright © 2019 My Math Forum. All rights reserved.      