# 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.

• You can provide an algebraic proof: if two polynomials of degree $n$ agree at $n+1$ points, they are the same polynomial. Do this with you sum and $P(X)=1$? Hmm, that doesn't fit your "combinatorial" request though.
– Pedro
Commented Feb 6, 2014 at 21:20
• Yeah, that's what I mean for the innterpolation proof, Commented Feb 6, 2014 at 21:41
• Have you tried small cases, $n=2$ or $n=3$? Commented Feb 7, 2014 at 2:15
• @GregMartin Yes, I have. Commented Feb 17, 2014 at 17:26

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.

• This is very neat but I'm not sure how exactly it proves the summation. Could you spell it out for me? Commented Feb 7, 2014 at 5:52
• @AlexanderGruber I have posted an example, it's faster like this. Let me know what you think. Commented Feb 7, 2014 at 6:21
• Well @Alexander? Commented Feb 17, 2014 at 13:59
• Sorry, I've been quite busy and hadn't been able to look over your edit yet. I will do so now. Commented Feb 17, 2014 at 17:21
• I like this a lot, I think it is exactly what I'm looking for. One question, regarding $\prod_{0<=i<j\leq n}(x_i-x_j)$, how do we know that this will end up with the same signs as the $\prod_{k\ne j}{x_k-x_j}$? Commented Feb 17, 2014 at 17:32