Concrete Mathematics - 2.4 - sum of 1/k-j On the last part of finding the final solution for $$\sum_{j=1}^n\sum_{k=j+1}^n \frac{1}{k-j}$$
After replacing $k = k+j$, will result to:
$$ S_n = \sum_{1 \leqslant j < k+j \leqslant n} \frac{1}{k} $$
Which, by summing first on $j$, will give us:
$$ S_n = \sum_{1 \leqslant k \leqslant n} ( \sum_{1 \leqslant j \leqslant n-k} \frac{1}{k}) $$
But I don't understand how the last sum was obtained from the second (the one obtained after replacing $k = k+j$).
Can somebody help me and explain it to me please?
 A: Suppose that $j$ and $k$ are integers satisfying the condition $1\le j<k+j\le n$. Since $j<k+j$, it also means that $k\ge 1$. What is the largest possible value of $k$? We must have $k+j\le n$, and $j\ge 1$, so $k\le n-j\le n-1$. Thus, $k$ can be anything from $1$ through $n-1$. If we fix $k$, what does the condition tell us about $j$? Clearly $j\ge 1$. Moreover, since $k+j\le n$, we must have $j\le n-k$.
Conversely, if $1\le k\le n-1$, and $1\le j\le n-k$, then $1\le j<k+j\le n$, and the condition is satisfied. This shows that the condition
$$1\le j<k+j\le n$$
is equivalent to the condition
$$1\le k\le n-1\qquad\text{and}\qquad 1\le j\le n-k\;,$$
and hence that
$$\sum_{1\le j<k+j\le n}\frac1k=\sum_{k=1}^{n-1}\sum_{j=1}^{n-k}\frac1k\;.$$
This isn’t identical to the result in Concrete Mathematics, because I used the exact upper bound on the possible values of $k$, and they used $n$ instead. Notice, though, that when $k=n$, the inner summation has lower limit $1$ and upper limit $0$ and therefore evaluates to $0$ anyway, so that
$$\sum_{k=1}^n\sum_{j=1}^{n-k}\frac1k=\sum_{k=1}^{n-1}\sum_{j=1}^{n-k}\frac1k\;.$$
They knew that using too large an upper bound on $k$ would not cause problems, because the inner sum would be $0$ for the extra $k$ values, and chose to go with the simpler expression.
A: This question is like the change of integration in an integral.  In the original sum:
$$
\sum_{j=1}^n\sum_{k=j+1}^n\frac{1}{k-j},
$$
$j$ is chosen first and then $k$ is chosen to be larger than $j$.
The first step is, as you say, to substitute $l=k-j$ so that the sum becomes
$$
\sum_{j=1}^n\sum_{l=1}^{n-j}\frac{1}{l},
$$
Now, we change the order of summation; the smallest that $l$ can be is $1$ and the largest that $l$ can be is $n-1$.  Therefore, the outer sum is $\sum_{l=1}^{n-1}$.  For any particular $l$, the $j$'s that can generate that $l$ must satisfy $l\leq n-j$ or that $j\leq n-l$.  Therefore, the sum becomes
$$
\sum_{l=1}^{n-1}\sum_{j=1}^{n-l}\frac{1}{l}.
$$
The only difference in what you wrote is that it allows $l=n$, but in this case, the inner sum is an empty sum, so the value doesn't change.
A: $$\sum_{j=1}^{n}\sum_{k=j+1}^{n}\frac{1}{k-j}=\sum_{j=1}^{n-1}H_{n-j}=\sum_{k=1}^{n-1}H_k=\sum_{k=1}^{n-1}\sum_{h=1}^{k}\frac{1}{h}=\sum_{h=1}^{n-1}\frac{n-h}{h}=n H_{n-1}-n+1.$$
