Multi-Index Summation: A Second Look Through Harmonic Numbers

Finding a Closed Form for \(S_n\)

We want to find a simple formula for the following sum, which we call \(S_n\):

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

This notation means: add up \(\frac{1}{k-j}\) for every pair of whole numbers \(j\) and \(k\) where \(j\) is strictly less than \(k\), and both are between 1 and \(n\). In other words, we are summing over every pair where \(j\) comes before \(k\).

Worked Examples

Let's check a few small values to get a feel for the sum:

• \(S_1 = 0\) — there are no valid pairs when \(n = 1\), so the sum is empty.
• \(S_2 = 1\) — the only pair is \((j, k) = (1, 2)\), giving \(\frac{1}{2-1} = 1\).
• \(S_3 = \frac{1}{2-1} + \frac{1}{3-1} + \frac{1}{3-2} = 1 + \frac{1}{2} + 1 = \frac{5}{2}\).

---

A Quick Reminder: Harmonic Numbers

Before diving in, it helps to know what a harmonic number is. The \(n\)th harmonic number \(H_n\) is just the sum of the reciprocals of the first \(n\) whole numbers:

$$H_n = 1 + \frac{1}{2} + \frac{1}{3} + \cdots + \frac{1}{n} = \sum_{1 \le k \le n} \frac{1}{k}$$

For example, \(H_1 = 1\), \(H_2 = \frac{3}{2}\), \(H_3 = \frac{11}{6}\). We also define \(H_0 = 0\).

---

Approach 1 — Rewrite as a Sum of Harmonic Numbers

The goal of this first approach is to rewrite \(S_n\) in terms of harmonic numbers, which we already know how to handle.

Step 1: Separate the two indices

The original sum runs over all pairs \((j, k)\) at once. We can split it into two nested sums — an outer sum over \(k\), and for each fixed \(k\), an inner sum over all valid values of \(j\):

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

Step 2: Substitute \(j \to k - j\)

The expression \(\frac{1}{k-j}\) is awkward because both \(j\) and \(k\) appear in the denominator. We can simplify it by replacing \(j\) with \(k - j\) — think of this as relabeling the inner index so that \(j\) ends up alone in the denominator instead of \(k - j\):

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

Step 3: Simplify the bounds on \(j\)

The condition \(1 \le k - j \lt k\) can be simplified. Subtracting \(k\) and flipping signs, it becomes \(0 \lt j \le k - 1\):

$$S_n = \sum_{1 \le k \le n} \sum_{0 \lt j \le k-1} \frac{1}{j}$$

Step 4: Recognize the inner sum as a harmonic number

The inner sum \(\sum_{0 \lt j \le k-1} \frac{1}{j}\) is just \(1 + \frac{1}{2} + \cdots + \frac{1}{k-1}\), which is exactly the definition of \(H_{k-1}\):

$$S_n = \sum_{1 \le k \le n} H_{k-1}$$

Step 5: Re-index to tidy up

The \(k - 1\) inside \(H_{k-1}\) is a little untidy. We can substitute \(k \to k + 1\) (shifting the index up by 1) to clean it up. When \(k\) runs from 1 to \(n\), \(k + 1\) runs from 2 to \(n + 1\), so the bounds become \(1 \le k + 1 \le n\), which simplifies to \(0 \le k \lt n\):

$$\boxed{S_n = \sum_{0 \le k \lt n} H_k}$$

This is a cleaner form, but we can go further — see Approach 2.

---

Approach 2 — Find the Explicit Closed Form

Now we start fresh and find an explicit formula with no sums at all.

Step 1: Substitute \(k \to k + j\)

Going back to the original sum, we replace \(k\) with \(k + j\). This shifts the variable so that the denominator \(k - j\) becomes simply \(k\), which is much easier to work with:

$$S_n = \sum_{1 \le j + k \le n,\ j \ge 1,\ k \ge 1} \frac{1}{k}$$

Step 2: Sum on \(j\) first

For a fixed value of \(k\), the index \(j\) can range from 1 up to \(n - k\) (since we need \(j + k \le n\)). Pulling out \(\frac{1}{k}\), which does not depend on \(j\) at all:

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

Step 3: Collapse the inner sum

The inner sum \(\sum_{1 \le j \le n-k} \frac{1}{k}\) is just adding \(\frac{1}{k}\) a total of \(n - k\) times, so it equals \(\frac{n-k}{k}\):

$$S_n = \sum_{1 \le k \le n} \frac{n - k}{k}$$

Step 4: Split the fraction

We can split \(\frac{n-k}{k}\) into \(\frac{n}{k} - 1\) and then separate the two resulting sums:

$$S_n = \sum_{1 \le k \le n} \frac{n}{k} - \sum_{1 \le k \le n} 1$$

Step 5: Factor and evaluate

Since \(n\) does not depend on \(k\), it factors out of the first sum. The second sum just counts how many values of \(k\) there are, which is \(n\):

$$S_n = n \left(\sum_{1 \le k \le n} \frac{1}{k}\right) - n$$

The sum in parentheses is exactly the definition of \(H_n\), so:

$$\boxed{S_n = nH_n - n}$$

---

Combining the Two Results

Approach 1 showed that \(S_n = \sum_{0 \le k \lt n} H_k\), and Approach 2 showed that \(S_n = nH_n - n\). Since both equal \(S_n\), we get a useful identity for free:

$$\sum_{0 \le k \lt n} H_k = nH_n - n$$

In other words, the sum of the first \(n\) harmonic numbers equals \(nH_n - n\).

---

What Did We Just Do? — Two Ways of Seeing It

The Algebraic Takeaway

In Approach 2, the key move was replacing \(k\) with \(k + j\). This is a general trick: whenever a double sum has terms involving \(k - j\) or \(k + j\) in the denominator, it is often worth substituting to put \(k\) alone in the denominator, then summing on \(j\) first. The inner sum becomes trivial, and the outer sum collapses into something manageable.

The Geometric Takeaway

We can also see what happened visually. For \(n = 4\), the pairs \((j, k)\) we are summing over form a triangle:

	\(k=1\)	\(k=2\)	\(k=3\)	\(k=4\)
\(j=1\)	—	\(\frac{1}{1}\)	\(\frac{1}{2}\)	\(\frac{1}{3}\)
\(j=2\)	—	—	\(\frac{1}{1}\)	\(\frac{1}{2}\)
\(j=3\)	—	—	—	\(\frac{1}{1}\)
\(j=4\)	—	—	—	—

Summing by rows (fixing \(j\), varying \(k\)) gives the row totals \(H_3,\ H_2,\ H_1,\ 0\), so the grand total is \(H_1 + H_2 + H_3\).

Summing by columns (fixing \(k\), varying \(j\)) gives the column totals \(0,\ H_1,\ H_2,\ H_3\), which is the same set of numbers in the same order — \(H_1 + H_2 + H_3\).

Summing by diagonals (fixing \(k - j\)) gives \(\frac{3}{1} + \frac{2}{2} + \frac{1}{3}\), since along each diagonal the value \(\frac{1}{k-j}\) is constant and the diagonal has a decreasing number of entries. This is exactly the sum we computed in Approach 2 after collapsing the inner sum.

All three perspectives — rows, columns, diagonals — give the same grand total. That is the geometry behind interchanging the order of summation.