# Help to understand $\sum_{1 \leqslant k \leqslant n} \sum_{1 \leqslant j \lt k} {\frac{1}{k-j}}$

I got this summation from the book Concrete Mathematics which I didn't exactly understand:

\begin{align} Sn &= \sum_{1 \leqslant k \leqslant n} \sum_{1 \leqslant j \lt k} {\frac{1}{k-j}} \\ &= \sum_{1 \leqslant k \leqslant n} \sum_{1 \leqslant k-j \lt k} {\frac{1}{j}} \\ &= \sum_{1 \leqslant k \leqslant n} \sum_{0 \lt j \leqslant k-1} {\frac{1}{j}} \\ \end{align}

I didn't understant why $1 \leqslant j \lt k$ became $1 \leqslant k-j \lt k$ in the second line and why $1 \leqslant k-j \lt k$ became $0 \lt j \leqslant k-1$ in the third line.

Can you guys help me understanding that?

• It seems there is a typo, are you sure of those expressions?
– user
Sep 18 '18 at 12:46
• I am sure they are correct. Just double checked. Sep 18 '18 at 12:47
• I don't understand the step in teh middle but the final is clear.
– user
Sep 18 '18 at 12:48
• middle step is just writing the limits of j some other way Sep 18 '18 at 12:58
• @NarendraDeconda Ah yes of course I've oversight the $<$ sign!
– user
Sep 18 '18 at 13:04

$$S_n = \sum_{k=1}^{n}\sum_{j=1}^{k-1}\dfrac{1}{k-j}$$

Let $k-j =\alpha$. Limits of $\alpha$ will be $1 \leq \alpha \leq k-1$, which is same as $1 \leq k-\alpha \leq k-1$.

$$\implies S_n = \sum_{k=1}^{n}\sum_{k-\alpha=1}^{k-1}\dfrac{1}{\alpha} =\sum_{k=1}^{n}\sum_{\alpha=1}^{k-1}\dfrac{1}{\alpha}= \sum_{k=1}^{n}\sum_{j=1}^{k-1}\dfrac{1}{j}$$

• The first should be $S_n = \sum_{k=1}^{n}\sum_{j=1}^{k-1}\dfrac{1}{k-j}$
– user
Sep 18 '18 at 12:47
• $0 \leq \alpha \leq k-1$ can also be written as $1 \leq k-\alpha \leq k$. I guess the question is correct Sep 18 '18 at 12:50
• I'm referring to the first line, in the OP $1\le j<k$ that is $1\le j\le k-1$.
– user
Sep 18 '18 at 13:03
• yes. the summation wont exist if j takes the value of k. it should be $1 \leq j \leq k-1$ Sep 18 '18 at 13:06

From here

$$S_n = \sum_{1 \leqslant k \leqslant n} \sum_{1 \leqslant j \lt k} {\frac{1}{k-j}}=\ldots$$

since $k-j$ goes from $k-1$ down to $1$ we have

$$\ldots=\sum_{1 \leqslant k \leqslant n} \, \sum_{1 \leqslant k-j \lt k} {\frac{1}{k-j}} =\ldots$$

now we change name to the index using $j$ insted of $k-j$

$$\ldots=\sum_{1 \leqslant k \leqslant n} \,\sum_{1 \leqslant j\lt k} {\frac{1}{j}}=\sum_{1 \leqslant k \leqslant n} \,\sum_{0 \lt j\leqslant k-1} {\frac{1}{j}}$$