6
$\begingroup$

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!

$\endgroup$
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you! Do you have a reference for (2)? $\endgroup$ – Watson Jun 22 '16 at 16:44
  • 1
    $\begingroup$ @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. $\endgroup$ – Jack D'Aurizio Jun 22 '16 at 16:47
  • 1
    $\begingroup$ @Watson You can also establish (2) by interchanging the order of summation, then recognizing a geometric series. $\endgroup$ – grand_chat Jun 22 '16 at 18:23
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Winther Jun 22 '16 at 17:34
  • $\begingroup$ @Winther: It's false to downvote. The result above is only a consequence of the binominal formula which can be provided. $\endgroup$ – user90369 Jun 22 '16 at 17:42
  • 1
    $\begingroup$ I was only providing you with a suggestion on how to improve the answer. I don't control (or care) how people vote here. $\endgroup$ – Winther Jun 22 '16 at 17:45
  • $\begingroup$ @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. $\endgroup$ – Watson Jun 22 '16 at 18:11
  • $\begingroup$ @Winther: Sorry, I thought wrong. $\endgroup$ – user90369 Jun 22 '16 at 19:38
0
$\begingroup$

$\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}}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you very much Felix! (BTW, I think your last sentence can be removed.) $\endgroup$ – Watson Jun 22 '16 at 20:12
  • $\begingroup$ @Watson Done ==> Removed. Thanks. $\endgroup$ – Felix Marin Jun 22 '16 at 20:45
  • $\begingroup$ 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]\ ?$$ $\endgroup$ – Did Jun 22 '16 at 20:57
  • $\begingroup$ @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. $\endgroup$ – Felix Marin Jun 22 '16 at 21:16
  • $\begingroup$ Now, why $$\lim_{x\ \to\ -1}\left(x\,\frac{\partial}{\partial x}\right)^{2} \left[\frac{(1 + x)^{n + 1}}{x}\right]=0\ ?$$ $\endgroup$ – Did Jun 22 '16 at 21:16

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.