# Proving $\sum\limits_{k=0}^n \sum\limits_{j=0}^{n-k} \frac{(k-1)^2}{k!} \frac{(-1)^j}{j!} =1$ without character theory

Let $n \geq 2$ be an integer. I would like to prove the following identity in an easy way: $$\sum\limits_{k=0}^n \left( \frac{(k-1)^2}{k!} \sum\limits_{j=0}^{n-k} \frac{(-1)^j}{j!} \right)=1$$

You can see on WolframAlpha, for $n=3$, that this holds.

Here is nice proof I've found. However it seems to be awfully sophisticated... Consider the representation $S_n \to \text{GL}(V)$ where $V=\text{span}_{\Bbb C}(e_1-e_2, \dots, e_1-e_n)$ and $\sigma \cdot (e_1-e_i) := e_{\sigma(1)}- e_{\sigma(i)}\,$. It is well-known that this is an irrep: we can show that if $0\neq u \in V$, then $\text{span}_{\Bbb C}(\{\sigma \cdot u \mid \sigma \in S_n\}) = V$.

In particular, the scalar product of character is $\langle \chi_{V}, \chi_V \rangle=1$. But $\chi_V = \chi_{S_n} - \chi_1$ where $\chi_{S_n}$ is the permutation character of $S_n$ and $\chi_{1}$ the trivial character.

$\newcommand{\supp}{\text{supp}}$ Therefore, if $\supp(\sigma)$ denotes the support of a permutation $\sigma$, we have: \begin{align} \langle \chi_{V}, \chi_V \rangle &= \frac{1}{n!} \sum\limits_{\sigma \in S_n} |\chi_{S_n}(\sigma)-1|^2\\&= \frac{1}{n!} \sum\limits_{\sigma \in S_n} \left|\text{card}(\{1, \dots, n\} \setminus \supp(\sigma)) \;-\; 1\right|^2\\&= \frac{1}{n!} \sum\limits_{m=0}^n\; \sum\limits_{\substack{\sigma \in S_n\\ |\supp(\sigma)|=m}} \left|n-m \;-\; 1\right|^2\\&\stackrel{(*)}{=} \frac{1}{n!} \sum\limits_{m=0}^n (n-m- 1)^2 {n \choose m} m! \sum\limits_{j=0}^m \frac{(-1)^j}{j!} \\&= \sum\limits_{m=0}^n (n-m- 1)^2\frac{1}{(n-m)!} \sum\limits_{j=0}^m \frac{(-1)^j}{j!} \\&= \sum\limits_{k=0}^n \left( \frac{(k-1)^2}{k!} \sum\limits_{j=0}^{n-k} \frac{(-1)^j}{j!} \right)=1 \end{align}

The equality $(*)$ holds because to choose $\sigma \in S_n$ has a support of cardinality $m$, I choose $m$ numbers out of $n$, and then I have $m!\sum\limits_{j=0}^{m} \frac{(-1)^j}{j!}$ derangements of these $m$ elements.

The following posts are close to my identity, but different: (1), (2). This one only proves $\sum\limits_{k=0}^n \left( \frac{1}{k!} \sum\limits_{j=0}^{n-k} \frac{(-1)^j}{j!} \right)=1$. In all cases, I would like to see some easy proofs of my identity.

We may start from: $$\sum_{k\geq 0} \frac{(k-1)^2}{k!}x^k = (1-x+x^2)\,e^{x}\tag{1}$$ $$\sum_{k\geq 0}\left(\sum_{j=0}^{k}\frac{(-1)^j}{j!}\right) x^k = \frac{e^{-x}}{1-x}\tag{2}$$ then notice that the original sum is just the coefficient of $x^n$ in the product between the RHSs of $(1)$ and $(2)$, i.e.

$$[x^n]\left(\frac{1-x+x^2}{1-x}\right)=[x^n]\left(-x+\color{red}{\frac{1}{1-x}}\right)\tag{3}$$

