# Binomial identity involving Harmonic numbers

Using numeric experiments, I have found the following identity $$k! H_k+\sum _{j=1}^k \frac{\sum _{i=j}^k (-1)^i \binom{k}{i} \left((j-i)^k-(-i-n+1)^k\right)}{j+n-1}=0$$ where $$H_k = \sum_{i=1}^k 1/i$$. This seems to hold for all $$k \ge 1$$ and $$n \ge 1$$.

It's fairly easy to check this for any fix $$k$$. But I am not able to prove it for general $$k$$. Induction also does not seem to work well in this case.

Update, you can check this with the following Mathematica code

Table[k!*HarmonicNumber[k] +
Sum[((-1)^(1 + i + k)*(-1 + i + n)^k*Binomial[k, i] +
Eulerian[k, i])*HarmonicNumber[-1 + i + n], {i, 0,
k}] ==
0, {k, 1, 6}, {n, 1, 10}]

• Those sums look a bit inclusion-exclusion principle -ey – Vladimir Lenin Dec 5 '20 at 22:17

This is not a whole solution but I think it can be salvaged. If we apply the well known identity $$a^k - b^k = (a-b) \cdot \sum\limits_{i=1}^{k-1} a^{k-1-i} b^i$$ for $$(a,b) = ((j-i),(-i-n+1))$$ then the conjecture above boils down to proving that:

$$\begin{eqnarray} rhs_\eta := \sum\limits_{j=1}^k \sum\limits_{i=j}^k \sum\limits_{\xi=\eta}^{k-1} (-1)^i \binom{k}{i} \binom{\xi}{\eta} (j-i)^{k-1-\xi} (1-i)^{\xi-\eta} = -k! H_k \cdot \delta_{\eta,0} \end{eqnarray}$$ for $$\eta=0,1,2,\cdots$$. This comes from the fact that the sum in question is now a polynomial in the variable $$n$$ whose all coefficients except for the zeroth term must vanish.

Let us take a look at the coefficient at the zeroth power of $$n$$ (meaning $$\eta=0$$). We have:

$$\begin{eqnarray} rhs_0 &=& -k + \sum\limits_{j=2}^k \sum\limits_{i=j}^k (-1)^i \binom{k}{i} \left( \frac{-(1-i)^k + (-i+j)^k}{j-1}\right) \\ &=& -k + \sum\limits_{i=1}^k (-1)^{i-1-k} (i-1)^k \binom{k}{i} \left( H_{i-1} - \psi^{(0)}_{i+1} + \psi^{(0)}_{k+1} \right) \\ &=& -k + \sum\limits_{i=0}^{k-1} (-1)^{i+k} i^k \binom{k}{i+1} \left(-\frac{1}{i+1} + H_k \right) \\ &=& -k+ \sum\limits_{i=0}^{k-1} (-1)^{i+k} i^k \binom{k}{i+1} \left(-\frac{1}{i+1} \right) + (1-k!) H_k \\ &=& -k+ (k - H_k) + (1-k!) H_k \end{eqnarray}$$

In the first line from the top we carried out a sum over $$\xi$$ since it is a geometric series. In the second line from the top we split the double sum into two sums and in the first sum we did the sum over $$j$$ whereas in the second sum we substituted for $$(i-j) \rightarrow i$$ and then we did the sum over $$j$$ as well. In the third line we substituted $$(i-1) \rightarrow i$$ and then we used the the relationship between the polygamma function and harmonic numbers. In the last two lines we did the remaining single sums by doing the usual tricks $$i^k = \left. d_t^k \exp(i t) \right|_{t=0}$$ and then using the binomial expansion to resum.

In order to complete the proof one needs to show that $$rhs_\eta =0$$ for all integer $$\eta >0$$ . This should not be hard to do.

In[530]:= n =.;

Table[Sum[(-1)^(i + xi - eta) Binomial[k, i] Binomial[xi, eta] If[
i == j && k - 1 == xi, 1, (j - i)^(k - xi - 1)] If[
i == 1 && xi == eta, 1, (i - 1)^(xi - eta)], {j, 1, k}, {i, j,
k}, {xi, eta, k - 1}] (-n)^eta, {k, 1, 5}, {eta, 0, k - 1}] //
Expand // MatrixForm

Table[-k +
Sum[(-1)^i Binomial[k, i] ((-(1 - i)^k + (-i + j)^k)/(-1 + j)) , {j,
2, k}, {i, j, k}], {k, 1, 5}]

Table[-k +
Sum[(-1)^(i - 1 + k) ((i - 1)^k)  Binomial[k,
i] (HarmonicNumber[i - 1] - PolyGamma[0, 1 + i] +
PolyGamma[0, 1 + k]), {i, 1, k}], {k, 1, 5}]

Table[-k +
Sum[(-1)^(i + k) ((i)^k)  Binomial[k,
i + 1] (-1/(i + 1) + HarmonicNumber[k]), {i, 0, k - 1}], {k, 1,
5}]
Table[-k +
Sum[(-1)^(i + k) ((i)^k)  Binomial[k, i + 1] (-1/(i + 1)), {i, 0,
k - 1}] + (1 - k!) HarmonicNumber[k], {k, 1, 5}]
Table[-k + (k - HarmonicNumber[k]) + (1 - k!) HarmonicNumber[k], {k,
1, 5}]