Proving $\sum \limits_{i=0}^k {n \choose i}(-1)^i = {n-1 \choose k}(-1)^k$

Question

What proof could I use to prove the following identity? I somehow know that Pascal's identity must be used but I need some help. Could anyone show me how to solve this? maybe by induction or combinatorial proof, it would be awesome to have both: $\sum \limits_{i=0}^k {n \choose i}(-1)^i = {n-1 \choose k}(-1)^k$

Answer 1

Let $P(k)$ be the statement $$\sum_{i = 0}^{k} \binom{n}{i}(-1)^i = \binom{n - 1}{k}(-1)^k$$

Let $k = 0$. Then $$\sum_{i = 0}^{0} \binom{n}{i}(-1)^i = \binom{n}{0}(-1)^0 = 1 \cdot 1 = \binom{n - 1}{0}(-1)^0$$ Thus, $P(0)$ holds.

Since $P(0)$ holds, we may assume $P(m)$ holds for some nonnegative integer $m$. Then $$\sum_{i = 0}^{m} \binom{n}{i}(-1)^i = \binom{n - 1}{m}(-1)^m$$ Let $k = m + 1$.
\begin{align*} \sum_{i = 0}^{m + 1} \binom{n}{i}(-1)^k & = \sum_{i = 0}^{m + 1} \binom{n}{i}(-1)^k + \binom{n}{m + 1}(-1)^{m + 1}\\ & = \binom{n - 1}{m}(-1)^m + \binom{n}{m + 1}(-1)^{m + 1} && \text{induction hypothesis}\\ & = -\binom{n - 1}{m}(-1)^{m + 1} + \binom{n}{m + 1}(-1)^{m + 1}\\ & = \left[-\binom{n - 1}{m} + \binom{n}{m + 1}\right](-1)^{m + 1}\\ & = \binom{n - 1}{m + 1}(-1)^{m + 1} \end{align*} where we have used Pascal's Identity $$\binom{n - 1}{k} + \binom{n - 1}{k - 1} = \binom{n}{k}$$ with $k = m + 1$ in the final step. Therefore, $P(m) \implies P(m + 1)$.

Since $P(0)$ holds and $P(m) \implies P(m + 1)$, $P(k)$ holds for each nonnegative integer $k$.

Note that the claim does hold for $k > n - 1$. If $k > n - 1$, the right hand side vanishes. The only nonzero terms on the left hand side are those for which $k \leq n$. If $k = n$, then $$\sum_{i = 0}^{n} \binom{n}{i}(-1)^i = \sum_{i = 0}^n \binom{n}{i}1^{n - i}(-1)^i = [1 + (-1)]^n = 0^n = 0$$ by the Binomial Theorem.