# Understanding the limit breakdown in a summation problem

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

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!

From $$1\leq j 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$$.

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.