Simplify a summation with indicator function

Question

I have this double summation that I want to simplify:

$$\sum^{q} _{j=-q} \sum^{q} _{i=-q} \mathbb{1}_{ \{h+j-i=0 \}}$$

A given solution says the answer is $2q+1-h$ for $|h| \leq 2q$ and $0$ otherwise.

I don't see this. For example, when I take $q=1$ and $h = 2*q = 2$ the summation sums up to $0$ which is unequal to $2q+1-h = 1$.

Anyone can help me out?

Answer 1

First note that the example $q=1, h=2$ works, since \begin{align*} \color{blue}{\sum_{j=-1}^1\sum_{i=-1}^1 1_{\{2+i-j=0\}}} &=\sum_{j=-1}^1\left(1_{\{j=1\}}+1_{\{j=2\}}+1_{\{j=3\}}\right)\\ &=\sum_{j=-1}^11_{\{j=1\}}\\ &=1\\ &\,\,\color{blue}{=2q+1-h} \end{align*}

We transfrom the double sum in a rather detailed way \begin{align*} \color{blue}{\sum_{j=-q}^q\,}&\color{blue}{\sum_{i=-q}^q 1_{\{h+j-i=0\}}}\\ &=\sum_{j=0}^{2q}\sum_{i=0}^{2q} 1_{\{h+(j-q)-(i-q)=0\}}=\sum_{j=0}^{2q}\sum_{i=0}^{2q} 1_{\{h+j-i=0\}}\tag{1}\\ &=\sum_{j=0}^{2q}\sum_{i=-h}^{2q-h} 1_{\{h+j-(i+h)=0\}}=\sum_{j=0}^{2q}\sum_{i=-h}^{2q-h} 1_{\{i=j\}}\tag{2}\\ &= \begin{cases} \sum_{j=0}^{2q}\sum_{\color{blue}{i=0}}^{2q-h} 1_{\{i=j\}}&\qquad h\geq 0\\ \\ \sum_{\color{blue}{j=-h}}^{2q}\sum_{i=-h}^{2q-h} 1_{\{i=j\}}&\qquad-h\geq 0 \end{cases}\tag{3}\\ &= \begin{cases} \sum_{j=0}^{\color{blue}{2q-h}}\sum_{i=0}^{2q-h} 1_{\{i=j\}}&\qquad h\geq 0,2q-h\geq 0\\ \\ \sum_{j=-h}^{2q}\sum_{i=-h}^{\color{blue}{2q}} 1_{\{i=j\}}&\qquad -h\geq 0,-h\leq 2q \end{cases}\tag{4}\\ &= \begin{cases} \sum_{j=0}^{2q-h}1&\qquad\qquad\qquad\quad 0 \leq h\leq 2q\\ \\ \sum_{j=-h}^{2q}1&\qquad\qquad\qquad\quad 0\leq -h\leq 2q \end{cases}\tag{5}\\ &\,\,\color{blue}{=2q+1-|h|}\qquad\qquad\qquad\qquad\color{blue}{|h| \leq 2q}\tag{6} \end{align*} and the claim follows.

Comment:

• In (1) we shift the indices to start from $0$ and do the compensation in the the indicator function.

• In (2) we simplify the indicator function by shifting the index $i$ to start from $-h$.

• In (3) we see thanks to the simple indicator condition $\{i=j\}$ that we can set the lower limit of the index $i$ resp. $j$ depending on $h\geq 0$ resp. $-h\geq 0$.

• In (4) we also set the upper limit of the indices $i$ and $j$ depending on $h$.

• In (5) we simplify the inner sums.

• In (6) we simplify the sums and can write the condition for $h$ conveniently.

Answer 2

If $|h|>2q$, then you will never have $h+j-i=0$ and hence all the indicators will always be zero (hint: use the triangle inequality).

For other values of $h$, note that once I choose $j$ there is only at most one choice of $i$ for which $h+j-i=0$. So you simply have to count the possible choices of $j$ for which there exists such a suitable $i$.

Answer 3

There are $(2q+1)\times(2q+1)$ pairs $(i,j)$ being summed over. Arrange these in a grid. Put a number "$1$" over all pairs for which $h+j-i=0$, and a zero over the others. You will find that the ones are arranged in a diagonal line. You just need to count the number of ones on this line. For example, when $q=3$, $h=2$, you get

0 0 0 0 1 0 0
0 0 0 1 0 0 0
0 0 1 0 0 0 0
0 1 0 0 0 0 0
1 0 0 0 0 0 0
0 0 0 0 0 0 0
0 0 0 0 0 0 0

Answer 4

We have

$$\sum_{a=-q}^q \sum_{b=-q}^q \mathrm{1}_{h+a-b=0} = \sum_{a=-q}^q \sum_{b=-q}^q \mathrm{Res}_{z=0} \frac{1}{z^{h+1+a-b}} \\ = \mathrm{Res}_{z=0} \frac{1}{z^{h+1}} \sum_{a=-q}^q \frac{1}{z^a} \sum_{b=-q}^q z^b = \mathrm{Res}_{z=0} \frac{1}{z^{h+1}} \left(\sum_{b=-q}^q z^b\right)^2 \\ = \mathrm{Res}_{z=0} \frac{1}{z^{h+1}} \left(\frac{1}{z^q} \sum_{b=0}^{2q} z^b\right)^2 = \mathrm{Res}_{z=0} \frac{1}{z^{h+2q+1}} \frac{(1-z^{2q+1})^2}{(1-z)^2} \\ = \mathrm{Res}_{z=0} \frac{1}{z^{h+2q+1}} \frac{1-2z^{2q+1}+z^{4q+2}}{(1-z)^2}.$$

The three pieces here are: first,

$$[z^{h+2q}] \frac{1}{(1-z)^2} = h+2q+1$$

for $h+2q\ge 0$ or $h\ge -2q,$ second

$$-2 [z^{h+2q}] \frac{z^{2q+1}}{(1-z)^2} = -2 [z^{h-1}] \frac{1}{(1-z)^2} = -2h$$

for $h+2q\ge 2q+1$ or $h\ge 1,$ third

$$[z^{h+2q}] \frac{z^{4q+2}}{(1-z)^2} = [z^{h-2q-2}] \frac{1}{(1-z)^2} = h-2q-1$$

for $h+2q\ge 4q+2$ or $h\ge 2q+2.$

Collecting everything we have that when $q=0$ the sum becomes $\mathrm{1}_{h=0}$ so we may suppose that $q\ge 1.$ We then obtain zero when $h\lt -2q.$ We get when $-2q\le h\lt 1$ the value $h+2q+1.$ Next for $1\le h\lt 2q+1$ we find $-h+2q+1.$ For $h=2q+1$ we get $h+2q+1-2h = 0.$ Finally for $h\ge 2q+2$ we get zero, adding all three pieces. We conclude with the closed form

$$\bbox[5px,border:2px solid #00A000]{ [[\; |h| \le 2q \;]] \times (2q+1-|h|).}$$