Is this sum $\sum_{k=0}^{n}{n\choose k}\sum_{i=0}^{k}(-1)^i{k\choose i}H_{n+k-i}=H_{2n}$ correct?

Question

Given the double sum, which has a closed form of $H_{2n}$

$$\sum_{k=0}^{n}{n\choose k}\sum_{i=0}^{k}(-1)^i{k\choose i}H_{n+k-i}\tag1$$

Where $H_n$ is the Harmonic number

$(1)$ is quite an interesting sums which give a neat simple closed form, we encounters it while just messing a round with the sum calculator. How to go about proving it, we have not ideas.

How do we go about by showing that $(1)=H_{2n}$?

note: $$\sum_{k=0}^{n}{n\choose k}x^k=(1+x)^n\tag2$$

$$\sum_{k=1}^{n}(-1)^{k+1}{1\over k}{n\choose k}=H_n\tag3$$

Answer 1

This has nothing particular to do with harmonic numbers; it works for any sequence $a_n$.

The coefficient of $a_\ell$ in the sum $\sum_k{n\choose k}\sum_i (-1)^i {k\choose i} a_{n+k-i}$ is, with $n+k-i=\ell$, $$\sum_k {k\choose k-i}{n\choose k}(-1)^i =\sum_k {k\choose \ell-n}{n\choose k}(-1)^{k-(\ell-n)}={n\choose \ell-n}(1+(-1))^{2n-\ell}.\tag1$$ The second equation uses the identity, $$\sum_k{k\choose m}{n\choose k}x^{k-m}={n\choose m}(1+x)^{n-m}.\tag2$$

The right hand side of (1) shows that the coefficient of $a_\ell$ is equal to one if $\ell=2n$ and is equal to zero otherwise. Therefore $$\sum_k{n\choose k}\sum_i (-1)^i {k\choose i} a_{n+k-i}=a_{2n}. $$

Answer 2

Note: This supplementary information might be useful.

The main theme in OPs question are so-called binomial inverse pairs. A simple example of such pairs is given by sequences $(a_n)_{n\geq 0},(b_n)_{n\geq 0}$ which fulfil for $n\geq 0$ the following identities \begin{align*} a_n=\sum_{k=0}^n\binom{n}{k}b_k\qquad\text{resp.}\qquad b_n=\sum_{k=0}^n(-1)^{k+n}\binom{n}{k}a_k\tag{1} \end{align*}

One relation implies the other in (1). This can be seen via exponential generating functions.

Let $A(x)$ and $B(x)$ be two exponential generating functions

$$A(x)=\sum_{n=0}^\infty a_{n}\frac{x^n}{n!} \qquad\qquad\text{ and }\qquad\qquad B(x)=\sum_{n=0}^\infty b_{n}\frac{x^n}{n!}$$

The expressions in (1) are the coefficients of

\begin{align*} A(x)=B(x)e^x\qquad\text{and}\qquad B(x)=A(x)e^{-x}\tag{2} \end{align*} The relationship in (2) is obvious and so the relationship in (1) follows.

The most important characterization of the pair of inverse relation in (1) is the orthogonal relation the pair implies. This follows by substituting one pair into the other. We obtain for $n\geq 0$

\begin{align*} a_n&=\sum_{k=0}^n\binom{n}{k}b_k\\ &=\sum_{k=0}^n\binom{n}{k}\sum_{i=0}^k(-1)^{i+k}\binom{k}{i}a_i\tag{3}\\ &=\sum_{i=0}^n a_i\sum_{k=i}^n(-1)^{i+k}\binom{n}{k}\binom{k}{i} \end{align*} Hence the orthogonal relation is \begin{align*} \delta_{ni}=\sum_{k=i}^n(-1)^{i+k}\binom{n}{k}\binom{k}{i} \end{align*} with $\delta_{ni}$ the Kronecker Delta.

Next, we consider the following identity for Harmonic Numbers:

\begin{align*} H_n&=\sum_{k=1}^{n}(-1)^{k+1}\binom{n}{k}\frac{1}{k} \end{align*}

(See e.g. the related question for a proof) and we observe, that $(-1)^{n-1}H_n$ and $\frac{1}{n}$ are a binomial inverse pair:

\begin{align*} (-1)^{n-1}H_n=\sum_{k=1}^{n}\binom{n}{k}\frac{(-1)^{n-k}}{k}&\qquad&\frac{1}{n}=\sum_{k=1}^{n}\binom{n}{k}(-1)^{k-1}H_k \end{align*}

OPs identity

We obtain from (1) by substitution of one side into the other \begin{align*} \sum_{k=0}^n\binom{n}{k}b_k&=\sum_{k=0}^n\binom{n}{k}\sum_{i=0}^k(-1)^{k-i}\binom{k}{i}a_{i}\\ &=\sum_{k=0}^n\binom{n}{k}\sum_{i=0}^k(-1)^{i}\binom{k}{i}a_{k-i}=a_n \end{align*}

Setting $a_n=H_{n+p}$ with $p$ constant, the claim follows when setting $p=n$. \begin{align*} \color{blue}{\sum_{k=0}^n\binom{n}{k}\sum_{i=0}^k(-1)^{i}\binom{k}{i}H_{p+k-i}=H_{n+p}} \end{align*}