2

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?

Travis Willse
  • 99,363
Diego Marques
  • 91
  • 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. – Diego Marques 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 – Narendra Deconda Sep 18 '18 at 12:58
  • @NarendraDeconda Ah yes of course I've oversight the $<$ sign! – user Sep 18 '18 at 13:04
  • @NarendraDeconda Anyway it should be $$...= \sum_{1 \leqslant k \leqslant n} \sum_{1 \leqslant k-j \lt k} {\frac{1}{k-j}}=...$$ – user Sep 18 '18 at 13:07
  • it will be $\sum_{k=1}^{n}\sum_{k-j=0}^{k-1} \dfrac{1}{k-j}$. There might be sume connfusion in using j in all the steps. Take $k-j$ as a different variable, say $\alpha$ and proceed further. In the end, replace $\alpha $ with j – Narendra Deconda Sep 18 '18 at 13:14
  • @NarendraDeconda Why are you assuming $0\le k-j\le k-1$? the sum considered implies $1\le k-j\le k-1$, the same error/typo is still present in your answer. – user Sep 18 '18 at 13:20
  • @gimusi, everywhere replace k with k-1 in my answers and comments. I hope that makes everything clear. In the question itself, the limits of j should be $1 \leq j \leq k-1$ – Narendra Deconda Sep 18 '18 at 13:23
  • How is the sum given in the OP $$Sn = \sum_{1 \leqslant k \leqslant n} \sum_{1 \leqslant j \lt k} {\frac{1}{k-j}}=\sum_{k=1}^{n}\sum_{j=1}^{k-1}\dfrac{1}{k-j}$$ equal to the one you started with $$S_n = \sum_{k=1}^{n}\sum_{j=1}^{k}\dfrac{1}{k-j}$$ – user Sep 18 '18 at 13:26
  • @gimusi, i have corrected it. thanks – Narendra Deconda Sep 18 '18 at 13:41
  • @NarendraDeconda Well done! Finally you get my point. Bye – user Sep 18 '18 at 13:51

2 Answers2

2

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

Narendra Deconda
  • 572
  • 3
  • 14
2

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

user
  • 154,566