Sums of binomial coefficients weighted by incomplete gamma

Question

I am interested in proving that

$$\sum_{k=0}^n\frac{k}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=1 $$ and $$\sum_{k=0}^n\frac{k^2}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}=2. $$ I verified it numerically for many values of $n$ and would like now to get to a proof. I rewrote it to make incomplete Gamma functions appear, but it is (apparently) not leading me further.

Has somebody ever encountered such an identity ? Is there an easy proof I am just completely missing ? I apologize if the question is trivial, I may lack some combinatorics tools.

Note: It was edited and should now be correct

Answer 1

Let $\mathbb{N}$ be the set $\left\{ 0,1,2,\ldots\right\} $.

If $n\in\mathbb{N}$ and $k\in\mathbb{N}$, then we shall use the notation $\genfrac{\{}{\}}{0pt}{0}{n}{k}$ for the number of set partitions of the set $\left\{ 1,2,\ldots,n\right\} $ into $k$ nonempty subsets. This is a Stirling number of the 2nd kind. We will mainly use the following formula: \begin{equation} \genfrac{\{}{\}}{0pt}{0}{n}{k}=\dfrac{1}{k!}\sum_{i=0}^{k}\left( -1\right) ^{i}\dbinom{k}{i}\left( k-i\right) ^{n}. \label{darij1.eq.stir=} \tag{1} \end{equation} For proofs of \eqref{darij1.eq.stir=}, see pretty much any text on enumerative combinatorics. For example, \eqref{darij1.eq.stir=} is the first equality sign of the formula (19) in David Galvin, Basic discrete mathematics, version 13 December 2017.

The definition of $\genfrac{\{}{\}}{0pt}{0}{n}{k}$ yields two facts:

• The number $\genfrac{\{}{\}}{0pt}{0}{n}{k}$ is a nonnegative integer for any $n\in\mathbb{N}$ and $k\in\mathbb{N}$.

• If $n\in\mathbb{N}$ and $k\in\mathbb{N}$ satisfy $k>n$, then \begin{equation} \genfrac{\{}{\}}{0pt}{0}{n}{k}=0 \label{darij1.eq.stir=0} \tag{2} \end{equation} (since there is no set partition of the set $\left\{ 1,2,\ldots,n\right\} $ into more than $n$ nonempty subsets).

(Of course, you can use \eqref{darij1.eq.stir=} as a definition of $\genfrac{\{}{\}}{0pt}{0}{n}{k}$, but then these two facts are not obvious.)

For any $n\in\mathbb{N}$, we define a number $B_{n}$ by \begin{equation} B_{n}=\sum_{k=0}^{n} \genfrac{\{}{\}}{0pt}{0}{n}{k}. \end{equation} This number $B_{n}$ is the number of all set partitions of the set $\left\{ 1,2,\ldots,n\right\} $ (since each addend $\genfrac{\{}{\}}{0pt}{0}{n}{k}$ in the sum counts those set partitions that have precisely $k$ parts). It is known as a Bell number.

The first Bell numbers are $B_{0}=1$, $B_{1}=1$, $B_{2}=2$, $B_{3}=5$ and $B_{4}=15$.

Now, for any $n\in\mathbb{N}$ and $p\in\mathbb{N}$, let me define the number \begin{equation} S_{p}\left( n\right) =\sum_{k=0}^{n}\dfrac{k^{p}}{k!}\sum_{l=0}^{n-k} \dfrac{\left( -1\right) ^{l}}{l!}. \end{equation}

You are conjecturing that $S_{1}\left( n\right) =1$ for all $n\geq1$, and that $S_{2}\left( n\right) =2$ for all $n\geq2$. These two equalities are particular cases of the following fact:

Theorem 1. Let $n\in\mathbb{N}$ and $p\in\mathbb{N}$ satisfy $n\geq p$. Then, $S_{p}\left( n\right) =B_{p}$.

But we can prove something even better:

Theorem 2. Let $n\in\mathbb{N}$ and $p\in\mathbb{N}$. Then, \begin{equation} S_{p}\left( n\right) =\sum_{k=0}^{n} \genfrac{\{}{\}}{0pt}{0}{p}{k}. \end{equation}

