2
$\begingroup$

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?

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

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

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

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

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