2019-07-13, 11:55 | #1 |
Feb 2017
Nowhere
101111111110_{2} Posts |
Polynomial interpolation of an integer sequence
In view of certain recent postings to the Mersenne Forum, it occurred to me to write up something about polynomial interpolation, by way of salvaging something worthwhile from the wreckage.
Instead of the general Lagrange interpolation formula, it occurred to me to use an approach specifically adapted to the case when the x-values of the points (x, y) to be interpolated are consecutive integers. In this situation, the interpolation is surprisingly simple. Given a sequence of integers n_{1}, n_{2}, n_{3},... and an index k, there is a straightforward way to describe a polynomial f = f(x) in Q[x] of degree less than k, for which f(1) = n_{1}, f(2) = n_{2}, ..., and f(k) = n_{k}. This uses the "binomial coefficient" polynomials f_{0}(x) = 1, f_{1}(x) = x, f_{2}(x) = x*(x-1)/2!, etc where f_{k}(x) = binomial(x,k) = x(x-1)...(x - (k-1))/k! We note that (1) f_{k}(x) assumes integer values for integer values of x, (2) f_{k}(m) = 0 for m = 0, 1, ..., k-1 and f_{k}(k) = 1, and (3) f_{k}(x) has degree k. We can thus interpolate the points (0, n_{1}) and (1, n_{2}) by taking f(x) = n_{1}*f_{0}(x) + (n2 - n1)*f_{1}(x). We can interpolate (2, n_{3}) by adding an appropriate multiple of f_{2}(x); we find that f(x) = n_{1}*f_{0}(x) + (n_{2} - n_{1})*f_{1}(x) + (n_{3} - 2*n_{2} + n_{1})*f_{3}(x). Obviously the interpolation can be continued indefinitely. Working out the coefficient of f_{k}(x) [like the (n_{3} - 2*n_{2} + n_{1}) above] is left as an exercise for the reader. Finally, we can shift the interpolation from (0, n_{1}), (1, n_{2}), ..., (k-1, n_{k}) to (1, n_{1}), (2, n_{2}), ..., (k, n_{k}) by shifting the functions f_{k}(x) = binomial(x,k) to f_{k}(x) = binomial(x-1,k). We note that the interpolation of (1, n_{1}), ..., (k, n_{k}) is unaffected by adding integer multiples of f_{k+1}(x), f_{k+2}(x), etc so a polynomial interpolation of (1, n_{1}), (2, n_{2}), ..., (k, n_{k}) can be extended to a polynomial interpolation of (1, n_{1}), (2, n_{2}), ..., (k, n_{k}), (k+1, n_{k+1}) where the integer n_{k+1} is completely arbitrary. Last fiddled with by Dr Sardonicus on 2019-07-13 at 11:57 Reason: adding item to list |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
New toy: Offline integer sequence search (ISS) | Till | Computer Science & Computational Number Theory | 5 | 2018-10-07 13:25 |
integer sequence that depends on the current one and the previous one and has addition and multiplic | MattcAnderson | MattcAnderson | 1 | 2017-05-04 18:07 |
Polynomial Coefficients Integer Sets | carpetpool | Miscellaneous Math | 1 | 2017-02-22 08:37 |
Missing Integer in a Sequence | a1call | Puzzles | 8 | 2016-05-17 23:25 |
Polynomial sequence | Orgasmic Troll | Puzzles | 6 | 2004-10-15 16:05 |