$\sum_{k=0}^n \sum_{l=0}^k \binom{n}{k} \binom{k}{l} (-1)^{k-l} s_l ?= \sum_{l=0}^n \sum_{k=l}^n (-1)^{n-k} \binom{n}{k}\binom{k}{l}s_l $

Question

I want to prove \begin{align} \sum_{k=0}^n \sum_{l=0}^k \binom{n}{k} \binom{k}{l} (-1)^{k-l} s_l ?= \sum_{l=0}^n \sum_{k=l}^n (-1)^{k-l} \binom{n}{k}\binom{k}{l}s_l = s_n \end{align} I can understand the last step using

\begin{align} \sum_{k=l}^{n} (-1)^{k-l} \binom{n}{k}\binom{k}{l} = \delta_{nl} \end{align}

But what about the first step?

Note added :

This problem was due to proving following binomial transformation

\begin{align} s_n = \sum_{k=0}^n \frac{n!}{(n-k)! k!} b^{n-k} c^k a_k \end{align} Its inverse formula is given as \begin{align} a_n = c^{-n} \sum_{k=0}^n \frac{n!}{(n-k)! k!} (-1)^{n-k} b^{n-k} s_k \end{align} What I want to prove is the above is really inverse.

So I start

\begin{align} s_n &= \sum_{k=0}^n \frac{n!}{(n-k)! k!} b^{n-k} c^k a_k = \sum_{k=0}^n \frac{n!}{(n-k)! k!} b^{n-k} c^k \left( c^{-k} \sum_{l=0}^{k} \frac{k!}{(k-l)! l!} (-1)^{k-l} b^{k-l} s_l\right) \\ & = \sum_{k=0}^n \frac{n!}{(n-k)! k!} b^{n-k} \left( \sum_{l=0}^{k} \frac{k!}{(k-l)! l!} (-1)^{k-l} b^{k-l} s_l\right) \end{align}

and to do right computation, I guess some identity and that's what i want to know.

Did you mean $(-1)^{k-l}$ instead of $(-1)^{n-k}$ in the middle term? — Stefan Lafon, Jul 27 '19 at 01:55
Permute the sums and note that the missing terms are all zero, $\binom{k}{l}=0$ for $l<k$. — AccidentalFourierTransform, Jul 27 '19 at 02:20

score 1 · Accepted Answer · answered Jul 27 '19 at 03:17

Basic double sum transformation:

$\sum_{k=0}^n \sum_{l=0}^k t(k, l) =\sum_{l=0}^n \sum_{k=l}^n t(k, l) $.

This is all $k$ and $l$ with $0 \le l \le k \le n$.

We also need $\sum_{k=0}^{n} (-1)^{k} \binom{n}{k} =0$ if $n > 0$ and $=1$ if $n = 0$.

This is the expansion of $(1-1)^n$ by the binomial theorem.

The second one:

$\begin{array}\\ \sum_{l=0}^n \sum_{k=l}^n (-1)^{k-l} \binom{n}{k}\binom{k}{l}s_l &=\sum_{l=0}^n s_l\sum_{k=l}^n (-1)^{k-l} \dfrac{n!k!}{k!(n-k)!l!(k-l)!}\\ &=\sum_{l=0}^n s_l\dfrac{n!}{l!}\sum_{k=l}^n (-1)^{k-l} \dfrac{1}{(n-k)!(k-l)!}\\ &=\sum_{l=0}^n s_l\dfrac{n!}{l!(n-l)!}\sum_{k=l}^n (-1)^{k-l} \dfrac{(n-l)!}{(n-k)!(k-l)!}\\ &=\sum_{l=0}^n s_l\binom{n}{l}\sum_{k=l}^n (-1)^{k-l} \binom{n-l}{k-l}\\ &=\sum_{l=0}^n s_l\binom{n}{l}\sum_{k=0}^{n-l} (-1)^{k} \binom{n-l}{k}\\ &= s_n\\ \end{array} $

The first one:

$\begin{array}\\ \sum_{k=0}^n \sum_{l=0}^k \binom{n}{k} \binom{k}{l} (-1)^{k-l} s_l &=\sum_{l=0}^n \sum_{k=l}^n \binom{n}{k} \binom{k}{l} (-1)^{k-l} s_l \end{array}\\ $

and this is the second one.

$\sum_{k=0}^n \sum_{l=0}^k \binom{n}{k} \binom{k}{l} (-1)^{k-l} s_l ?= \sum_{l=0}^n \sum_{k=l}^n (-1)^{n-k} \binom{n}{k}\binom{k}{l}s_l $

1 Answers1

Linked