Algebraic proof for Vandermonde’s identity + book recommendations for practising summation notation.

index-notationnotationsummation

I am trying to digest the proof for Vandermonde's identity, but due to my lack of experience with manipulating sigma notation, I am unable to understand how they got the RHS in the first step (expressing the product of two polynomials in sigma notation):
$$\left(\sum\limits_{i=0}^ma_ix^i\right)\left(\sum\limits_{j=0}^nb_jx^j\right)=\sum\limits_{r=0}^{m+n}\left(\sum\limits_{k=0}^r a_kb_{r-k}\right)x^r$$

Can someone please give me a step-by-step run through for how they deduced this result, making it clear what Summation rules/identities have been utilised.

For example, why have they introduced the new index variable $r$? Why not just apply the sigma notation rule (listed on Wikipedia):
$$\left(\sum\limits_{i=0}^n a_i\right)\left(\sum\limits_{j=0}^n b_j\right)=\sum\limits_{i=0}^n\sum\limits_{j=0}^na_ib_j$$
Does anyone also have any book recommendations for practising manipulating Capital Sigma notation (i.e. using the identities)? https://en.wikipedia.org/wiki/Summation

Best Answer

A common representation of a polynomial $p=p(x)$ is given according to increasing powers of $x$. \begin{align*} \sum_{i=0}^n a_ix^i=a_0+a_1x+a_2x^2+\cdots + a_nx^n\tag{1} \end{align*} Since the multiplication of two polynomials is again a polynomial, it is reasonable to also look for the common representation of the product of poynomials as given in (1).

We obtain \begin{align*} \color{blue}{\left(\sum_{i=0}^{m}a_ix^i\right)\left(\sum_{j=0}^nb_jx^j\right)} &=\sum_{i=0}^m\sum_{j=0}^n\left(a_ix^i\right)\left(b_jx^j\right)\tag{1}\\ &=\sum_{i=0}^m\sum_{j=0}^na_ib_jx^{i+j}\tag{2}\\ &=\sum_{r=0}^{m+n}\left(\sum_{{i+j=r}\atop{{0\leq i\leq m}\atop{0\leq j\leq n}}}a_ib_j\right)x^r\tag{3}\\ &\,\,\color{blue}{=\sum_{r=0}^{m+n}\left(\sum_{i=0}^ra_ib_{r-i}\right)x^r}\tag{4} \end{align*}

Comment:

  • In (1) we use arithmetic rules like distributivity, etc. and obtain a representation as it is given in the wiki page.

  • In (2) we use associativity, commutativity and $x^ix^j=x^{i+j}$.

  • In (3) we do the crucial step, namely collecting like powers and write them in increasing order using a newly introduced index $r$. Collecting like powers is described in the inner sum via $i+j=r$. We also respect the index range by explicitly stating them in the inner sum.

  • In (4) we eliminate the index variable $j$ which is related by $r=i+j \to j=r-i$. We also do not longer state upper bounds $m$ and $n$ in the inner sum for $i$ and $j$. We instead sum up to the upper limit $m+n$ by simply taking $a_i=0$ if $i>m$ and similarly by taking $b_j=0$ if $j>n$.

Hint: You might find chapter 2: Sums in Concrete Mathematics by R.L. Graham, D.E. Knuth and O. Patashnik helpful. It provides a thorough introduction to the use of sums.

Related Question