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

Question

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<j$, 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<N$.

Answer 1

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}$

Answer 2

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?