TAOCP 1.2.7 Exercise 25

Exercise 25. [M21] Let

$$ H_n^{(u,v)} = \sum_{1 \le j \le k \le n} \frac{1}{j^u k^v}. $$

What are $H_n^{(0,v)}$ and $H_n^{(u,0)}$? Prove the general identity

$$ H_n^{(u,v)} + H_n^{(v,u)} = H_n^{(u)}H_n^{(v)} + H_n^{(u+v)}. $$

Verified: no
Solve time: -

Solution

By definition,

$$ H_n^{(u,v)}=\sum_{1\le j\le k\le n}\frac1{j^uk^v}. $$

When $u=0$,

$$ H_n^{(0,v)} =\sum_{1\le j\le k\le n}\frac1{k^v} =\sum_{k=1}^n\sum_{j=1}^k\frac1{k^v} =\sum_{k=1}^n\frac{k}{k^v} =\sum_{k=1}^n k^{1-v}. $$

Hence

$$ H_n^{(0,v)}=H_n^{(v-1)}. $$

When $v=0$,

$$ H_n^{(u,0)} =\sum_{1\le j\le k\le n}\frac1{j^u} =\sum_{j=1}^n\sum_{k=j}^n\frac1{j^u} =\sum_{j=1}^n\frac{n+1-j}{j^u}. $$

Therefore

$$ H_n^{(u,0)} =(n+1)\sum_{j=1}^n\frac1{j^u}-\sum_{j=1}^n j^{1-u}, $$

$$ H_n^{(u,0)}=(n+1)H_n^{(u)}-H_n^{(u-1)}. $$

To prove the general identity, consider

$$ H_n^{(u)}H_n^{(v)} =\left(\sum_{j=1}^n\frac1{j^u}\right) \left(\sum_{k=1}^n\frac1{k^v}\right) =\sum_{j=1}^n\sum_{k=1}^n\frac1{j^uk^v}. $$

Partition the summation domain into the three disjoint regions $j<k$, $j>k$, and $j=k$. Then

$$ H_n^{(u)}H_n^{(v)} =\sum_{1\le j<k\le n}\frac1{j^uk^v} +\sum_{1\le k<j\le n}\frac1{j^uk^v} +\sum_{k=1}^n\frac1{k^{u+v}}. $$

Interchanging the dummy variables $j$ and $k$ in the second sum gives

$$ \sum_{1\le k<j\le n}\frac1{j^uk^v} =\sum_{1\le j<k\le n}\frac1{j^vk^u}. $$

Hence

$$ H_n^{(u)}H_n^{(v)} =\sum_{1\le j<k\le n}\frac1{j^uk^v} +\sum_{1\le j<k\le n}\frac1{j^vk^u} +H_n^{(u+v)}. $$

Now,

$$ H_n^{(u,v)} =\sum_{1\le j<k\le n}\frac1{j^uk^v} +\sum_{k=1}^n\frac1{k^{u+v}}, $$

and similarly,

$$ H_n^{(v,u)} =\sum_{1\le j<k\le n}\frac1{j^vk^u} +\sum_{k=1}^n\frac1{k^{u+v}}. $$

Adding these equations yields

$$ H_n^{(u,v)}+H_n^{(v,u)} =\sum_{1\le j<k\le n}\frac1{j^uk^v} +\sum_{1\le j<k\le n}\frac1{j^vk^u} +2H_n^{(u+v)}. $$

Comparing with the previous expression for $H_n^{(u)}H_n^{(v)}$,

$$ H_n^{(u,v)}+H_n^{(v,u)} =H_n^{(u)}H_n^{(v)}+H_n^{(u+v)}. $$

This completes the proof.

∎