Now the claim is pretty trivial: the original sum equals $1$ for every $n\in\mathbb{N}$, except for $n=1$ where it equals zero.

• Thank you! Do you have a reference for (2)? – Watson Jun 22 '16 at 16:44
• @Watson: it is just a consequence of a simple lemma. If $$f(x)=\sum_{n\geq 0}a_n x^n,$$ then: $$\sum_{n\geq 0}\left(\sum_{k=0}^{n}a_k\right)x^n = \frac{f(x)}{1-x}.$$ Just multiply both sides of the last equation by $(1-x)$ and rearrange. – Jack D'Aurizio Jun 22 '16 at 16:47
• @Watson You can also establish (2) by interchanging the order of summation, then recognizing a geometric series. – grand_chat Jun 22 '16 at 18:23

Another method is induction.

$f(n):=\sum\limits_{k=0}^n \left( \frac{(k-1)^2}{k!} \sum\limits_{j=0}^{n-k} \frac{(-1)^j}{j!} \right)$

It's easy to calculate $f(n+1)-f(n)=0$ for $n\ge 2$:

$f(0)=1$, $f(1)=0$, $f(2)=1$

$$f(n+1)-f(n)= \sum\limits_{k=0}^{n+1}\frac{(k-1)^2(-1)^{n+1-k}}{k!(n+1-k)!}=\\\sum\limits_{k=2}^{n+1}\frac{k(k-1)(-1)^{n+1-k}}{k!(n+1-k)!} - \sum\limits_{k=1}^{n+1}\frac{k(-1)^{n+1-k}}{k!(n+1-k)!} +\sum\limits_{k=0}^{n+1}\frac{(-1)^{n+1-k}}{k!(n+1-k)!}=\\ \frac{0^{n-1}}{(n-1)!}-\frac{0^n}{n!}+\frac{0^{n+1}}{(n+1)!}=0$$

for $n\ge 2$

• It's fairly easy, but it does require showing that $\sum_{k=0}^{n}{n\choose k}(k-1)^2(-1)^{k} = 0$. Adding how to do this would improve the answer. – Winther Jun 22 '16 at 17:34
• @Winther: It's false to downvote. The result above is only a consequence of the binominal formula which can be provided. – user90369 Jun 22 '16 at 17:42
• I was only providing you with a suggestion on how to improve the answer. I don't control (or care) how people vote here. – Winther Jun 22 '16 at 17:45
• @user90369: thank you for your idea! If you add a bit more detail to your answer, as suggested by Winther, I will upvote your post. – Watson Jun 22 '16 at 18:11
• @Winther: Sorry, I thought wrong. – user90369 Jun 22 '16 at 19:38

