12
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Pedro
    Commented Feb 6, 2014 at 21:20
  • $\begingroup$ Yeah, that's what I mean for the innterpolation proof, $\endgroup$
    – Alexander Gruber
    Commented Feb 6, 2014 at 21:41
  • $\begingroup$ Have you tried small cases, $n=2$ or $n=3$? $\endgroup$ Commented Feb 7, 2014 at 2:15
  • $\begingroup$ @GregMartin Yes, I have. $\endgroup$
    – Alexander Gruber
    Commented Feb 17, 2014 at 17:26

1 Answer 1

2
$\begingroup$

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.

enter image description here

$\endgroup$
8
  • $\begingroup$ This is very neat but I'm not sure how exactly it proves the summation. Could you spell it out for me? $\endgroup$
    – Alexander Gruber
    Commented Feb 7, 2014 at 5:52
  • $\begingroup$ @AlexanderGruber I have posted an example, it's faster like this. Let me know what you think. $\endgroup$ Commented Feb 7, 2014 at 6:21
  • $\begingroup$ Well @Alexander? $\endgroup$ Commented Feb 17, 2014 at 13:59
  • $\begingroup$ Sorry, I've been quite busy and hadn't been able to look over your edit yet. I will do so now. $\endgroup$
    – Alexander Gruber
    Commented Feb 17, 2014 at 17:21
  • 1
    $\begingroup$ 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}$? $\endgroup$
    – Alexander Gruber
    Commented Feb 17, 2014 at 17:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .