Binomial/combinatorics summation proof question

108 Views Asked by At

Given $\sum_{k=0}^{2r} (-1)^k \binom{n}{k}\binom{n}{2r-k} = (-1)^r\binom{n}{r}$ for $0≤r≤\frac12n$

How do I show that $\sum_{k=0}^{r} (-1)^k \binom{n}{k}\binom{n}{2r-k} = \frac12(-1)^r\binom{n}{r}[1+\binom{n}{r}]$ for $0≤r≤\frac12n$

For context, the first statement is derived from considering the coefficient of $x^{2r}$ in the statement $(1-x)^n(1+x)^n=(1-x^2)^n$ where $2r≤n$

1

There are 1 best solutions below

6
On BEST ANSWER

Use symmetry: we split the sum into two parts and then we change the index in the second one by letting $j=2r-k$, $$\begin{align} \sum_{k=0}^{2r} (-1)^k \binom{n}{k}&\binom{n}{2r-k}=\sum_{k=0}^{r} (-1)^k \binom{n}{k}\binom{n}{2r-k}+\sum_{k=r+1}^{2r} (-1)^k \binom{n}{k}\binom{n}{2r-k}\\ &=\sum_{k=0}^{r} (-1)^k \binom{n}{k}\binom{n}{2r-k}+\sum_{j=0}^{r-1} (-1)^{2r-j} \binom{n}{2r-j}\binom{n}{j}\\ &=\sum_{k=0}^{r} (-1)^k \binom{n}{k}\binom{n}{2r-k}+\sum_{j=0}^{r} (-1)^{j} \binom{n}{2r-j}\binom{n}{j}- (-1)^{r}\binom{n}{r}^2\\ &=2\sum_{k=0}^{r} (-1)^k \binom{n}{k}\binom{n}{2r-k}- (-1)^{r}\binom{n}{r}^2. \end{align}$$