Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
1  
    
@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
1  
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.