So, I'm required to show that
$$\sum_{k=0}^m (-1)^k{n\choose{k}} = (-1)^m {{n-1}\choose{m}}$$ holds for all $0 \leq m < n$
Of course, my base case starts with $n = 1$, so my value of $m$ must be $0$. It is then easy to see that the RHS of the identity for these values of $m$ and $n$ equals $1$, and the sum $$\sum_{k=0}^0(-1)^k {0\choose k}$$
evaluates to $1$. So, the LHS and RHS agree for the base case. We assume the statement holds for some $n \geq 1$, but proving the inductive step is where I am stuck at. In other words, I want to show that
$$\sum_{k=0}^m (-1)^k{{n+1}\choose{k}} = (-1)^m {{n}\choose{m}}$$
holds for all $0 \leq m < n+1$. Any help would be greatly appreciated.
Best Answer
It's trivial if $m=0$. We can induct on $m$, provided we use the convention $\binom{a}{b}=0$ if $a<b$. If the desired result holds when $m=j$, increasing $m$ to $j+1$ adds $(-1)^{j+1}\binom{n}{j+1}$ to the left-hand side and $(-1)^{j+1}\binom{n-1}{j+1}-(-1)^j\binom{n-1}{j}=(-1)^{j+1}\binom{n}{j+1}$ to the other.