Direct combinatorial proof of a sum identity on formal Lagrange polynomials Let $k$ be a field and $K=k(x_0,x_1,\ldots, x_n)[x]$.  Define $$\mathcal{L}_k(x)\triangleq \prod_{\substack{j=0\\  j\ne k}}^n\frac{x-x_j}{x_k-x_j}.$$

Is there a purely combinatorial way to show that
  $$\sum_{k=0}^n\mathcal{L}_k(x)=1?$$

That is, I would like to consider the $\mathcal{L}_k(x)$ as formal polynomials, not as functions. I am aware of proof by interpolation, but I think there must be an interesting combinatorial proof using counting arguments with the indices.

My attempt.
To directly add the summands together, we need a common denominator.  Let $R_n=\{0,\ldots, n\}$, $S=\{(i,j)\in R_n\times R_n |j<i\}$, and $S_k=\{(i,j)\in S | i=k\text{ or }j=k\}$.
First, note that
$$\begin{eqnarray*}\prod_{\substack{j=0\\  j\ne k}}^n\frac{1}{x_k-x_j}&=&
\prod_{\substack{j=0\\  j< k}}^n\frac{1}{x_k-x_j}\prod_{\substack{j=0\\  j> k}}^n\frac{1}{-(x_j-x_k)}\\&=&\prod_{j=0}^{k-1}\frac{1}{x_k-x_j}\prod_{j=k+1}^n\frac{1}{-(x_j-x_k)}\\
&=&(-1)^{n-k}\prod_{(i,j)\in S_k}\frac{1}{x_i-x_j}
\end{eqnarray*}$$
To get a common denominator, we therfore multiply each term by $$\frac{\prod_{(i,j)\in S\setminus S_k}x_i-x_j}{\prod_{(i,j)\in S\setminus S_k}x_i-x_j}$$
to obtain $$\prod_{j<i}\frac{1}{x_i-x_j}\sum_{k=0}^n\left((-1)^{n-k}\prod_{\substack{j=0\\ j\ne k}}^n(x-x_j)\prod_{(i,j)\in S\setminus S_k}(x_i-x_j)\right)$$
...and here is where I can't get stuck, can't think of a how to continue.
 A: There is a nice argument using the Vandermonde determinant. I don't know if it's combinatorial enough to your taste.
Consider the Vandermonde matrix $V(x_0, x_1, \dots, x_n)$. Its determinant is $$D = \prod_{0 \leq i< j \leq n} (x_i-x_j).$$ (There are many arguments for this.) Remark that if we shift all of the $x_i$'s by the same variable, the determinant doesn't change, because $x_i-x_j = (x_i+x)-(x_j+x)$. Therefore,
$$D(x_0+x,\: x_1+x,\: \dots,\: x_n+x) = D(x_0, x_1, \dots, x_n) = D.$$
But now if we expand the determinant $D(x_0+x,\: x_1+x,\: \dots,\: x_n+x)$ along the column of $1$'s, we get precisely the formula $\sum \mathcal L_k(x) = 1$ after dividing by $D$ (using induction on each of the $n+1$ smaller determinants).
Edit: Here's an example of what I mean, for $n=2$. I hope it's clear. At the top we have the Vandermonde determinant, and I have expanded it out along the column of $1$'s. I end up with $3$ Vandermonde determinants of one smaller size, which I also evaluate using the trick above. Dividing the bottom result by the top result gives your formula. Sorry about the picture quality, it's a narrow space and I couldn't get the whole board in any other way.

