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

binomial-coefficients

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.

Best Answer

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.

Related Question