Basic interpolation

Say we've got \(n\) points through which we need to fit a polynomial. We'll solve the problem iteratively. First we'll find a polynomial that passes through one point, then we'll add a term to that polynomial to make it pass through another point, and then a third point will come into play -- etc.

Let the given points be \(\begin{array}{c}n\\(x_i, y_i)\\i=1\end{array}\) and let \(p_k\) denote the \(k\)th polynomial that we find. \(p_n\) is our final answer. \(p_k = \begin{cases}y_1 & \text{ if } k = 1\\ p_{k-1} + (y_k - p_{k-1}\bigg|_{x=x_k}) \prod_{i=1}^{k-1} \frac{x - x_i}{x_k - x_i} & \text{ if } 1 < k \leq n\end{cases}\).