Double sum identity involving binomial coefficients, possibly connected to umbral calculus

Question

I would be interested in seeing an insightful proof, or really, any alternative proof of the identity $$ \begin{aligned} &\sum_{j=0}^h(x+1)^j\binom{h}{j}\sum_{k=0}^r\binom{r}{k}x^k(r-k+h-j)!=\sum_{j=0}^h\binom{h}{j}(r+j)!\sum_{i=0}^{j+r}\frac{x^i}{i!}. \end{aligned} $$ The only proof I've managed to come up with is surprisingly cumbersome. It can be seen in this answer by searching for the line, "This is the $x=-2$ case of the sum" in the section "Alternative formula of Wyman and Moser".

I ran across this identity in the course of proving the equality of the two expressions, $$ \varphi(h; n)=\sum_{i=0}^n(-1)^i\frac{2n}{2n-i}\binom{2n-i}{i}\nu(h,h+n-i), $$ where $$ \nu(h,h+n)=\sum_{k=0}^h(-1)^k\binom{h}{k}(n+h-k)!, $$ and $$ \varphi(h;n)=\sum_{i\ge0}(-1)^i\frac{n}{n-i}\binom{n-i}{i}\sum_{j=0}^h\binom{h}{j}k_{n-2i+j}, $$ where $$ k_r=r!\sum_{i=0}^r\frac{(-2)^i}{i!}. $$ The former is a formula of Touchard, related to double derangements and the ménage problem, and the latter is an, empirically discovered, generalization of a formula of Wyman and Moser for the ménage problem.

My feeling that this is connected with umbral calculus is rather vague. It comes from the observation that $$ \sum_{i\ge0}(-1)^i\frac{n}{n-i}\binom{n-i}{i}x^{n-2i} $$ is a rescaled Chebyshev polynomial of the first kind, and that the formula for $\varphi(h;n)$ comes from the umbral-style replacement of $x^{n-2i}$ with $\sum_{j=0}^h\binom{h}{j}k_{n-2i+j}$, while $$ \sum_{i=0}^n(-1)^i\frac{2n}{2n-i}\binom{2n-i}{i}x^{\frac{1}{2}(2n-2i)} $$ is a rescaled Chebyshev polynomial of the first kind of twice the index (in the variable $x^{1/2}$), with $\varphi(h;n)$ arising from the different umbral-style replacement of $x^{n-i}$ with $\nu(h,h+n-i)$. I don't know much about umbral calculus, and don't know whether there's any sort of transformation theory that would shed light on how the replacement of $x^n$ by $x_n$ has to change when polynomial identities are used (such as the identity relating Chebyshev polynomials to Chebyshev polynomials of twice the index). Any comments about umbral calculus would be a bonus, but my main question is about proof of the identity.

Answer 1

Here we derive a more general identity:

$$ \sum_{j=0}^{m} \binom{m}{j}(x+y)^j \sum_{k=0}^{n} \binom{n}{k} x^k (m-j+n-k)! = \sum_{j=0}^{m} \binom{m}{j} y^{m-j} (j+n)! \sum_{i=0}^{j+n} \frac{x^i}{i!}. \tag{*} $$

The proof is fairly simple and relies on the following identity:

$$ \int_{0}^{\infty} (t+x)^n e^{-t} \, \mathrm{d}t = n!\sum_{i=0}^{n} \frac{x^i}{i!}. $$

The above identity can be proved either by the mathematical induction on $n$ or using the Poisson process. Then

\begin{align*} \text{[LHS of (*)]} &= \sum_{j=0}^{m} \binom{m}{j}(x+y)^j \sum_{k=0}^{n} \binom{n}{k} x^k \int_{0}^{\infty} t^{m-j+n-k}e^{-t} \, \mathrm{d}t \\ &= \int_{0}^{\infty} (t+x+y)^m (t+x)^n e^{-t} \, \mathrm{d}t \\ &= \sum_{j=0}^{n} \binom{m}{j} y^{m-j} \int_{0}^{\infty} (t+x)^{j+n} e^{-t} \, \mathrm{d}t \\ &= \sum_{j=0}^{n} \binom{m}{j} y^{m-j} (j+n)! \sum_{i=0}^{j+n} \frac{x^i}{i!} \\ &= \text{[RHS of (*)]}. \end{align*}

