# A recurrence relation

Originally published at 狗和留美者不得入内. You can comment here or there.

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.

• #### 15 цитат Достоевского о либералах

Копирван из https://pravdoiskatel77.livejournal.com/14379545.html Фёдор Михайлович прошёл сложный жизненный путь, от социалиста-утописта, до…

• #### 中国姓氏的南北分布

有意思的是分布是很不均匀的，也就是说好多姓是南方比例远高于北方比例或相反。从这一点，你如果知道一个人的父母的姓氏，你就可以对他是北方人还是南方人有个有点统计显著的估计。 读者可以在包含大姓分布图的…

• #### Why I think Stanford professor James Landay's piece on computing in China in 2011 exposed his idiocy

I dittoed his blog post on my LiveJournal too, see https://gmachine1729.livejournal.com/175023.html. For the original, see…

• Post a new comment

#### Error

Anonymous comments are disabled in this journal

default userpic