1

In Concrete Mathematics, after the "Rocky Road" equality, the authors introduce the problem $$\sum_{1\leq j< k\leq n} \frac{1}{k - j}$$

They eventually arrive at the solution involving letting $k \to k + j$ to simplify the sum.

$$\sum_{1\leq j< k + j\leq n} \frac{1}{k} = \sum_{1\leq k\leq n} \left( \sum_{1\leq j\leq n - k}\frac{1}{k} \right)$$

How did they arrive at the bounds for $j$ and $k$ in the second sum?

I assumed they would use the Iversonian identity $$[1\leq j < k + j \leq n] = [1\leq k + j\leq n][1\leq j < k + j]$$ but they derived something completely different.

The best I could figure out was that because $k + j \leq n$, then $j \leq n - k$, but I'm not sure how the $k + j$ disappeared in the outer-most sum. I would have assumed that since $k + j \leq n$ that it would become $1\leq k \leq n - j$.

user246500
  • 13

2 Answers2

1

Fix a particular value of $k$ in the outer summation. What values of $j$ are compatible with it? From the summation on the lefthand side we know that we must have $1\le j<k+j\le n$, so on the one hand we must have $1\le j$, and on the other we must have $j\le n-k$ (by subtracting $k$ from $k+j\le n$). Clearly $j$ can take on any value within that range, so we want to sum over that range; that is, we want

$$\sum_{1\le j\le n-k}\frac1k\;.$$

Now what are the possible values of $k$ in the outermost sum? Clearly $k$ can be as small as $1$, so the only real question is how big it can be. Since $j\ge 1$ and $k+j\le n$, in fact the maximum possible value of $k$ is $n-1$, taken when $j=1$, and we could have written

$$\sum_{1\le k\le n-1}\sum_{1\le j\le n-k}\frac1k\;.$$

However, there’s no harm in letting $k$ run up to $n$, since in that case the inner sum is empty and therefore equal to $0$.

Note that the limits on $k$ cannot depend on $j$: the index of the outer sum is set first, and then the index of the inner sum runs through its specified range. The limits on $j$ can depend on $k$, however, since $k$ is fixed first. This is exactly similar to the situation with iterated integrals. If you have an integral

$$\int_a^b\int_c^df(x,y)\,dxdy\;,$$

the inner limits $c$ and $d$ can depend on $y$, the outer variable of integration, but the outer limits $a$ and $b$ have to stand on their own: they can’t depend on $x$.

Brian M. Scott
  • 616,228
  • By similar reasoning, could summation be done on $k$ first? I think it would be $$\sum_{1\leq j\leq n - 1} \sum_{j+1\leq k\leq n} \frac{1}{j}$$ – user246500 Jun 07 '15 at 20:10
  • @user246500: You mean on $j$ first, I think. Yes, but not as you have it here. If you sum on $j$ first, let $\ell=k-j$; then for each value of $j$, $\ell$ runs from $1$ to $n-j$, so you get $$\sum_{1\le j\le n-1}\sum_{1\le\ell\le n-j}\frac1\ell;.$$ This is exactly the same as the second displayed line in my answer, once you rename $k$ to $j$ and $j$ to $\ell$. – Brian M. Scott Jun 07 '15 at 23:04
0

A diagram might help (see below).

enter image description here

Put $r=k-j$.
Summand becomes $\dfrac 1r$.

From the diagram we can see that $r$ can be 'contracted' to $1$ or 'stretched' to $n$ (actually $n-1$; see comment in original solution by Brian M. Scott) hence the summation for $r$ is taken as $ \sum_{1\leq r\leq n}$.

Also, for a given value of $r$, we can see that $j$ runs from $1$ to $n-r$. Hence the summation for $j$ is taken as $ \sum_{1\leq j\leq n-r}$.

Hence the original summation can be restated as follows: $$\begin{align} \sum_{1\leq j<k\leq n} \frac 1{k-j} &=\sum_{1\leq r\leq n} \left(\sum_{1\leq j\leq n-r} \frac 1r\right)\\ &=\sum_{1\leq k\leq n} \left(\sum_{1\leq j\leq n-k} \frac 1k\right) \qquad \text{using a new $k$ in place of $r$ WLOG}\quad \blacksquare \end{align}$$

Hypergeometricx
  • 22,657