Prove $\sum_{j=0}^k (-1)^j {\binom n j}=(-1)^k \binom{n-1}{k}$.
It can be proven easily using induction and Pascal's identity, but I want some insight. The alternating sum reminds of inclusion-exclusion, but the RHS can be negative.
I've also tried the snake oil method, but don't know how to finish it:
$$\sum_n (\sum_{j=0}^k (-1)^j {\binom n j})x^n= \sum_{j=0}^k (-1)^j \sum_n {\binom n j}x^n$$
$$=\sum_{j=0}^k (-1)^j \frac{x^j}{(1-x)^{j+1}}=\frac{1}{1-x} \sum_{j=0}^k (\frac{-x}{1-x})^j=1-(\frac{-x}{1-x})^{k+1}$$
Best Answer
When $k$ is even, then the RHS counts the number of ways to choose $k$ things from the set $\{1, \dots, n-1\}$.
Another way to count that is to count the number of ways to choose $k$ things from the set $\{1, \dots, n\}$, except this number is too big, since it includes $k$-sized subsets that have the number $n$ in them. You want to subtract this from your count, so you would subtract the number of $k$-sized subsets of $\{1,\dots,n\}$ that include the number $n$.
How do you get a $k$-sized subset of $\{1,\dots,n\}$ that has $n$ in it? You pick $n$, then you pick $j$ numbers from $\{1,\dots,n-1\}$ where $j = k-1$. So you could count the number of ways to do this by counting the number of $j$-sized subsets of $\{1,\dots,n-1\}$. Or you could do what we did above: count the $j$-sized subsets of $\{1,\dots,n\}$ and then realize you've over-counted because you're including some sets that have $n$ in them.
Continuing this process, you get:
$${n-1\choose k} = {n\choose k} - \left[{n\choose k-1} -\left[{n\choose k-2} - \left[{n\choose k-3} - \dots\right]\right]\right]$$
When $k$ is odd, just switch the signs, i.e. prove that -LHS = -RHS.