[proofplan] We compare the interpolating polynomial $p$ with the degree at most $n+1$ Newton interpolant through the enlarged node list $x_0,\ldots,x_n,t$. The Newton form shows that adding the last node contributes exactly the [divided difference](/page/Divided%20Difference) $f[x_0,\ldots,x_n,t]$ multiplied by the nodal product $\prod_{m=0}^{n}(s-x_m)$. Evaluating at $s=t$ and using the interpolation identities gives the desired error formula. [/proofplan]

[step:Write the enlarged Newton interpolant through $x_0,\ldots,x_n,t$]Define the enlarged node list $y_0,\ldots,y_{n+1}\in I$ by \begin{align*} y_m=x_m \end{align*} for $m\in\{0,\ldots,n\}$, and \begin{align*} y_{n+1}=t. \end{align*} Since $t\notin X_n$ and the $x_m$ are pairwise distinct, the nodes $y_0,\ldots,y_{n+1}$ are pairwise distinct. Let $q\in\mathcal{P}_{n+1}$ be the Newton interpolation polynomial for $f$ on the nodes $y_0,\ldots,y_{n+1}$: \begin{align*} q(s)=f[y_0]+\sum_{j=1}^{n+1} f[y_0,\ldots,y_j]\prod_{\ell=0}^{j-1}(s-y_\ell) \end{align*} for $s\in\mathbb{R}$. By the [Newton interpolation formula](/theorems/474) for divided differences, $q(y_j)=f(y_j)$ for every $j\in\{0,\ldots,n+1\}$.[/step]

[guided]We enlarge the interpolation data by appending the point $t$ to the original nodes. Formally, define $y_m=x_m$ for $m\in\{0,\ldots,n\}$ and $y_{n+1}=t$. The hypothesis $t\notin X_n$ is used here: it guarantees that the divided differences in the enlarged list involve distinct nodes, so the Newton coefficients are defined. The Newton interpolation polynomial associated to these data is the map $q:\mathbb{R}\to\mathbb{R}$ given by \begin{align*} q(s)=f[y_0]+\sum_{j=1}^{n+1} f[y_0,\ldots,y_j]\prod_{\ell=0}^{j-1}(s-y_\ell). \end{align*} This polynomial has degree at most $n+1$, because the $j$th summand is a polynomial of degree at most $j$. The Newton interpolation formula says that this polynomial interpolates the values of $f$ at the selected nodes: \begin{align*} q(y_j)=f(y_j) \end{align*} for every $j\in\{0,\ldots,n+1\}$. In particular, $q(x_m)=f(x_m)$ for $m\in\{0,\ldots,n\}$ and $q(t)=f(t)$.[/guided]

[step:Separate the degree at most $n$ part from the final Newton term] Define $r:\mathbb{R}\to\mathbb{R}$ by \begin{align*} r(s)=f[y_0]+\sum_{j=1}^{n} f[y_0,\ldots,y_j]\prod_{\ell=0}^{j-1}(s-y_\ell). \end{align*} Then $r\in\mathcal{P}_n$, and the Newton formula for $q$ gives \begin{align*} q(s)=r(s)+f[y_0,\ldots,y_n,y_{n+1}]\prod_{\ell=0}^{n}(s-y_\ell) \end{align*} for every $s\in\mathbb{R}$. Substituting $y_m=x_m$ and $y_{n+1}=t$, this becomes \begin{align*} q(s)=r(s)+f[x_0,\ldots,x_n,t]\prod_{m=0}^{n}(s-x_m). \end{align*} [/step]

[step:Identify the degree at most $n$ part with the given interpolating polynomial] For every $m\in\{0,\ldots,n\}$, the Newton interpolation property applied to the truncated polynomial $r$ gives \begin{align*} r(x_m)=f(x_m). \end{align*} The given polynomial $p\in\mathcal{P}_n$ also satisfies $p(x_m)=f(x_m)$ for every $m\in\{0,\ldots,n\}$. Hence the polynomial $r-p\in\mathcal{P}_n$ has the $n+1$ distinct roots $x_0,\ldots,x_n$. A nonzero polynomial of degree at most $n$ has at most $n$ distinct roots, so $r-p$ is the zero polynomial. Therefore \begin{align*} r(s)=p(s) \end{align*} for every $s\in\mathbb{R}$. [/step]

[step:Evaluate the comparison formula at the new node $t$] Using $r=p$ in the decomposition of $q$, we have \begin{align*} q(s)=p(s)+f[x_0,\ldots,x_n,t]\prod_{m=0}^{n}(s-x_m) \end{align*} for every $s\in\mathbb{R}$. Evaluating at $s=t$ gives \begin{align*} q(t)=p(t)+f[x_0,\ldots,x_n,t]\prod_{m=0}^{n}(t-x_m). \end{align*} Since $q$ interpolates $f$ at the enlarged node $t$, we have $q(t)=f(t)$. Therefore \begin{align*} f(t)-p(t)=f[x_0,\ldots,x_n,t]\prod_{m=0}^{n}(t-x_m). \end{align*} This is the asserted interpolation error formula. [/step]