[proofplan] We prove the result by induction on the order of the [divided difference](/page/Divided%20Difference). The order-zero case is exactly the pointwise definition of the linear combination. For the induction step, we apply the recursive definition of divided differences to the first and last sublists of nodes, use the induction hypothesis on those two lower-order divided differences, and then collect the coefficients $\alpha$ and $\beta$. [/proofplan]

[step:Verify the order-zero case from the pointwise definition] Let $y_0\in S$, and let $u:S\to\mathbb{R}$ be any function. By the order-zero convention in the definition of divided differences, $u[y_0]=u(y_0)$. Hence, for $h=\alpha f+\beta g$, \begin{align*} h[y_0]=h(y_0)=\alpha f(y_0)+\beta g(y_0)=\alpha f[y_0]+\beta g[y_0]. \end{align*} Thus the asserted linearity holds for divided differences of order $0$. [/step]

[step:Apply the recursive formula and use the induction hypothesis]Assume that the asserted linearity holds for divided differences of order $m-1$, where $m\in\mathbb{N}$. Let $y_0,\ldots,y_m\in S$ be pairwise distinct. Since $y_m\ne y_0$, the denominator $y_m-y_0$ is nonzero, and the recursive definition of divided differences gives \begin{align*} h[y_0,\ldots,y_m]=\frac{h[y_1,\ldots,y_m]-h[y_0,\ldots,y_{m-1}]}{y_m-y_0}. \end{align*} The sublists $y_1,\ldots,y_m$ and $y_0,\ldots,y_{m-1}$ are pairwise distinct, so the induction hypothesis applies to both. Therefore \begin{align*} h[y_1,\ldots,y_m]=\alpha f[y_1,\ldots,y_m]+\beta g[y_1,\ldots,y_m]. \end{align*} Also, \begin{align*} h[y_0,\ldots,y_{m-1}]=\alpha f[y_0,\ldots,y_{m-1}]+\beta g[y_0,\ldots,y_{m-1}]. \end{align*} Substituting these two identities into the recursive formula gives \begin{align*} h[y_0,\ldots,y_m]=\alpha\frac{f[y_1,\ldots,y_m]-f[y_0,\ldots,y_{m-1}]}{y_m-y_0}+\beta\frac{g[y_1,\ldots,y_m]-g[y_0,\ldots,y_{m-1}]}{y_m-y_0}. \end{align*} Applying the recursive definition of divided differences once more, this becomes \begin{align*} h[y_0,\ldots,y_m]=\alpha f[y_0,\ldots,y_m]+\beta g[y_0,\ldots,y_m]. \end{align*}[/step]

[guided]We now prove the induction step in detail. Assume that linearity is already known for divided differences of order $m-1$, where $m\in\mathbb{N}$. Let $y_0,\ldots,y_m\in S$ be pairwise distinct nodes. The pairwise distinctness has two roles: it ensures that the shorter node lists $y_1,\ldots,y_m$ and $y_0,\ldots,y_{m-1}$ are valid lists for divided differences, and it ensures that $y_m-y_0\ne 0$, so the recursive quotient is defined. By the recursive definition of divided differences, applied to the function $h:S\to\mathbb{R}$, we have \begin{align*} h[y_0,\ldots,y_m]=\frac{h[y_1,\ldots,y_m]-h[y_0,\ldots,y_{m-1}]}{y_m-y_0}. \end{align*} The point of using this recursion is that both divided differences on the numerator have order $m-1$, so the induction hypothesis applies to them. Since $y_1,\ldots,y_m$ are pairwise distinct, the induction hypothesis gives \begin{align*} h[y_1,\ldots,y_m]=\alpha f[y_1,\ldots,y_m]+\beta g[y_1,\ldots,y_m]. \end{align*} Since $y_0,\ldots,y_{m-1}$ are also pairwise distinct, the induction hypothesis also gives \begin{align*} h[y_0,\ldots,y_{m-1}]=\alpha f[y_0,\ldots,y_{m-1}]+\beta g[y_0,\ldots,y_{m-1}]. \end{align*} Substitute these two identities into the recursive formula for $h[y_0,\ldots,y_m]$. We obtain \begin{align*} h[y_0,\ldots,y_m]=\frac{\alpha f[y_1,\ldots,y_m]+\beta g[y_1,\ldots,y_m]-\alpha f[y_0,\ldots,y_{m-1}]-\beta g[y_0,\ldots,y_{m-1}]}{y_m-y_0}. \end{align*} Now collect the $\alpha$ terms and the $\beta$ terms in the numerator, then distribute the nonzero denominator: \begin{align*} h[y_0,\ldots,y_m]=\alpha\frac{f[y_1,\ldots,y_m]-f[y_0,\ldots,y_{m-1}]}{y_m-y_0}+\beta\frac{g[y_1,\ldots,y_m]-g[y_0,\ldots,y_{m-1}]}{y_m-y_0}. \end{align*} Each fraction is again exactly the recursive definition of the order-$m$ divided difference, first for $f$ and then for $g$. Therefore \begin{align*} h[y_0,\ldots,y_m]=\alpha f[y_0,\ldots,y_m]+\beta g[y_0,\ldots,y_m]. \end{align*} This proves the induction step.[/guided]

[step:Conclude the statement for the prescribed nodes] By induction on the order, the linearity identity holds for every $m\in\mathbb{N}\cup\{0\}$ and every pairwise distinct list $y_0,\ldots,y_m$ in $S$. Taking $m=n$ and $y_i=x_i$ for each $i\in\{0,\ldots,n\}$ gives \begin{align*} (\alpha f+\beta g)[x_0,\ldots,x_n]=\alpha f[x_0,\ldots,x_n]+\beta g[x_0,\ldots,x_n]. \end{align*} This is the desired identity. [/step]