Does it hold that $\displaystyle\sum_{j=2}^{n-1}\sum_{k=1}^{j-1}\Big(\frac{2}{kj}-\frac{1}{k(n-j)}\Big)=0$?

Question

I am assigned in a homework to find the value of $s_{n,3}$, the Stirling number of the 1$^{\text{st}}$ kind with $k=3$. I came to a point where

$$s_{n,3}=n!\sum_{k=1}^{n-2}\sum_{j=k+1}^{n-1}\frac{1}{3kj(n-j)}\text{.}$$

However, for some small $n$, because of some typo in computer, I accidentally found that

$$s_{n,3}=(n-1)!\Big(H_{n-1}H_{n-2}-\sum_{k=1}^{n-2}\frac{H_k}{k}\Big)\text{,}$$

where $H_n$ is the $n^{\text{th}}$ harmonic number.

I was so happy because this is a more elegant form, only to find that I have a difficulty to prove it. After some routine work, the problem reduced to answer whether

$$\sum_{j=2}^{n-1}\sum_{k=1}^{j-1}\Big(\frac{2}{kj}-\frac{1}{k(n-j)}\Big)=0$$

holds. I also found that this is equivalent to ask whether

$$\sum_{k=1}^{n-1}\frac{1}{k^2}=\sum_{k=1}^{n-1}\sum_{j=n-k}^{n-1}\frac{1}{kj}$$

holds. That is, whether the sum of squares of reciprocal over diagonal equals the sum of reciprocal of products over upper right triangle of $[n-1]\times[n-1]$.

Can anyone here give me some hint? By the way, any other better form of $s_{n,3}$ is appreciated. Thanks!

Answer 1

Definition of $\,s_{n,k}\,$ : $\enspace\displaystyle \prod\limits_{v=0}^{n-1}(x-v) = \sum\limits_{k=0}^n (-1)^{n-k}s_{n,k}x^k$

You can start with $\enspace\displaystyle -\ln\prod\limits_{v=1}^n \left(1-\frac{x}{v}\right) =\sum\limits_{k=1}^\infty\frac{x^k}{k}\sum\limits_{v=1}^n\frac{1}{v^k}\enspace$ and

$\enspace\displaystyle -\ln\prod\limits_{v=1}^n \left(1-\frac{x}{v}\right) = -\ln\left(1+\left(\prod\limits_{v=1}^n \left(1-\frac{x}{v}\right)-1\right)\right) =$

$\enspace\displaystyle = -\ln(1+x) \circ \left(\prod\limits_{v=1}^n \left(1-\frac{x}{v}\right)-1\right) = \left(\sum\limits_{k=1}^\infty\frac{(-x)^k}{k}\right) \circ \left(\sum\limits_{k=1}^\infty\frac{(-x)^k}{n!}s_{n+1,k+1}\right) \enspace$ .

I'm not going to discuss the combinatorics of nested functions here, that's too much, and there's certainly appropriate literature on it.

We are looking at $\enspace\displaystyle [x^2]\left(-\ln\prod\limits_{v=1}^n \left(1-\frac{x}{v}\right) \right)\enspace$ and get

$\enspace\displaystyle \frac{1}{2}\sum\limits_{k=1}^n \frac{1}{k^2} = \frac{1}{2}H_n^2 - \frac{1}{n!}s_{n+1,3}\enspace$ and therefore $\enspace\displaystyle s_{n,3} = \frac{(n-1)!}{2} \left(H_{n-1}^2 - \sum\limits_{k=1}^{n-1} \frac{1}{k^2} \right) \,$ .

This is equivalent to your second formula for $\,s_{n,3}\,$, easily proofed by induction, because for $\,n\in\mathbb{N}\,$ it’s:

$\displaystyle \left(H_n^2 - \sum\limits_{k=1}^n \frac{1}{k^2} \right) - \left(H_{n-1}^2 - \sum\limits_{k=1}^{n-1} \frac{1}{k^2} \right) = 2\frac{H_{n-1}}{n} =$

