Apply the principle of mathematical induction or its variants to show that for all positive integers $m$ and $n$ such that $0\le m<n$:

Question

As the title says

Apply the principle of mathematical induction or its variants to show that for all positive integers $m$ and $n$ such that $0\le m < n$,

$$\sum_{k=0}^m(-1)^k\binom{n}k=(-1)^m\binom{n-1}m\,.$$

Not sure, I tried using traditional combinational proofs, but I'm a little lost on where to go.

Answer 1

Do the induction on $n$. For your induction hypothesis suppose that

$$\sum_{k=0}^m(-1)^k\binom{n}k=(-1)^m\binom{n-1}m$$

for all $m$ such that $0\le m<n$; then you want to show that

$$\sum_{k=0}^m(-1)^k\binom{n+1}k=(-1)^m\binom{n}m$$

whenever $0\le m<n+1$. For $0\le m<n$ you can follow the usual pattern for such proofs, starting with this:

$$\begin{align*} \sum_{k=0}^m(-1)^k\binom{n+1}k&=\sum_{k=0}^m(-1)^k\left(\binom{n}k+\binom{n}{k-1}\right)\\ &=\sum_{k=0}^m(-1)^k\binom{n}k+\sum_{k=0}^m(-1)^k\binom{n}{k-1}\\ &=(-1)^m\binom{n-1}m+\sum_{k=1}^m(-1)^k\binom{n}{k-1}\\ &=(-1)^m\binom{n-1}m+\sum_{k=0}^{m-1}(-1)^{k+1}\binom{n}k\\ &=(-1)^m\binom{n-1}m-\sum_{k=0}^{m-1}(-1)^k\binom{n}k\,; \end{align*}$$

see if you can finish it from there.

The remaining case, $m=n$, has to be handled separately; for now I’ll leave that to you, merely noting that it follows from an application of the binomial theorem.