Go Back > Great Internet Mersenne Prime Search > Math > Number Theory Discussion Group

Thread Tools
Old 2019-07-13, 11:55   #1
Dr Sardonicus
Dr Sardonicus's Avatar
Feb 2017

22×769 Posts
Default 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
Dr Sardonicus is offline   Reply With Quote

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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.