I was working on this projecteuler.com problem, and I was very interested by the premise. Essentially, given n terms, find an (n-1)th degree polynomial that describes the data perfectly.
This is obviously possible for n = 1 or 2. I can build a constant function for 1 term, a linear function for 2 terms. 3 terms isn't so hard either -- I think I could imagine a quadratic function to describe any 3 terms.
I have the feeling that this is generally possible, but I don't have a good reason to think so. I'm not interested in hints or solutions to the Project Euler problem, but I'm very interested in an explanation, proof, or counterexample for the following statement:
Given a sequence S with n terms, there exists a polynomial f of degree n - 1 where, for all indices i in S, f(i) = Si
Apologies for some probably shoddy formalism in that wording, I don't have too much experience with this sort of thing. If indices or sequence aren't the right words, I'm welcome to a rewording suggestion.
I also have a feeling that this could relevant to a Taylor Series, but it's been a while.
The Lagrange interpolation delivers such a polynomial of degree at most $ n-1$. It's the unique such polynomial, since the difference of two such, $f_1-f_2$, must have $n>n-1$ zeros, hence must be identically zero.
The polynomial does not necessarily have degree equal to $n-1$. For example, the data $f(1)=1$, $f(2)=2$, $f(3)=3$ does not fit any quadratic polynomial; it fits to a line.