Proof of Theorem 2. The definition of $S_{p}\left( n\right) $ yields \begin{align*} S_{p}\left( n\right) & =\sum_{k=0}^{n}\dfrac{k^{p}}{k!}\underbrace{\sum _{l=0}^{n-k}\dfrac{\left( -1\right) ^{l}}{l!}}_{\substack{=\sum \limits_{j=k}^{n}\dfrac{\left( -1\right) ^{j-k}}{\left( j-k\right) !}\\\text{(here, we have}\\\text{substituted }j-k\\\text{for }l\text{ in the sum)}}}=\sum_{k=0}^{n}\dfrac{k^{p}}{k!}\sum_{j=k}^{n}\dfrac{\left( -1\right) ^{j-k}}{\left( j-k\right) !}\\ & =\underbrace{\sum_{k=0}^{n}\sum_{j=k}^{n}}_{=\sum_{j=0}^{n}\sum_{k=0}^{j} }\dfrac{k^{p}}{k!}\cdot\dfrac{\left( -1\right) ^{j-k}}{\left( j-k\right) !}=\sum_{j=0}^{n}\sum_{k=0}^{j}\dfrac{k^{p}}{k!}\cdot\dfrac{\left( -1\right) ^{j-k}}{\left( j-k\right) !}\\ & =\sum_{j=0}^{n}\underbrace{\sum_{k=0}^{j}\dfrac{k^{p}}{k!}\cdot \dfrac{\left( -1\right) ^{j-k}}{\left( j-k\right) !}}_{\substack{=\sum \limits_{k=0}^{j}\dfrac{\left( j-k\right) ^{p}}{\left( j-k\right) !} \cdot\dfrac{\left( -1\right) ^{k}}{k!}\\\text{(here, we have substituted }j-k\\\text{for }k\text{ in the sum)}}}=\sum_{j=0}^{n}\sum_{k=0} ^{j}\underbrace{\dfrac{\left( j-k\right) ^{p}}{\left( j-k\right) !} \cdot\dfrac{\left( -1\right) ^{k}}{k!}}_{=\dfrac{1}{j!}\cdot\left( -1\right) ^{k}\dfrac{j!}{k!\left( j-k\right) !}\left( j-k\right) ^{p}}\\ & =\sum_{j=0}^{n}\sum_{k=0}^{j}\dfrac{1}{j!}\cdot\left( -1\right) ^{k}\underbrace{\dfrac{j!}{k!\left( j-k\right) !}}_{=\dbinom{j}{k}}\left( j-k\right) ^{p}\\ & =\sum_{j=0}^{n}\sum_{k=0}^{j}\dfrac{1}{j!}\cdot\left( -1\right) ^{k}\dbinom{j}{k}\left( j-k\right) ^{p}=\sum_{j=0}^{n}\dfrac{1}{j!} \sum_{k=0}^{j}\left( -1\right) ^{k}\dbinom{j}{k}\left( j-k\right) ^{p}\\ & =\sum_{j=0}^{n}\dfrac{1}{j!}\sum_{i=0}^{j}\left( -1\right) ^{i}\dbinom {j}{i}\left( j-i\right) ^{p} \end{align*} (here, we have renamed the summation index $k$ as $i$). Comparing this with \begin{align*} & \sum_{k=0}^{n}\underbrace{ \genfrac{\{}{\}}{0pt}{0}{p}{k}}_{\substack{=\dfrac{1}{k!}\sum\limits_{i=0}^{k}\left( -1\right) ^{i} \dbinom{k}{i}\left( k-i\right) ^{p}\\\text{(by \eqref{darij1.eq.stir=}, applied to }p\text{ instead of }n\text{)}}}\\ & =\sum_{k=0}^{n}\dfrac{1}{k!}\sum\limits_{i=0}^{k}\left( -1\right) ^{i}\dbinom{k}{i}\left( k-i\right) ^{p}=\sum_{j=0}^{n}\dfrac{1}{j!} \sum_{i=0}^{j}\left( -1\right) ^{i}\dbinom{j}{i}\left( j-i\right) ^{p}\\ & \qquad\left( \text{here, we have renamed the summation index }k\text{ as }j\right) , \end{align*} we obtain $S_{p}\left( n\right) =\sum_{k=0}^{n} \genfrac{\{}{\}}{0pt}{0}{p}{k}$. This proves Theorem 2. $\blacksquare$

