# Sum $\sum_{i = 1}^N \sum_{j = i + 1}^N \mathbb{I} (j - i \leqslant K)$

Let $$N,K$$ be non-negative integers. What's the value of the following sum?

$$S(N,K) = \sum_{i = 1}^N \sum_{j = i + 1}^N \mathbb{I} (j - i \leqslant K)$$

where $$\mathbb{I}(\mathcal P)=1$$ if $$\mathcal P$$ is a true proposition and $$\mathbb{I}(\mathcal P)=0$$ otherwise.

For example, if $$N=K$$, then $$S(N,N)$$ simply counts the number of pairs $$(i,j)$$ with $$i,j\in\{1,\dots,N\}$$ such that $$i, which is easily seen to be

$$S(N,N)=N(N-1)/2$$

Also it is easy to see that $$S(N,K)=S(N,N)$$ whenever $$K\ge N$$. I'm only having trouble with the case where $$K.

• It would be nice if your progress so far is demonstrated. – Lee David Chung Lin Apr 18 at 13:33
• Can you solve the problem for $K = N$? – John Hughes Apr 18 at 13:39
• @JohnHughes Yes, see edit. – becko Apr 18 at 13:44
• @LeeDavidChungLin I added some edits. Note that this is not homework, so I can't be 100% sure that an analytical solution exists. I just ran into this sum solving a different problem (also not homework). – becko Apr 18 at 13:45

## 2 Answers

Split the sum on $$i$$ until $$N-K$$, and from $$N-K+1$$ to $$N$$ respectively, call them $$S_1, S_2$$, where we assume $$1\le K < N$$ as the other cases have been dealt with in the post.

If $$i\le N-K$$, the sum on $$j$$ has all its $$K$$ terms, so $$S_1=K(N-K)$$

If $$i> N-K$$, the second sum has only $$N-i$$ terms, so $$S_2=\sum_{i=N-K+1}^{i=N}{(N-i)}=\sum_{k=0}^{k=K-1}k=\frac{K(K-1)}{2}$$

Putting it together:

$$\sum_{i = 1}^N \sum_{j = i + 1}^N \mathbb{I} (j - i \leqslant K)= KN-\frac{K(K+1)}{2}=\frac{K(2N-K-1)}{2}$$

• To be a bit more general, $S(K,N)=\min(K,N)\times[2N-\min(K,N)-1]$. – becko Apr 18 at 14:26
• That's the general form for all $N,K$ indeed – Conrad Apr 18 at 14:29
• I forgot to divide by 2 in my comment. – becko Apr 28 at 8:12

Hint: Just a manipulation $$S(N,K)=\sum _{i=1}^N\sum _{j=i+1}^N\mathbb{I}(j-i\leq K)=\sum _{i=1}^N\sum _{j=i+1}^N\mathbb{I}(j\leq K+i)=\sum _{i=1}^N\sum _{j=i+1}^{\min \{K+i,N\}}1\qquad\qquad\qquad$$$$\qquad\qquad\qquad\qquad\qquad\qquad\qquad=\sum _{i=1}^{N-K}\sum _{j=i+1}^{K+i}1+\sum _{i=N-K+1}^N\sum _{j=i+1}^N1.$$ Can you finish?