Sums of binomial coefficients weighted by incomplete gamma

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$

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.

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