Sheng Li (gmachine1729) wrote,
Sheng Li

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.

Tags: algebra, combinatorics, linear algebra, 数学/математика

  • Some thoughts on Greek, Persian, Arab, Indian, and Chinese science

    Originally published at 狗和留美者不得入内. You can comment here or there. Reading more about history, I’ve come to notice that China’s main…

  • 中英俄生物化学单词表


  • 美国的理工科教育和文化以及其对中国的影响


  • Post a new comment


    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened