Permutations and Combinations Show that $\binom{n}{0} - \binom{n}{1} + \binom{n}{2} - ...+(-1)^k * \binom{n}{k} = (-1)^k * \binom{n-1}{k}$.
I know this has to do with permutations and combination problems, but I'm not sure how would I start with this problem. 
 A: We have the identity $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$. So we see the series telescope:
$$\sum_{i=0}^{k} (-1)^{i} \binom{n}{i} = \binom{n}{0} + \sum_{i=1}^{k} \binom{n-1}{i-1} + \sum_{i=0}^{k} \binom{n-1}{i}$$ 
So we see $\binom{n}{0} = 1$. Then $\binom{n}{1} = \binom{n-1}{0} + \binom{n-1}{1}$. For any $x$, $\binom{x}{0} = 1$. So $\binom{n}{0} - \binom{n-1}{0} = 0$.
Now look at $\binom{n}{2} = \binom{n-1}{1} + \binom{n-2}{2}$. By telescoping, $-\binom{n-1}{1} + \binom{n-1}{1} = 0$.
So we are left with the term $\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$, with the $\binom{n-1}{k-1}$ cancelling out out the $\binom{n-1}{k-1}$ term from $\binom{n}{k-1}$. Then we are left with $\binom{n-1}{k}$. 
A: I assume that $n \geq 1$ and $K \geq 0$. We need to prove that
$\sum_{k=0}^{K}(-1)^k\binom{n}{k}=(-1)^K\cdot\binom{n-1}{K}$
I like proofs by induction. So we fix some $n \geq 1$ and our base case is $K = 0$. In this case we have (recall that for any $~n~$ $\binom{n}{0} = 1$):
$LHS: ~~ \sum_{k=0}^{0}(-1)^k\binom{n}{k} = (-1)^0\binom{n}{0} = 1\cdot 1=1$
$RHS: ~~ (-1)^0\cdot \binom{n-1}{0} = 1\cdot1=1$
Now we assume that the formula is correct for some $K \geq 0$ and show that then it's correct for $K+1$ (notice that for any $~x~$ and any $~k~$  $~(-1)^{k+1}x=-(-1)^kx~$ thus$~(-1)^kx + (-1)^{k+1}x = 0$):
$\sum_{k=0}^{K+1}(-1)^k\binom{n}{k} = \sum_{k=0}^{K}(-1)^k\binom{n}{k} + (-1)^{K+1}\binom{n}{K+1}=(-1)^K\cdot\binom{n-1}{K}+(-1)^{K+1}\binom{n}{K+1}=(-1)^K\cdot\binom{n-1}{K} + (-1)^{K+1}\binom{n-1}{K} + (-1)^{K+1}\binom{n-1}{K+1} = (-1)^{K+1}\binom{n-1}{K+1}$
