1
$\begingroup$

Dear fellow members of Math.SE,

I am currently facing a challenge in comprehending a solution to an example problem presented in Donald Knuth's Concrete Mathematics. The problem is as follows:

\begin{align} S_n&=\sum_{1\leq j<k \leq n}\frac{1}{k-j} \\ &=\sum_{1\leq j <k+j \leq n}\frac{1}{k} \qquad \text{(by replacing $k$ with $k+j$)}\\ &=\sum_{1\leq k \leq n} \; \sum_{1\leq j \leq n-k} \frac{1}{k} \end{align}

I am having difficulty understanding the transition from the second line to the third line. Specifically, I am unsure how the author arrived at the breaking down of the limit into two separate summations. Thank you for your time and assistance!

$\endgroup$

2 Answers 2

1
$\begingroup$

From $1\leq j <k+j \leq n$ we have $k > 0$ so $k \ge 1$. We also have $j \le n-k$.

Similarly, $k \le n-j \le n-1$. Note that this is different than the third line which has $k \le n$, but this is correct because the inner sum is empty when $k=n$.

Finally, we have $j\ge 1$.

$\endgroup$
1
$\begingroup$

In the second line, we are adding over all values of $j$ and $k$ satisfying the condition $1 \le j < k+j \le n$; one way to do this is to fix a value of $k$, add over all values of $j$ that are valid for that fixed value of $k$, and then repeat this for all valid values of $k$.

To do this, we need to determine which values for j are valid for any particular value of $k$. Note that in the compound inequality above, since $k \ge 1$, the second inequality is really redundant; the remaining two inequalities, $1 \le j$ and $k+j \le n$, can be combined to give $1 \le j \le n-k$.

Next, we need to determine the valid values of $k$. Again looking at the compound inequality above, we have that $k \ge 1$ and (since $j \ge 1$) that $k \le n-1$; combining these gives us $1 \le k \le n-1$.

Now, taking some liberties with the notation for simplicity but also to make clear this is independent of the terms in the summation, we have that

$$\begin{align} \sum_{1 \le j < k+j \le n} &= \sum_{k=1, \; 1 \le j \le n-1} + \sum_{k=2, \; 1 \le j \le n-2} + \sum_{k=3, \; 1 \le j \le n-3} + \ldots + \sum_{k=n-2, \; 1 \le j \le 2} + \sum_{k=n-1, \; 1 \le j \le 1} \\[2mm] &= \sum_{1 \le k \le n-1} \; \sum_{1 \le j \le n-k} \end{align}$$

The upper limit on $k$ should really be $n-1$, not $n$ as given in the text, but as was noted previously, there is no valid value of $j$ for $k=n$ so this discrepancy adds no extra terms to the sum.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .