Sum with binomial coefficient

Question

How can I prove that

$$\sum_{y=1}^{k \choose s} (-1)^{y+1} \sum_{r=0}^{k} (-1)^{r} {k \choose r} {{k-r \choose s} \choose y} = (-1)^{k-s} {{k-1} \choose s-1} ?$$

I know this is correct from simulations.

Answer 1

We will use the fact that for any $0\le s \le n$, the truncated alternating sum of binomial coefficients is known: $$\sum_{k=0}^{s} (-1)^{k} \binom{n}{k} = (-1)^{s} \binom{n-1}{s}$$ This follows easily by backwards induction on $s$: for $s = n$ it is just the binomial theorem $(1 - 1)^{n} = 0$, and given the identity for $s$, we have that $$\sum_{k=0}^{s-1} (-1)^{k} \binom{n}{k} = (-1)^{s} \left( \binom{n-1}{s} - \binom{n}{s} \right) = (-1)^{s-1} \binom{n-1}{s-1}$$ using Pascal's identity $ \binom{n}{s} = \binom{n-1}{s} + \binom{n-1}{s-1}$. To conclude, deduce from this identity that $$\sum_{y=1}^{\binom{k}{s}} (-1)^{y+1} \binom{\binom{k-r}{s}}{y} = \begin{cases} 1 & k-r \ge s \\ 0 & \text{else} \end{cases}$$ since the binomial coefficients in the sum are nonnull precisely when $k-r \ge s$, and $\binom{k-r}{s} \le \binom{k}{s}$ always. Accordingly, the desired sum is $$\sum_{r=0}^{k-s} (-1)^{r} \binom{k}{r} = (-1)^{k-s} \binom{k-1}{k-s} = (-1)^{k-s} \binom{k-1}{s-1}$$