# A recurrence relation

I noticed that

$(x_1 - x_k)\displaystyle\sum_{i_1+\cdots+i_k=n} x_1^{i_1}\cdots x_k^{i_k} = \displaystyle\sum_{i_1+\cdots+i_{k-1}=n+1} x_1^{i_1}\cdots x_{k-1}^{i_{k-1}} - \displaystyle\sum_{i_2+\cdots+i_k=n+1} x_2^{i_2}\cdots x_k^{i_k}.$

In the difference on the RHS, it is apparent that terms without $x_1$ or $x_k$ will vanish. Thus, all the negative terms which are not cancelled out have a $x_k$ and all such positive terms have a $x_1$. Combinatorially, all terms of degree $n+1$ with $x_k$ can be generated by multiplying $x_k$ on all terms of degree $n$. Analogous holds for the positive terms. The terms with only $x_1$ and $x_k$ are cancelled out with the exception of the $x_1^{n+1} - x_k^{n+1}$ that remains.

This recurrence appears in calculation of the determinant of the Vandermonde matrix.