# Factoring inequalities on Double Summation (Donald Knuth's Concrete Mathematics)

If you have the Concrete mathematics book please refer to page 40 and 41.

So how come this given sum $$\sum_{1 \le j < k + j \le n} \frac{1}{k}$$

becomes

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

I do not understand how this is proven since to my understanding i am following from the book's method of factoring inequalities,

$$[1\le j < k+j \le n] = [1 \le j \le n][j < k+j\le n] \text{ or } [1\le k+j \le n][1 \le j < k+j]$$

And it doesn't look like the double summation above. I Tried simplifying the two above and it leads me to nowhere near the answer.

If $1\le j<k+j\le n$, then $1\le j$ and $k+j\le n$; the latter inequality is equivalent to $j\le n-k$, so $1\le j<k+j\le n$ implies that $1\le j\le n-k$, the inequality governing the inner summation. Thus, we want to find some expression such that

$$[1\le j<k+j\le n]=[\text{expression}][1\le j\le n-k]\;.$$

What part(s) of $1\le j<k+j\le n$ can we not infer from $1\le j\le n-k$? The inequality $1\le j\le n-k$ says everything about $j$ that can be inferred from $1\le j<k+j\le n$, and it also implies that $k\le n-1$, but it imposes no lower bound on $k$; the missing factor will have to take care of that.

The original inequality $1\le j<k+j\le n$ implies that $1\le k$, since $j<k+j$, and that $k<n$, since $k+1\le k+j\le n$; thus, it implies that $1\le k\le n-1$. The inequality $1\le j\le n-k$ gives us half of that, but it doesn’t say that $1\le k$. Thus, we should have

$$[1\le j<k+j\le n]=[1\le k][1\le j\le n-k]\;,$$

and you can fairly easily check that this is indeed the case. If we use this decomposition, we get

$$\sum_{1\le j<k+j\le n}\frac1k=\sum_{1\le k}\,\sum_{1\le j\le n-k}\frac1k\;.$$

This is technically correct, but it’s harder than necessary to work with. The inner summation is non-zero only for $k\le n-1$, so we might as well add this condition to the outer sum as well:

$$[1\le j<k+j\le n]=[1\le k\le n-1][1\le j\le n-k]\;,$$

and

$$\sum_{1\le j<k+j\le n}\frac1k=\sum_{1\le k\le n-1}\,\sum_{1\le j\le n-k}\frac1k\;.$$

This is a perfectly reasonable way to rewrite the original summation as a double summation, but as the marginal note in Concrete Mathematics points out, it’s a little messier than necessary. There is no harm in simplifying the outer condition to $1\le k\le n$ to get

$$[1\le j<k+j\le n]=[1\le k\le n][1\le j\le n-k]$$

and

$$\sum_{1\le j<k+j\le n}\frac1k=\sum_{1\le k\le n}\,\sum_{1\le j\le n-k}\frac1k\;:$$

when $k=n$, the inner summation is $0$ anyway.

• Master Class. Can you suggest any kind of resource for these techniques? – silentboy Mar 18 '16 at 15:14
• @silentboy: Not really, I’m afraid: the discussion in Concrete Mathematics is actually one of the best that I’ve seen. It’s probably not very helpful advice, but I will say that once you have some basics, seeing and working through lots of calculations involving summations probably does more than anything else to develop the skill. – Brian M. Scott Mar 18 '16 at 15:21
• Thanks. I got another two inequality previously. That doesn't help to reduce the double summation though. But I thought they weren't right. Reading your answer gave me an idea that that was right too. And I wrote a little program to show if these two are equivalent. Indeed they are. – silentboy Mar 18 '16 at 15:43
• @silentboy: You’re welcome. It sounds as if you’re getting a handle on it now. – Brian M. Scott Mar 18 '16 at 15:44
• Yeah. The other inequality look like same with changed indexes. But the expression remains 1/k. That made me fool. BUT: ideone.com/i8vhAL shows they are equal after the summation. – silentboy Mar 18 '16 at 15:51