# Finding a generating function for a pattern

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.

-
@DanielFischer Thanks! Not only does such a function exist, it looks like there's a formula to find it without much trouble. (I'll have to read this more carefully.) Not bad. – rogaos Sep 4 '13 at 18:49
Look also at Newton interpolation, it's a different algorithm (to find the same polynomial), sometimes easier to calculate by hand than the Lagrange formula. – Daniel Fischer Sep 4 '13 at 18:50

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) = S_i$
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.