Double summation, index change clarification.

Solution 1:

Let me introduce you to Iverson's convention: $[condition]$ is 1 if $condition$ is true, 0 (very much so, so that multiplied by $\infty$ it still gives 0) otherwise. I also like to write sums by giving conditions on their indices as "subindex", that puts all together and also makes it easy to write sums e.g. over the elements of a set, not just boring 1, 2, 3, ..., $n$ ones. If no conditions on the index, anything goes there. If useful, smash several sums into one sum over a collection of indices.

In those terms: $$ \sum_{2 \le k \le n} \sum_{1 \le j \le k - 1} \frac{1}{k - j} = \sum_k [2 \le k \le n] \sum_j [1 \le j \le k - 1] \frac{1}{k - j} \\ = \sum_{j, k} [2 \le k \le n] \cdot [1 \le j \le k - 1] \cdot \frac{1}{k - j} $$ We can juggle the sums around, as the outer $[]$ doesn't depend on $j$. And as the sums have no conditions once we moved those into $[]$, their order doesn't matter.

Now $[2 \le k \le n] \cdot [1 \le j \le k - 1]$ is 1 if both conditions are true, i.e., we can combine/rearrange/separate: $$ [2 \le k \le n] \cdot [1 \le j \le k - 1] = [1 \le j < k \le n] = [1 \le j < n] \cdot [j < k \le n] $$ After doing the same steps as above in reverse, this gives the rearranged sums: $$ \sum_{1 \le j \le n - 1} \sum_{j + 1 \le k \le n} \frac{1}{k - j} $$

Solution 2:

He’s simply made the substitution $m=k-j$ that he wrote next to the equals sign. It’s easy to see that that turns $\frac1{k-j}$ into $\frac1m$. To see what it does to the indexing of the sums, look at the pairs $\langle k,j\rangle$ for which the first double summation actually has terms:

$$\begin{array}{c|cc} k\backslash j&1&2&3&\dots&n-1\\ \hline 2&\frac1{2-1}\\ 3&\frac1{3-1}&\frac1{3-2}\\ 4&\frac1{4-1}&\frac1{4-2}&\frac1{4-3}\\ \vdots&\vdots&\vdots&\vdots&\ddots\\ n&\frac1{n-1}&\frac1{n-2}&\frac1{n-3}&\cdots&\frac11 \end{array}$$

When $m=k-j$ is $1$, we get the terms on the top diagonal; when it’s $2$, we get the terms on the second diagonal; and so on, down to the single term $\frac1{n-1}$ with denominator $n-1$ on the $(n-1)$-st diagonal. The double summation on the righthand side, then, is summing by diagonals. The first, or $m=1$, diagonal has $n-1$ terms; the second has $n-2$ terms; and in general the $m$-th has $n-m$ terms. These terms are all $\frac1m$, so we could jump directly to $$\sum_{m=1}^{n-1}\frac{n-m}m\;,$$ but your instructor took an intermediate step that doesn’t require drawing (or at least imagining) the array above.

If $m=k-j$, then $j=k-m$, and

$$\sum_{k=2}^n\sum_{j=1}^{k-1}\frac1{k-j}=\sum_{k=2}^n\sum_{k-m=1}^{k-1}\frac1m\;.$$

Now $m=k-(k-m)$, so as $k-m$ runs from $1$ to $k-1$, $m$ runs from $k-1$ to $k-(k-1)=1$. And we can certainly add up those terms in the opposite order without affecting the total, so

$$\sum_{k=2}^n\sum_{k-m=1}^{k-1}\frac1m=\sum_{k=2}^n\sum_{m=1}^{k-1}\frac1m\;.$$

Now just reverse the order of summation: if you look at all terms in the double sum, you see that $m$ can be anything from $1$ through $n-1$, and for each $m$, $k$ can be anything from $m+1$ through $n$, so

$$\sum_{k=2}^n\sum_{m=1}^{k-1}\frac1m=\sum_{m=1}^{n-1}\sum_{k=m+1}^n\frac1m\;.$$

(This step is just like reversing the order of integration back in calculus.) Finally, for each $m$ there are $n-m$ values of $k$, so

$$\sum_{m=1}^{n-1}\sum_{k=m+1}^n\frac1m=\sum_{m=1}^{n-1}\frac{n-m}m=n\sum_{m=1}^{n-1}\frac1m-\sum_{m=1}^{n-1}1=nH_{n-1}-(n-1)\;,$$

where $H_{n-1}$ is the $(n-1)$-st harmonic number.