Proof of Theorem 1. For each $k\in\left\{ p+1,p+2,\ldots,n\right\} $, we have $k\geq p+1>p$ and thus \begin{equation} \genfrac{\{}{\}}{0pt}{0}{p}{k}=0 \label{darij1.pf.t1.1} \tag{3} \end{equation} (by \eqref{darij1.eq.stir=0}, applied to $p$ instead of $n$). Now, Theorem 2 yields \begin{align*} S_{p}\left( n\right) & =\sum_{k=0}^{n} \genfrac{\{}{\}}{0pt}{0}{p}{k}\\ & =\sum_{k=0}^{p} \genfrac{\{}{\}}{0pt}{0}{p}{k}+\sum_{k=p+1}^{n}\underbrace{ \genfrac{\{}{\}}{0pt}{0}{p}{k}}_{\substack{=0\\\text{(by \eqref{darij1.pf.t1.1})}}}\\ & \qquad\left( \text{here, we have split the sum at }k=p\text{, since }0\leq p\leq n\right) \\ & =\sum_{k=0}^{p} \genfrac{\{}{\}}{0pt}{0}{p}{k}+\underbrace{\sum_{k=p+1}^{n}0}_{=0}=\sum_{k=0}^{p} \genfrac{\{}{\}}{0pt}{0}{p}{k}=B_{p} \end{align*} (since the definition of $B_{p}$ yields $B_{p}=\sum_{k=0}^{p} \genfrac{\{}{\}}{0pt}{0}{p}{k}$). This proves Theorem 1. $\blacksquare$

Answer 2

We have $$ \sum_{k\geq 0}\frac{k}{k!}x^k = xe^x $$ and $$ \sum_{k\geq 0}\left(\sum_{l=0}^k\frac{(-1)^l}{l!}\right)x^k = \frac{e^{-x}}{1-x}. $$ Your first sum is the coefficient of $x^n$ in $$ xe^x\cdot \frac{e^{-x}}{1-x} = \frac{x}{1-x} =\sum_{n\geq 1}x^n. $$ Similarly, $$ \sum_{k\geq 0}\frac{k^2}{k!}x^k = x(1+x)e^x, $$ so the second sum is the coefficient of $x^n$ in $$ x(1+x)e^x\cdot \frac{e^{-x}}{1-x} = \frac{x(1+x)}{1-x} =x+ 2\sum_{n\geq 2}x^n. $$ In general we have for any integer $c\geq 0$ that $$ \sum_{k=0}^n\frac{k^c}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!} = B(n),\ \ n\geq c, $$ where $B(n)$ is a Bell number.

Answer 3

The first sum is (we use the change of variables $m=k-1$) $$\sum_{k+l\leqslant n}(-1)^l\frac{k}{k!l!}=\sum_{m+l\leqslant n-1}(-1)^l\frac1{m!l!}=\sum_{m+l\leqslant n-1}(-1)^l\binom{m+l}l\cdot \frac1{(m+l)!}.$$ If we fix the value of $m+l=N$, then $$\sum_{l\leqslant N}(-1)^l\binom{N}l=\begin{cases}1,\quad N=0\\0,\quad N>0.\end{cases}$$ Thus the result. For the second sum, we write $k^2=k(k-1)+k$, therefore $$ \sum_{k=0}^n\frac{k^2}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}= \sum_{k=0}^n\frac{k(k-1)}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}+ \sum_{k=0}^n\frac{k}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}, $$ the second sum is already shown to be equal to 1, in the first sum is (here only $k\geqslant 2$ matters, and we denote $m=k-2$) $$ \sum_{k=0}^n\frac{k(k-1)}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!}= \sum_{m+l\leqslant n-2}(-1)^l\frac1{m!l!}, $$ this is already calculated above and also equals to 1 (if $n\geqslant 2$ of course).

Answer 4

This is the generating function version of Darij's answer.

Define $$ S_p(n) = \sum_{k=0}^n\frac{k^p}{k!}\sum_{l=0}^{n-k}\frac{(-1)^l}{l!} = \sum_{t=0}^n \frac{1}{t!} \sum_{k=0}^t \binom{t}{k}k^p(-1)^{t-k},$$ where all I did is write $t=k+l$.

The exponential generating function wrt $p$ is $$ \sum_{p=0}^\infty S_p(n)\frac{x^p}{p!} = \sum_{t=0}^n \frac{1}{t!} (e^x-1)^t,$$ by summing over $p$ and then over $k$.