Answer 2

This is a partial answer. Both, LHS and RHS are polynomials in $x$ of degree $r+h$. We use the coefficient of operator $[x^t]$ to denote the coefficient of $x^t$ of a series. We show the validity of the identity for all coefficients $[x^t]$ with $0\leq t\leq r,h$. In order to do so, we transform and simplify the LHS as well as the RHS proving thereby equality.

We do the easier part first and start with the RHS.

Let $0\leq t\leq r,h$. We obtain \begin{align*} \color{blue}{[x^t]}&\color{blue}{\sum_{j=0}^h\binom{h}{j}(r+j)!\sum_{i=0}^{j+r}\frac{x^i}{i!}}\\ &=\frac{1}{t!}\sum_{j=0}^h\binom{h}{j}(r+j)!\tag{1}\\ &=\frac{1}{t!}\sum_{j=0}^h\frac{h!}{j!(h-j)!}(r+j)!\\ &\,\,\color{blue}{=\frac{r!h!}{t!}\sum_{j=0}^h\binom{r+j}{j}\frac{1}{(h-j)!}}\tag{2} \end{align*}

Comment:

• In (1) we select the coefficient of $x^t$.

And now the somewhat more demanding LHS.

We obtain \begin{align*} \color{blue}{[}&\color{blue}{x^t]\sum_{j=0}^h(x+1)^j\binom{h}{j}\sum_{k=0}^r\binom{r}{k}x^k(r-k+h-j)!}\\ &=\sum_{k=0}^t\binom{r}{k}[x^{t-k}]\sum_{j=0}^h(x+1)^j\binom{h}{j}(r-k+h-j)!\tag{3}\\ &=\sum_{k=0}^t\binom{r}{t-k}[x^{k}]\sum_{j=0}^h(x+1)^j\binom{h}{j}(r-t+k+h-j)!\tag{4}\\ &=\sum_{k=0}^t\binom{r}{t-k}\sum_{j=k}^h\binom{j}{k}\binom{h}{j}(r-t+k+h-j)!\tag{5}\\ &=\sum_{k=0}^t\frac{r!}{(t-k)!(r-t+k)!}\sum_{j=k}^h\frac{j!}{k!(j-k)!}\,\frac{h!}{j!(h-j)!}(r-t+k+h-j)!\\ &=\frac{r!h!}{t!}\sum_{k=0}^t\sum_{j=k}^h\binom{t}{k}\binom{r-t+k+h-j}{h-j}\frac{1}{(j-k)!}\\ &=\frac{r!h!}{t!}\sum_{k=0}^t\sum_{j=0}^{h-k}\binom{t}{k}\binom{r-t+h-j}{h-j-k}\frac{1}{j!}\tag{6}\\ &=\frac{r!h!}{t!}\sum_{j=0}^h\sum_{k=0}^{h-j}\binom{t}{k}\binom{r-t+h-j}{h-j-k}\frac{1}{j!}\tag{7}\\ &=\frac{r!h!}{t!}\sum_{j=0}^h\left(\sum_{k=0}^{j}\binom{t}{k}\binom{r-t+j}{j-k}\right)\frac{1}{(h-j)!}\tag{8}\\ &\,\,\color{blue}{=\frac{r!h!}{t!}\sum_{j=0}^h\binom{r+j}{j}\frac{1}{(h-j)!}}\tag{9} \end{align*} and the claim follows.

Comment:

• In (3) we exchange the sums, rearrange terms and select the coefficient of $x^k$. Since we have $t\leq r$ we can set the upper index of the outer sum to $t$. Other terms do not contribute.

• In (4) we change the order of summation $k\to t-k$.

• In (5) we select the coefficient of $x^k$. Since $\binom{j}{k}=0$ if $j<k$, we set the lower index of the inner sum to $k$.

• In (6) we shift the index of the inner sum to start with $j=0$.

• In (7) we exchange the sums.

• In (8) we change the order of summation of the outer sum: $j\to h-j$.

• In (9) we finally apply the Chu-Vandermonde identity to the inner sum.