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.

  • $\begingroup$ Interesting identity. So, (+1) in any case. $\endgroup$ – 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*}

  • 1
    $\begingroup$ Very nice and elegant solution. (+1) $\endgroup$ – Markus Scheuer Jun 25 '20 at 7:09
  • $\begingroup$ Thanks for this answer. It definitely gives me a better way to think about things. $\endgroup$ – 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*}


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.