1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It would be nice if your progress so far is demonstrated. $\endgroup$ – Lee David Chung Lin Apr 18 at 13:33
  • $\begingroup$ Can you solve the problem for $K = N$? $\endgroup$ – John Hughes Apr 18 at 13:39
  • $\begingroup$ @JohnHughes Yes, see edit. $\endgroup$ – becko Apr 18 at 13:44
  • 1
    $\begingroup$ @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). $\endgroup$ – becko Apr 18 at 13:45
2
$\begingroup$

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

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

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?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.