Numerical Methods: Very Difficult Problems with Solutions

Solution:
Let [tex]\omega(x)=(x-x_1)(x-x_2)\ldots(x-x_n)[/tex] and put [tex]P(x)=x^n-\omega(x)[/tex]. We have
[tex]\omega(x)=x^n-(x_1+x_2+\ldots+x_n)x^{n-1}+\ldots[/tex]
so the terms [tex]x^n[/tex] cancel and [tex]P[/tex] is a polynomial of degree at most [tex]n-1[/tex]; moreover [tex]P(x_i)=x_i^n-0=f(x_i)[/tex] for [tex]i=1,\ldots,n[/tex]. The interpolation polynomial of degree [tex]\le n-1[/tex] through [tex]n[/tex] distinct nodes is unique, hence [tex]P[/tex] is the interpolation polynomial of [tex]f[/tex] at [tex]x_1,\ldots,x_n[/tex]. In Newton's form it reads
[tex]P(x)=f[x_1]+f[x_1,x_2](x-x_1)+\ldots+f[x_1,\ldots,x_n](x-x_1)\ldots(x-x_{n-1})[/tex]
so [tex]f[x_1,\ldots,x_n][/tex] is the coefficient of [tex]x^{n-1}[/tex] in [tex]P[/tex]. From
[tex]P(x)=x^n-\omega(x)=(x_1+x_2+\ldots+x_n)x^{n-1}+\ldots[/tex]
we obtain
[tex]f[x_1,x_2,\ldots,x_n]=x_1+x_2+\ldots+x_n[/tex]
Check for [tex]n=2[/tex]: [tex]f[x_1,x_2]=\frac{x_2^2-x_1^2}{x_2-x_1}=x_1+x_2[/tex].

Solution:
Fix an arbitrary real [tex]x[/tex] and consider the polynomial of degree [tex]n+2[/tex] in the variable [tex]t[/tex]
[tex]g(t)=(x-t)^{n+2}[/tex]
Divide it by the monic polynomial [tex]\omega(t)[/tex] of degree [tex]n+1[/tex]:
[tex]g(t)=\omega(t)q(t)+r(t),\qquad \deg q=1,\qquad \deg r\le n[/tex]
Since [tex]\omega(x_k)=0[/tex], we have [tex]r(x_k)=g(x_k)[/tex] for [tex]k=0,\ldots,n[/tex]. The Lagrange polynomial [tex]L(t)=\sum_{k=0}^{n}g(x_k)l_k(t)[/tex] is the unique polynomial of degree [tex]\le n[/tex] taking the values [tex]g(x_k)[/tex] at the [tex]n+1[/tex] distinct nodes, so [tex]r=L[/tex]. Putting [tex]t=x[/tex] and using [tex]g(x)=0[/tex]:
[tex]\sum_{k=0}^{n}(x-x_k)^{n+2}l_k(x)=r(x)=g(x)-\omega(x)q(x)=-\omega(x)q(x)[/tex]
It remains to find [tex]q(t)=\alpha t+\beta[/tex]. Let [tex]s=x_0+x_1+\ldots+x_n[/tex]; then
[tex]\omega(t)=t^{n+1}-s\,t^n+\ldots,\qquad g(t)=(-1)^n(t-x)^{n+2}=(-1)^n\left(t^{n+2}-(n+2)x\,t^{n+1}+\ldots\right)[/tex]
Since [tex]\deg r\le n[/tex], the coefficients of [tex]t^{n+2}[/tex] and [tex]t^{n+1}[/tex] in [tex]g[/tex] and in [tex]\omega q=(t^{n+1}-s\,t^n+\ldots)(\alpha t+\beta)[/tex] coincide:
[tex]\alpha=(-1)^n,\qquad \beta-\alpha s=-(-1)^n(n+2)x\ \Rightarrow\ \beta=(-1)^n\left(s-(n+2)x\right)[/tex]
Hence
[tex]q(x)=(-1)^n\left(x+s-(n+2)x\right)=(-1)^n\left(s-(n+1)x\right)=-(-1)^n\sum_{k=0}^{n}(x-x_k)[/tex]
and therefore
[tex]\sum_{k=0}^{n}(x-x_k)^{n+2}l_k(x)=-\omega(x)q(x)=(-1)^n\omega(x)\sum_{k=0}^{n}(x-x_k)[/tex]
Since [tex]x[/tex] was arbitrary, the identity holds for every real [tex]x[/tex]. (For [tex]n=0[/tex]: [tex]l_0=1[/tex] and both sides equal [tex](x-x_0)^2[/tex].)