Lagrange Interpolation Formula
The Lagrange Interpolation Formula states that For any distinct complex numbers and any complex numbers , there exists a unique polynomial of degree less than or equal to such that for all integers , , and this polynomial is
This formula is useful for many olympiad problems, especially since such a polynomial is unique.
Consider an th-degree polynomial of the given form
Substituting into the given equation yields us
Again, substituting yields us
Repeating this process, by substituting in we get the Lagrange Interpolation Formula as:
While this formula may appear intimidating, it's actually not so difficult to see what is going on: for each term in the sum, we are finding a polynomial of degree that goes through the points and for . When we add them all together, we end up with a polynomial that interpolates the desired points.