# An interesting sum identity: $\sum \frac 1 {k_1\cdots k_m} = \sum_{k=1}^n \frac{(-1)^{k-1}}{k^m} \binom n k$

Fix a positive integer $$m$$. I am trying to prove $\sum \frac 1 {k_1\cdots k_m} = \sum_{k=1}^n \frac{(-1)^{k-1}}{k^m} \binom n k$ where the sum on the left is taken over all integer $$m$$-tuples $$(k_1,\dots,k_m)$$ such that $$1\le k_1\le \cdots\le k_m\le n$$. This comes immediately after having proved that $\sum_{k=1}^n b_k/k = \sum_{k=1}^n \frac{a_k}k \binom n k$ where $$b_n = \sum_{k=1}^n a_k\binom n k$$. There's a strong similarity, so I suspect that I should use this result to prove the above. In particular it suggests that we take $$a_k/k = (-1)^{k-1}/k^m$$ which is to say $$a_k = (-1)^{k-1}/k^{m-1}$$. If this is the right path then we want to show that $\sum\frac 1 {k_1\cdots k_m} = \sum_{k=1}^n \frac{b_k}k = \sum_{k=1}^n \frac 1 k \sum_{j=1}^k a_j\binom{k}j = \sum_{k=1}^n \frac 1 k \sum_{j=1}^k \frac{(-1)^{j-1}}{j^{m-1}}\binom{k}j$ Now trying to rearrange and reindex the sums basically just seems to get you back into the proof that $$\sum b_k/k = \sum a_k\binom n k /k$$ so that seems like a dead end.

I'm guessing that somehow, instead, we should find a more direct reason why these are equal, perhaps by splitting fractions. For instance, $$\frac 1 {2\cdot 3} = \frac{1}{2}-\frac{1}{3}$$ but there is no such simple splitting for $$\frac 1 {2\cdot 4}$$.

The right-hand side of the above seems to suggest that perhaps we fix a $$1\le k \le n$$ as the least number in $$(k_1,\dots,k_m)$$, and then use something that looks vaguely like inclusion-exclusion.

From here the question looks like "Is there a reason why, if we collect all the terms of $$\sum \frac 1 {k_1\cdots k_m}$$ with a fixed $$k_1$$, that the sum of these terms is $$\frac 1 k \sum_{j=1}^k \frac{(-1)^{j-1}}{j^m}\binom k j$$?"

Just to test the idea out, if we set $$n=4,m=2$$ and $$k_1=2$$ then we would be looking at the terms $\frac{1}{2\cdot 2}+\frac{1}{2\cdot 3}+\frac{1}{2\cdot 4}$ and on the other hand we would be trying to see whether this is the same as $\frac 1 2 \sum_{j=1}^2 \frac{(-1)^{j-1}}{j^2}\binom 2 j = \frac 1 2 \cdot \left( 2 - \frac 1 4 \right)$ A quick computation shows these are not equal, so then I'm not sure if I made a mistake along the way, or if the entire plan of attack is flawed.

If the entire plan is flawed, I don't have a plan B.

• In that third equation the final expression on the RHS inside the first summation is the same as the RHS of the identity you want to prove but with $m$ replaced by $m-1$. That suggests an induction on $m$; have you tried this? Commented Sep 17, 2022 at 18:59
• This is a very nice looking problem. Where did you find it? It seems there are quite a few methods to deal with it. Commented Sep 17, 2022 at 22:33
• @C-RAM It's problem 1.2.22 of the relatively new book by Douglas West, Combinatorial Mathematics. Commented Sep 17, 2022 at 22:42
• Although I should probably mention that in his statement of the problem he credits Dilcher and Woord for two different publications containing the equality. Commented Sep 17, 2022 at 22:45
• A small remark, this is the so-called Dilcher's formula, see e.g. mathworld.wolfram.com/DilchersFormula.html. Commented Jan 30, 2023 at 8:59

Let $$S_{m,n}$$ be your first sum, so $$$$\begin{split} S_{m+1,n}&=\sum_{1\leq k_1\leq\cdots\leq k_{m+1}\leq n}\frac{1}{k_1k_2\cdots k_mk_{m+1}}\\ &=\sum_{\ell=1}^n\left[\sum_{1\leq k_1\leq\cdots \leq k_m\leq\ell}\frac{1}{k_1k_2\cdots k_m\ell}\right]\\ &=\sum_{\ell=1}^n\frac{1}{\ell}S_{m,\ell}\\ \end{split}$$$$ Now, we proceed by induction on $$m$$. Suppose that $$$$S_{m,n}=\sum_{k=1}^n\frac{(-1)^{k-1}}{k^m}{n\choose k}$$$$ for all $$n\geq 0$$, then $$$$\begin{split} S_{m+1,n}&=\sum_{\ell=1}^n\frac{1}{\ell}S_{m,\ell}\\ &=\sum_{\ell=1}^n\frac{1}{\ell}\sum_{k=1}^\ell\frac{(-1)^{k-1}}{k^m}{\ell\choose k}\\ &=\sum_{\ell=1}^n\sum_{k=1}^\ell\frac{(-1)^{k-1}}{\ell k^m}{\ell\choose k}\\ \end{split}$$$$ Changing the order of summation gives us $$$$\begin{split} S_{m+1,n}&=\sum_{k=1}^n\sum_{\ell=k}^n\frac{(-1)^{k-1}}{\ell k^m}{\ell\choose k}\\ &=\sum_{k=1}^n\frac{(-1)^{k-1}}{k^m}\sum_{\ell=k}^n\frac{1}{\ell}{\ell\choose k}\\ &=\sum_{k=1}^n\frac{(-1)^{k-1}}{k^m}\sum_{\ell=k}^n\frac{1}{k}{{\ell-1}\choose {k-1}}\\ &=\sum_{k=1}^n\frac{(-1)^{k-1}}{k^{m+1}}\sum_{\ell=k}^n{{\ell-1}\choose {k-1}}\\ \end{split}$$$$ Finally, using a modified version of the hockey-stick identity $$\sum_{\ell=k}^n{{\ell-1}\choose {k-1}}={n\choose k}$$ (when $$n\geq k$$), we have that $$$$S_{m+1,n}=\sum_{k=1}^n\frac{(-1)^{k-1}}{k^{m+1}}{n\choose k}\\$$$$ which finishes our inductive step. Now, note that there exists one tuple of length $$0$$, and the empty product is defined as $$1$$, so by definition $$$$S_{0,n}=1=\sum_{k=1}^n\frac{(-1)^{k-1}}{k^0}{n\choose k}$$$$ where the second equality is true by the binomial theorem, which proves the base case. Therefore, by induction $$$$S_{m,n}=\sum_{k=1}^n\frac{(-1)^{k-1}}{k^m}{n\choose k}$$$$ for all $$m,n\geq 0$$.