Given $n+1$ distinct points $\left\{x_{0}, x_{1}, \ldots, x_{n}\right\}$, let $p_{n} \in \mathbb{P}_{n}$ be the real polynomial of degree $n$ that interpolates a continuous function $f$ at these points. State the Lagrange interpolation formula.

Prove that $p_{n}$ can be written in the Newton form

$$p_{n}(x)=f\left(x_{0}\right)+\sum_{k=1}^{n} f\left[x_{0}, \ldots, x_{k}\right] \prod_{i=0}^{k-1}\left(x-x_{i}\right)$$

where $f\left[x_{0}, \ldots, x_{k}\right]$ is the divided difference, which you should define. [An explicit expression for the divided difference is not required.]

Explain why it can be more efficient to use the Newton form rather than the Lagrange formula.