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

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.

• Interesting identity. So, (+1) in any case. – Markus Scheuer Jun 24 '20 at 12:37

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

• Very nice and elegant solution. (+1) – Markus Scheuer Jun 25 '20 at 7:09
• Thanks for this answer. It definitely gives me a better way to think about things. – Will Orrick Jun 26 '20 at 15:42

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, 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.