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

Question

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.

Thank you for your comments!

Answer 1

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.

Answer 2

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$

Answer 3

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