Neville's algorithm

Remarks

By induction on $j - i$, the number $p_{i,j}$ is the value at $x$ of the interpolation polynomial of degree at most $j - i$ through $(x_i, y_i), \dots, (x_j, y_j)$. Indeed, the same recursion with $x$ as a variable gives a polynomial of degree at most $j - i$. At $x = x_i$ it gives $p_{i,j-1}(x_i) = y_i$, and at $x = x_j$ it gives $p_{i+1,j}(x_j) = y_j$. At an inner node $x_k$ both terms give $y_k$. So the output $p_{0,n}$ is the value at $x$ of the interpolation polynomial of all the data.

Example: data $(0, 1)$, $(1, 3)$, $(2, 7)$ and $x = 3$. Then $p_{0,1} = \frac{3 \cdot 3 - 2 \cdot 1}{1} = 7$, $p_{1,2} = \frac{2 \cdot 7 - 1 \cdot 3}{1} = 11$ and $p_{0,2} = \frac{3 \cdot 11 - 1 \cdot 7}{2} = 13$. This agrees with the interpolation polynomial $x^2 + x + 1$ at $3$.

Non-example: if two nodes coincide, $x_i = x_j$ with $i < j$, the recursion divides by $x_j - x_i = 0$, so the algorithm is not defined.