Finding a Closed Form for \(S_n\)
We add \(\frac{1}{k-j}\) over all pairs with \(1 \le j < k \le n\).
Rewrite the sum as a sum of harmonic numbers.
Substitute \(k \to k+j\) and collapse the inner sum directly.
We want a simple formula for \[ S_n=\sum_{1 \le j < k \le n}\frac{1}{k-j}. \]
This means: for every pair of whole numbers \(j\) and \(k\) between 1 and \(n\) with \(j
Worked Examples
- \(S_1=0\), because there are no valid pairs.
- \(S_2=1\), from the single pair \((1,2)\).
- \(S_3=\frac{1}{2-1}+\frac{1}{3-1}+\frac{1}{3-2}=1+\frac12+1=\frac52.\)
A Quick Reminder: Harmonic Numbers
The \(n\)th harmonic number is
For example, \[ H_1=1,\qquad H_2=\frac32,\qquad H_3=\frac{11}{6}, \] and by convention \(H_0=0\).
Rewrite \(S_n\) as a Sum of Harmonic Numbers
Step 1: Separate the two indices
Split the sum into an outer sum over \(k\) and an inner sum over \(j\):
Step 2: Re-index the inner sum
Replace the inner index by \(j \mapsto k-j\). Then the denominator becomes simply \(j\):
Step 3: Recognize a harmonic number
The inner sum is exactly \(H_{k-1}\), so:
Step 4: Tidy the index
Shift the index to get the cleaner form:
Find the Explicit Closed Form
Step 1: Substitute \(k \to k+j\)
Start again from the original sum and replace \(k\) by \(k+j\). This turns the denominator into \(k\):
Step 2: Sum over \(j\) first
For fixed \(k\), the index \(j\) ranges from 1 to \(n-k\). So:
Step 3: Collapse the inner sum
The inner sum adds \(\frac1k\) exactly \(n-k\) times, so:
Step 4: Split the summand
giving:
Step 5: Factor and evaluate
Pull out the constant \(n\) and count the second sum:
Combining the Two Results
Approach 1 gave \[ S_n=\sum_{0 \le k < n} H_k, \] while Approach 2 gave \[ S_n=nH_n-n. \]
Since both equal the same quantity, we get the identity:
So the sum of the first \(n\) harmonic numbers has a closed form in terms of \(H_n\).
What Did We Just Do?
The algebraic view
The key move in Approach 2 was replacing \(k\) by \(k+j\). Whenever a denominator involves a difference like \(k-j\), this kind of substitution is often useful because it isolates one variable and makes the inner sum trivial.
The geometric view
For \(n=4\), the valid pairs \((j,k)\) form a triangular region:
| \(k=1\) | \(k=2\) | \(k=3\) | \(k=4\) | |
|---|---|---|---|---|
| \(j=1\) | — | \(\frac11\) | \(\frac12\) | \(\frac13\) |
| \(j=2\) | — | — | \(\frac11\) | \(\frac12\) |
| \(j=3\) | — | — | — | \(\frac11\) |
| \(j=4\) | — | — | — | — |
Summing by rows gives \(H_3+H_2+H_1\). Summing by columns gives the same total. Summing by diagonals gives \[ \frac{3}{1}+\frac{2}{2}+\frac{1}{3}, \] because each diagonal has a constant value and a decreasing number of entries.
All three views count the same triangular array. The only thing that changes is the way the terms are grouped.
Frequently Asked Questions
These are the practical questions students usually have when first seeing this harmonic-number double sum.
Why does the sum start at \(S_1=0\)?
Because there are no pairs \((j,k)\) with \(1 \le j < k \le 1\). The summation region is empty.
Why is re-indexing helpful in Approach 1?
Because it turns the denominator \(k-j\) into a plain index, which makes the inner sum recognizable as a harmonic number.
Why does the substitution \(k \to k+j\) help in Approach 2?
Because the denominator becomes just \(k\), and then the inner sum simply counts how many times each reciprocal appears.
Why do rows, columns, and diagonals all give the same answer?
Because they are just different ways of grouping the same set of terms in the same triangular region.
What is the simplest thing to remember from this problem?
The sum depends only on the difference \(k-j\), and that makes diagonal regrouping and harmonic-number structure natural.
Comments
Post a Comment