$\newcommand{\angles}{\left\langle\,{#1}\,\right\rangle} \newcommand{\braces}{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}{\displaystyle{#1}} \newcommand{\expo}{\,\mathrm{e}^{#1}\,} \newcommand{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}{\overline{#1}} \newcommand{\pars}{\left(\,{#1}\,\right)} \newcommand{\partiald}[]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{k = 0}^{n}\bracks{{\pars{k - 1}^{2} \over k!} \sum_{j = 0}^{n - k}{\pars{-1}^{j} \over j!}} = 1:\,?}$

Lets $\ds{a_{k} \equiv {\pars{k - 1}^{2} \over k!}\,,\ b_{j} \equiv {\pars{-1}^{j} \over j!}\ \mbox{such that}\ \sum_{k = 0}^{n}{\pars{k - 1}^{2} \over k!} \sum_{j = 0}^{n - k}{\pars{-1}^{j} \over j!} = \sum_{k = 0}^{n}a_{k}\sum_{j = 0}^{n - k}b_{j}}$.

Then, we'll compare the sums for upper limits of $\ds{n}$ and $\ds{n + 1}$: \begin{align} \sum_{k = 0}^{n + 1}a_{k}\sum_{j = 0}^{n + 1 - k}b_{j} & = \sum_{k = 0}^{n}a_{k}\sum_{j = 0}^{n + 1 - k}b_{j} + a_{n + 1}\sum_{j = 0}^{0}b_{j} = \sum_{k = 0}^{n}a_{k}\pars{\sum_{j = 0}^{n - k}b_{j} + b_{n + 1 - k}} + a_{n + 1} \\[3mm] & = \sum_{k = 0}^{n}a_{k}\sum_{j = 0}^{n - k}b_{j} + \sum_{k = 0}^{n}a_{k}b_{n + 1 -k} + a_{n + 1} = \sum_{k = 0}^{n}a_{k}\sum_{j = 0}^{n - k}b_{j} + \sum_{k = 0}^{n + 1}a_{k}b_{n + 1 - k} \end{align}
which leads to \begin{equation} \sum_{k = 0}^{n + 1}a_{k}\sum_{j = 0}^{n + 1 - k}b_{j} - \sum_{k = 0}^{n}a_{k}\sum_{j = 0}^{n - k}b_{j} = \sum_{k = 0}^{n + 1}a_{k}b_{n + 1 - k}\tag{1} \end{equation}
In the following step, we'll show that the difference between the sums for the upper limits of $\ds{n + 1}$ and $\ds{n}$ $\pars{~\mbox{the RHS of}\ \pars{1}~}$ vanishes out. Namely, \begin{align} \sum_{k = 0}^{n + 1}a_{k}b_{n + 1 -k} & = \sum_{k = 0}^{n + 1}{\pars{k - 1}^{2} \over k!}\, {\pars{-1}^{n + 1 - k} \over \pars{n + 1 - k}!} = {\pars{-1}^{n} \over \pars{n + 1}!} \sum_{k = 0}^{n +1}{n + 1 \choose k}\pars{k - 1}^{2}\pars{-1}^{k - 1} \\[3mm] & = {\pars{-1}^{n} \over \pars{n + 1}!}\, \lim_{x\ \to\ -1}\pars{x\,\partiald{}{x}}^{2}\ \sum_{k = 0}^{n +1}{n + 1 \choose k}x^{k - 1} \\[3mm] & = {\pars{-1}^{n} \over \pars{n + 1}!}\, \underbrace{% \lim_{x\ \to\ -1}\pars{x\,\partiald{}{x}}^{2} \bracks{\pars{1 + x}^{n + 1} \over x}}_{\ds{=\ 0}} = 0 \end{align}

The RHS $\pars{1}$ vanishes out which show that the sum is independent of $\ds{n}$ and it has the value of $\ds{\ \large\color{#f00}{1}}$.

• Thank you very much Felix! (BTW, I think your last sentence can be removed.) – Watson Jun 22 '16 at 20:12
• @Watson Done ==> Removed. Thanks. – Felix Marin Jun 22 '16 at 20:45
• Why are we supposed to believe that $$\lim_{x\ \to\ -1}\left(x\,\frac{\partial}{\partial x}\right)^{2} \left[\frac{(1 + x)^{n + 1}}{x}\right]=\lim_{x\ \to\ 0}\left(x\,\frac{\partial}{\partial x}\right)^{2} \left[\frac{x^{n + 1}}{1-x}\right]\ ?$$ – Did Jun 22 '16 at 20:57
• @Did You are right. Thanks. I forgot that there are multiplicative prefactors $x$ 's in $x\,{\partial \over \partial x}$ which must be changed. I just removed that line. – Felix Marin Jun 22 '16 at 21:16
• Now, why $$\lim_{x\ \to\ -1}\left(x\,\frac{\partial}{\partial x}\right)^{2} \left[\frac{(1 + x)^{n + 1}}{x}\right]=0\ ?$$ – Did Jun 22 '16 at 21:16