Finite double sum: Improve index transformation

Question

In order to prove a rather complicated binomial identity a small part of it implies a transformation of a double sum.

The double sum and its transformation have the following shape: \begin{align*} \sum_{k=0}^{l}\sum_{j=\max\{1,k\}}^{\min\{l,k+c\}}1=\sum_{j=1}^{l}\sum_{k=0}^{\min\{j,c\}}1\qquad\qquad l\geq 1, c\geq 1 \end{align*}

Here I do not want to take care of the terms which are to sum up. They are set to $1$ for the sake of simplicity. What matters is an efficient, short indextransformation showing that the identity is valid.

At the time I've found a rather long-winded solution. It is added as answer to this question. But in fact I would appreciate to find a more elegant way to prove this identity.

Answer 1

Perhaps the simplest argument is geometric. A sketch makes it evident that if $c\le\ell$, the lefthand side is the number of points of $\Bbb N\times\Bbb N$ lying in the convex hull of the points $\langle 0,1\rangle$, $\langle 0,c\rangle$, $\langle 1,1\rangle$, $\langle \ell-c,\ell\rangle$, and $\langle\ell,\ell\rangle$. For $c\le j\le\ell$ the $j$-section has $c+1$ points, and for $1\le j<c$ it has $j+1$ points, so in general it has $\min\{j+1,c+1\}$ points. Clearly

$$\sum_{k=0}^{\min\{j,c\}}1=\min\{j+1,c+1\}\;.$$

Here’s the sketch:

The colored regions contain the points in question. The orange region comprises the $j$-sections with $c+1$ points; the blue, the $j$-sections with $j+1$ points.

For $c>\ell$ the blue region expands to the top of the square.

Answer 2

Note: It would be nice to provide a more elegant solution than my answer below.

The following identity is valid for $l\geq 1, c\geq 1$ \begin{align*} \sum_{k=0}^{l}\sum_{j=\max\{1,k\}}^{\min\{l,k+c\}}1=\sum_{j=1}^{l}\sum_{k=0}^{\min\{j,c\}}1 \end{align*}

In Order to prove this identity we consider two cases: $c<l$ and $c\geq l$.

Case $(c<l)$: \begin{align*} \sum_{k=0}^{l}&\sum_{j=\max\{1,k\}}^{\min\{l,k+c\}}1\\ &=\sum_{j=1}^c1+\sum_{k=1}^{l-c}\sum_{j=k}^{k+c}1+\sum_{k=l-c+1}^{l}\sum_{j=k}^{l}1\tag{1}\\ &=\sum_{j=1}^c1+\sum_{k=1}^{l-c}\sum_{j=0}^{c}1+\sum_{k=1}^{c}\sum_{j=k+l-c}^{l}1\tag{2}\\ &=\sum_{j=1}^c1+\sum_{k=1}^{l-c}\sum_{j=0}^{c}1+\sum_{j=l-c+1}^{l}\sum_{k=1}^{j-l+c}1\tag{3}\\ &=\sum_{j=1}^c1+\sum_{k=1}^{l-c}\sum_{j=0}^{c}1+\sum_{j=1}^{c}\sum_{k=1}^{j}1\tag{4}\\ &=\sum_{j=1}^{c}\sum_{k=0}^{j}1+\sum_{k=1}^{l-c}\sum_{j=0}^{c}1\tag{5}\\ &=\sum_{j=1}^{c}\sum_{k=0}^{j}1+\sum_{k=c+1}^{l}\sum_{j=0}^{c}1\tag{6}\\ &=\sum_{j=1}^{c}\sum_{k=0}^{j}1+\sum_{j=c+1}^{l}\sum_{k=0}^{c}1\tag{7}\\ &=\sum_{j=1}^{l}\sum_{k=0}^{\min\{j,c\}}1\\ \end{align*}

Comment:

• In (1) we separate $k=0$ and split the sum according to $\min\{l,k+c\}$

• In (2) indextransfomation of $k$ in rightmost summand

• In (3) exchange of sums in rightmost summand

• In (4) indextransformation of $j$ in rightmost summand

• In (5) merge of left and right summand

• In (6) indextransformation of $k$ in right summand

• In (7) exchange of index names in right summand

Case $(c\geq l)$: \begin{align*} \sum_{k=0}^{l}&\sum_{j=\max\{1,k\}}^{\min\{l,k+c\}}1\\ &=\sum_{j=1}^l1+\sum_{k=1}^l\sum_{j=k}^l1\tag{1}\\ &=\sum_{j=1}^l1+\sum_{k=1}^l\sum_{j=l-k+1}^l1\tag{2}\\ &=\sum_{j=1}^l1+\sum_{k=1}^l\sum_{j=0}^{k-1}1\tag{3}\\ &=\sum_{k=1}^l\sum_{j=0}^{k}1\tag{4}\\ &=\sum_{j=1}^{l}\sum_{k=0}^{\min\{j,c\}}1\\ &\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\Box \end{align*}

Comment:

• In (1) we separate $k=0$

• In (2) change of order of summation of $j$ in right summand

• In (3) indextransformation of $j$ in right summand

• In (4) merge of summands