Why $\sum_{k=0}^m\sum_{r=k}^{k+n} = \sum_{r=0}^{m+n}\sum_{k=0}^r$?

Question

I saw the proof about Vandermonde's identity here but i do not understand this step \begin{align} &=\sum_{k=0}^m\sum_{r=k}^{k+n}\binom{m}{k}\binom{n}{r-k}x^r&\\ &=\sum_{r=0}^{m+n}{\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}}x^r\\ \end{align}

Especially, why \begin{align} \sum_{k=0}^m\sum_{r=k}^{k+n} &= \sum_{r=0}^{m+n}\sum_{k=0}^r \end{align}

Answer 1

Short answer (swapping summations): $$0\le \underbrace{k}_{1}\le \underbrace{r}_{2}\le k+n\le m+n \Rightarrow 0\le \underbrace{r}_{1}\le m+n,0\le \underbrace{k}_{2}\le r.$$

Long answer (the second is summing diagonally):

Without loss of generality, consider $m\le n$.

Denote: $$\sum_{k=0}^m\sum_{r=k}^{k+n}\binom{m}{k}\binom{n}{r-k}x^r=\sum_{k=0}^m\sum_{r=k}^{k+n} a_{kr}\\ =\sum_{r=0}^{m+n}\color{#C00000}{\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}}x^r=\sum_{r=0}^{m+n}\sum_{k=0}^r a_{kr}$$ Note: ${m\choose k}=0,k>m$ and ${n\choose r-k}=0,n+k<r<k$.

Hence: $$\begin{align}\sum_{k=0}^m\sum_{r=k}^{k+n} a_{kr}= &[a_{00}+a_{01}+a_{02}+\cdots +a_{0m}+\cdots+a_{0n}]+\\ &[a_{11}+a_{12}+a_{13}+\cdots +a_{1m}+\cdots+a_{1(n+1)}]+\\ &[a_{22}+a_{23}+a_{24}+\cdots +a_{2m}+\cdots+a_{2(n+2)}]+\\ \vdots\\ &[a_{mm}+a_{m(m+1)}+a_{m(m+2)}+\cdots +a_{mm}+\cdots+a_{m(m+n)}]\end{align}\\ $$ $$\begin{align}\sum_{r=0}^{m+n}\sum_{k=0}^r a_{kr}= &[a_{00}]+\\ &[a_{01}+a_{11}]+\\ &[a_{02}+a_{12}+a_{22}]+\\ &[a_{03}+a_{13}+a_{23}+a_{33}]+\\ \vdots\\ &[a_{0m}+a_{1m}+a_{2m}+a_{3m}+\cdots+a_{mm}]+\\ &[a_{0(m+1)}+a_{1(m+1)}+\cdots+a_{m(m+1)}+\color{red}{a_{(m+1)(m+1)}}]+\\ \vdots\\ &[a_{0n}+a_{1n}+a_{2n}+\cdots+a_{mn}+\color{red}{a_{(m+1)n}+\cdots+a_{nn}}]+\\ &[\color{red}{a_{0(n+1)}}+a_{1(n+1)}+\cdots+a_{m(n+1)}+\color{red}{a_{(m+1)(n+1)}+\cdots +a_{(n+1)(n+1)}}]+\\ \vdots\\ &\small{[\color{red}{a_{0(m+n)}+\cdots +a_{(m-1)(m+n)}}+a_{m(m+n)}+\color{red}{a_{(m+1)(m+n)}+\cdots +a_{(m+n)(m+n)}}]}.\end{align}$$ Note: $\color{red}{a_{kr}}=0,k>m,n+k<r<k$.

Answer 2

Iverson notation can be very useful for reordering summations.

$$\begin{align} &=\sum_{k=0}^m\sum_{r=k}^{k+n}\cdots &\\ &=\sum_k \sum_r [0 \le k] [k \le m] [k \le r] [r \le k + n] \cdots \\ &=\sum_k \sum_r [0 \le k] [k \le r] [0 \le r] [k \le m] [r \le k + n] [r \le m + n] \cdots \\ &=\sum_r [0 \le r] [r \le m + n] \sum_k [0 \le k] [r - n \le k] [k \le r] [k \le m] \cdots \\ &=\sum_{r=0}^{m+n} \sum_{k=\max(0,r-n)}^{\min(m,r)} \cdots \end{align}$$ The further simplification is not general and relies on the summed term being zero outside the more explicit range.