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

Question

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

Answer 1

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.

Answer 2

Of course you can write

$$\left(\sum\limits_{i=0}^ma_ix^i\right)\left(\sum\limits_{j=0}^nb_jx^j\right)=\sum\limits_{i=0}^{m}\sum\limits_{j=0}^n a_ix^ib_j x^j = \sum\limits_{i=0}^{m}\sum\limits_{j=0}^na_ib_jx^{i+j} . \tag{1}$$ However, the product of polynomials is again a polynomial and thus the RHS of $(1)$ should be rewritten in the form $$\sum_{r=0}^N c_rx^r .$$ For an integer $p$ let us write $[p] = \{0,1,\ldots,p \}$. With this notation the RHS of $(1)$ gets $$\sum\limits_{i=0}^{m}\sum\limits_{j=0}^na_ib_jx^{i+j} = \sum_{(i,j) \in [m] \times [n]} a_ib_jx^{i+j} . \tag{2}$$

On the RHS of $(2)$ the expression $i+j$ takes all values from $0+0 = 0$ to $m + n$. For $r \in [m+n]$ let $I_r$ denote the set of all pairs $(i,j) \in [m] \times [n]$ such that $i + j = r$. Clearly $$I_r = \{(k,r-k) \mid k \in [r] \} .$$ The sets $I_r$ are pairwise disjoint and we have $$[m] \times [n] = \bigcup_{r =0}^{m+n} I_r .$$ Therefore $$\sum_{(i,j) \in [m] \times [n]} a_ib_jx^{i+j} = \sum_{r=0}^{m+n} \left(\sum_{(i,j) \in I_r} a_ib_j\right)x^r = \sum_{r=0}^{m+n} c_rx^r$$ with $$c_r = \sum_{(i,j) \in I_r} a_ib_j =\sum_{k=0}^r a_kb_{r-k} .$$