$\displaystyle = 2\left(H_n H_{n-1} - \sum\limits_{k=1}^{n-1}\frac{H_k}{k} \right) - 2\left(H_{n-1}H_{n-2} - \sum\limits_{k=1}^{n-2}\frac{H_k}{k} \right) $

---

Notes about the question:

Induction is a good way to proof your assumption – as you’ve done.

$(1)\enspace$ Start:

$\hspace{1cm}\displaystyle \sum\limits_{j=2}^{n-1}\frac{2}{j} \sum\limits_{k=1}^{j-1}\frac{1}{k} |_{n=3} = 1 = \sum\limits_{j=2}^{n-1}\frac{1}{n-j} \sum\limits_{k=1}^{j-1}\frac{1}{k} |_{n=3}$

$(2)\enspace\displaystyle \sum\limits_{j=2}^{n-1}\frac{2}{j} \sum\limits_{k=1}^{j-1}\frac{1}{k}\enspace$ and $\enspace\displaystyle \sum\limits_{j=2}^{n-1}\frac{1}{n-j} \sum\limits_{k=1}^{j-1}\frac{1}{k}\enspace$ are growing in the same way:

$\hspace{1cm}\displaystyle \sum\limits_{j=2}^n\frac{2}{j} \sum\limits_{k=1}^{j-1}\frac{1}{k} - \sum\limits_{j=2}^{n-1}\frac{2}{j} \sum\limits_{k=1}^{j-1}\frac{1}{k} = \frac{2}{n}H_{n-1}$

$\hspace{1cm}\displaystyle \sum\limits_{j=2}^n\frac{1}{n+1-j} \sum\limits_{k=1}^{j-1}\frac{1}{k} - \sum\limits_{j=2}^{n-1}\frac{1}{n-j} \sum\limits_{k=1}^{j-1}\frac{1}{k} = \sum\limits_{j=1}^{n-1}\frac{1}{(n-j)j} = \frac{2}{n}H_{n-1}$

Answer 2

It is embarrassed that I haven't thought of induction! The answer lies in the last expression that whether

$$\sum_{k=1}^{n-1}\frac{1}{k^2}=\sum_{k=1}^{n-1}\sum_{j=n-k}^{n-1}\frac{1}{kj}$$ holds. It is convenient to ask the lower left version. That is, whether it holds that

$$\sum_{k=1}^{n-2}\sum_{j=1}^{n-k-1}\frac{1}{kj}+\sum_{k=1}^{n-1}\frac{1}{k^2}=\sum_{k=1}^{n-1}\sum_{j=1}^{n-1}\frac{1}{kj}\text{.}$$

Since it holds when $n=3$, we assume it holds for $n\geq3$. We claim that

$$\sum_{k=1}^{n-1}\sum_{j=1}^{n-k}\frac{1}{kj}+\sum_{k=1}^{n}\frac{1}{k^2}=\sum_{k=1}^n\sum_{j=1}^n\frac{1}{kj}\text{.}$$

By assumption, we have \begin{align*} \sum_{k=1}^{n-1}\sum_{j=1}^{n-k}\frac{1}{kj}+\sum_{k=1}^{n}\frac{1}{k^2}&=\bigg(\sum_{k=1}^{n-2}\sum_{j=1}^{n-k-1}\frac{1}{kj}+\sum_{j=1}^{n-1}\frac{1}{j(n-j)}\bigg)+\frac{1}{n^2}+\sum_{k=1}^{n-1}\frac{1}{k^2}\\ &=\frac{1}{n^2}+\sum_{k=1}^{n-1}\sum_{j=1}^{n-1}\frac{1}{kj}+\sum_{j=1}^{n-1}\frac{1}{j(n-j)}\\ &=\sum_{k=1}^n\sum_{j=1}^n\frac{1}{kj}\text{,} \end{align*} where the last equality is by the easy identity

$$\sum_{j=1}^{n-1}\frac{1}{j(n-j)}=\frac{2}{n}\sum_{j=1}^{n-1}\frac{1}{j}\text{.}$$

However, any combinatorial proof of this problem is welcomed!