mersenneforum.org > Math Polynomial interpolation of an integer sequence
 Register FAQ Search Today's Posts Mark Forums Read

 2019-07-13, 11:55 #1 Dr Sardonicus     Feb 2017 Nowhere 22×769 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 n1, n2, n3,... 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) = n1, f(2) = n2, ..., and f(k) = nk. This uses the "binomial coefficient" polynomials f0(x) = 1, f1(x) = x, f2(x) = x*(x-1)/2!, etc where fk(x) = binomial(x,k) = x(x-1)...(x - (k-1))/k! We note that (1) fk(x) assumes integer values for integer values of x, (2) fk(m) = 0 for m = 0, 1, ..., k-1 and fk(k) = 1, and (3) fk(x) has degree k. We can thus interpolate the points (0, n1) and (1, n2) by taking f(x) = n1*f0(x) + (n2 - n1)*f1(x). We can interpolate (2, n3) by adding an appropriate multiple of f2(x); we find that f(x) = n1*f0(x) + (n2 - n1)*f1(x) + (n3 - 2*n2 + n1)*f3(x). Obviously the interpolation can be continued indefinitely. Working out the coefficient of fk(x) [like the (n3 - 2*n2 + n1) above] is left as an exercise for the reader. Finally, we can shift the interpolation from (0, n1), (1, n2), ..., (k-1, nk) to (1, n1), (2, n2), ..., (k, nk) by shifting the functions fk(x) = binomial(x,k) to fk(x) = binomial(x-1,k). We note that the interpolation of (1, n1), ..., (k, nk) is unaffected by adding integer multiples of fk+1(x), fk+2(x), etc so a polynomial interpolation of (1, n1), (2, n2), ..., (k, nk) can be extended to a polynomial interpolation of (1, n1), (2, n2), ..., (k, nk), (k+1, nk+1) where the integer nk+1 is completely arbitrary. Last fiddled with by Dr Sardonicus on 2019-07-13 at 11:57 Reason: adding item to list

 Similar Threads Thread Thread Starter Forum Replies Last Post Till Computer Science & Computational Number Theory 5 2018-10-07 13:25 MattcAnderson MattcAnderson 1 2017-05-04 18:07 carpetpool Miscellaneous Math 1 2017-02-22 08:37 a1call Puzzles 8 2016-05-17 23:25 Orgasmic Troll Puzzles 6 2004-10-15 16:05

All times are UTC. The time now is 21:50.

Thu Apr 9 21:50:42 UTC 2020 up 15 days, 19:23, 1 user, load averages: 1.52, 1.69, 1.78