Exercise 1.4.22* (Conundrum 4/8)

Question

Show that if $m$ and $n$ are integers, $0 \leq m < n$, then
$$\sum_{k=0}^m (-1)^k \binom{n}{k} = (-1)^m \binom{n-1}{m}.$$

Richard Ganaye · Accepted Answer

\begin{proof} Using the Pascal's formula,
\begin{align*}
\sum_{k=0}^m (-1)^k \binom{n}{k}  &= 1 + \sum_{k=1}^m (-1)^k \binom{n}{k}\
&= 1 + \sum_{k=1}^m (-1)^k  \left[ \binom{n-1}{k-1} + \binom{n-1}{k} ight]\
&=1 + \sum_{k=1}^m (-1)^k  \binom{n-1}{k-1} + \sum_{k=1}^m (-1)^k  \binom{n-1}{k}\
&= 1 + \sum_{K = 0}^{m-1} (-1)^{K+1} \binom{n-1}{K} + \sum_{k=1}^m (-1)^k  \binom{n-1}{k}\qquad (K=k-1)\
&= 1 - \sum_{k = 0}^{m-1} (-1)^{k} \binom{n-1}{k} +  \sum_{k=1}^m (-1)^k  \binom{n-1}{k}\
&= - \sum_{k = 1}^{m-1} (-1)^{k} \binom{n-1}{k} + \sum_{k=1}^{m-1} (-1)^k  \binom{n-1}{k} + (-1)^m \binom{n-1}{m}\
&=(-1)^m \binom{n-1}{m}.
\end{align*}
This proves
$$\sum_{k=0}^m (-1)^k \binom{n}{k} = (-1)^m \binom{n-1}{m}.$$
\end{proof}

Exercise 1.4.22* (Conundrum 4/8)

Answers

Comments

Exercise 1.4.22* (Conundrum 4/8)

Answers

Comments

Add answer