Binomial identity involving Harmonic numbers

Question

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}]

Answer 1

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}]