Let's say we have multiple integer sequences, some coming from polynomials (of unknown degrees), some coming from non-polynomials. For example: $a = 1,4,9,16,32,...$
We want to figure out whether $a$ is coming from a polynomial or not. My idea was to fit a Lagrange polynomial on the first $n$ elements ($a_{1}$ to $a_{n}$) in the sequence. Then use the Lagrange Polynomial to calculate the error between the correct next $n$ values (from $a_{n+1}$ to $a_{2n}$) and the 'predicted' values from the Lagrange Polynomial. An error of $0$ would then indicate that the sequence is likely from a polynomial, an error $>0$ would indicate that either $n$ is chosen too small (i.e. the degree is higher than $n$) or the sequence does not come from a polynomial.
Regarding the above example, this works all right when I use small $n$, for example, $n = 10$. However, when setting $n$ to 100, the fitted Lagrange Polynomial has degree a lot higher than 2. And the error gets rather large. But I need a high $n$ to be able to detect polynomials of high degree.
Is there a method of interpolation that does not suffer from this problem? Or can the Lagrange Method be used differently on this task? It seems as this is similar to regularization in machine learning where small or $0$ values are prefered.