Note that $\frac{1}{t!}(e^x-1)^t$ is the exponential generating function for the Stirling numbers $\genfrac{\{}{\}}{0pt}{0}{p}{t}$. Also note that the lowest power of $x$ appearing in $(e^x-1)^t$ is $x^t$ so for $n\ge p$ you might as well take the infinite sum $e^{e^x-1}$ which is the generating function for the Bell numbers.

Answer 5

A combinatorial proof may not be easy, or even considered proper, but it could shed some light on the meaning of these formulae.

The sum with alternating signs resembles the definition of derangements: \begin{equation*} d(n) = n! \sum_{i=0}^n \frac{(-1)^i}{i!}. \end{equation*} This is the number of permutations where no element appears in its original position. It is straightforward to rewrite the first equation as \begin{equation*} \sum {n \choose k} \cdot k \cdot d(n-k) = n! \label{r1}\tag{r1} \end{equation*}

The role of the factor $k$ is not obvious, so assume for a moment that it is not there (!), and focus on: \begin{equation*} \sum {n \choose k} \cdot d(n-k) = n! \label{r2}\tag{r2} \end{equation*}

This new equation allows for a fairly simple combinatorial proof: On the one hand we are counting in how many ways a class of $n$ students can be rearranged, and the result is $n!$ by definition of permutation.

On the other hand, we observe that in any given permutation each element can either stay in its original position or not. Let's say that $k$ students keep their place: there are ${n \choose k}$ ways to select those, and $d(n-k)$ ways to scramble the others. By summing over $k$ we cover all permutations without overlap.

We found a partition of permutations, and this can be a starting point to attack the original problem. We can prove (\ref{r1}) with a slight variation of the above: We count in how many ways a class of $n$ students can be rearranged, given that one student at random will receive a red hat and will not change place. There are $n$ ways to extract who will receive the red had, and $(n-1)!$ ways to rearrange the others, for a total of $n!$.

On the other hand, we select $k$ students that will not change place, then pick at random one of those and give her the hat, finally scramble the rest. The product of the number of way for these three actions gives one addend in LHS of (\ref{r1}).

The partition of the permutations in (\ref{r2}) is maybe surprising on its own, but together with (\ref{r1}) is a kind of magic: apparently we can add or drop a factor $k$ with no effect on the result. This until we consider that the sums distribute weights differently. A striking difference is for $k=0$, where $d(n-k)$ is maximum in (\ref{r2}) but nullified in (\ref{r1}).

We might now want to go further and attempt the second equation. This can be rewritten as \begin{equation*} \sum {n \choose k} \cdot k^2 \cdot d(n-k) = 2 \cdot n! \label{r3}\tag{r3} \end{equation*}

The same reasoning can be adapted: Each student has $2$ lottery tickets, and each can get with the same probability and independently a red hat and a blue scarf. Each winner will stay in its original position, while the others are allowed to move. In how many ways we can do that? There are two mutually exclusive cases, either we have only one winner for both prizes, $n$ ways, and that others are rearranged, $(n-1)!$ ways; or we have two winners, $n\cdot (n-1)$ ways, and the others are rearranged, $(n-2)!$ ways. Two cases but same results, so $2 \cdot n!$.

On the other hand, the winners belong to the $k$ students that will not change place. We pick $k$ students who do not move, ${n \choose k}$ ways, assign two prizes independently, $k^2$ ways, and derange the others, $d(n-k)$ ways.

This is quite remarkable, and would be a pity to stop here. What if we added more prizes, a pair of green gloves, a yellow whistle, etc. for a total of $m$ gifts? The reasoning above can be applied in a straightforward way to the LHS of (\ref{r3}), simply changing $k^2$ with $k^m$.

A bit more work is needed for the RHS, which so far was the easiest. The number of ways to group $m$ prizes is $B(m)$, the $m$-th Bell number. Now a final treat. Assume the prizes are distributed to $r$ winners. We can select the winners in $n\cdot(n-1)\cdot\ldots\cdot(n-r+1)$ ways and rearrange the others in $(n-r)!$ ways. It is very convenient, because we always have $n!$ for each of the possible grouping of prizes regardless of the number of winners. This concludes the combinatorial interpretation of \begin{equation*} \sum {n \choose k} \cdot k^m \cdot d(n-k) = B(m) \cdot n! \label{r4}\tag{r4} \end{equation*}