# 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.

## 1 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? 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. 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. Mar 18 '16 at 15:43
• @silentboy: You’re welcome. It sounds as if you’re getting a handle on it now. 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. Mar 18 '16 at 15:51