Splitting up compound inequalities of multiple variables

Question

I'm reading through Concrete Mathematics 2nd ed. In the last example in section 2.4 Multiple Sums (p.40), they go from this:

$$ \sum_{1\le j < k+j\le n} \frac{1}{k} $$

to this, in one step:

$$ \sum_{1\le k\le n} \sum_{1\le j\le n-k} \frac{1}{k} $$

The purpose is to sum first on $j$ which is desirable since $j$ does not appear in $\frac1k$. ($n$ is constant while $j,k$ are index variables.)

I can understand this step graphically by plotting it, but I can't figure out how they did it purely symbolically. Is there a general non-graphical way to split up these compound inequalities, i.e. to factor out a certain variable like $j$?

Answer 1

We obtain \begin{align*} \sum_{\color{blue}{1\leq j<k+j\leq n}}\frac{1}{k}&=\sum_{{1\leq k\leq n-1,1\leq j\leq n-1}\atop{k+j\leq n}}\frac{1}{k}\tag{1}\\ &=\sum_{1\leq k\leq n-1}\sum_{1\leq j\leq n-k}\frac{1}{k}\tag{2}\\ &=\sum_{\color{blue}{1\leq k\leq n}}\sum_{\color{blue}{1\leq j\leq n-k}}\frac{1}{k}\tag{3} \end{align*}

Comment:

• In (1) we write the index region of the RHS somewhat more conveniently as preparation for the next step(s). We conclude thereby from $1\leq j<k+j$ that $k\geq 1$ and from $k+j\leq n$ that $k\leq n-1$ resulting in $1\leq k\leq n-1$. Analogously we see that $j\leq n-1$, since $k+j\leq n$ and $k\geq 1$.

• In (2) we use from (1) that $j\leq n-k$, since $k+j\leq n$. We observe from (1) that both $1\leq j\leq n-1$ and $j\leq n-k$ has to be valid which can be written as $1\leq j\leq n-k$.

• In (3) we write for convenience only $n$ instead of $n-1$ as upper limit of the index $k$ without changing anything, since the index region $1\leq j\leq 0$ of the inner sum is then the empty set, i.e. the inner sum $\sum_{1\leq j\leq 0}\frac{1}{k}=0$ when $k=n$.