Combinatorial proof that $\sum_{j=0}^k (-1)^j {\binom n j}=(-1)^k \binom{n-1}{k}$ 
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}$$

Reverse the terms in your LHS and multiply by $(-1)^k$ to see that your identity is equivalent to this: $\sum_{j=0}^k (-1)^{j} {\binom n {k-j}}= \binom{n-1}{k}$. The right hand side is the number of $k$-subsets of positive integers less than $n$. That equals the number of $k$-subsets of positive integers less than or equal to $n$ minus the number of $k$-subsets of positive integers less than or equal to $n$ that contain the integer $n$, or $\binom n k - \binom {n-1}{k-1}$. (This is the defining recurrence for binomial coefficients.) Continue with this idea:
$\begin{align*}
\binom{n-1}{k} &= \binom n k - \binom {n-1}{k-1}\\
 &= \binom n k - \left(\binom {n}{k-1}- \binom {n-1}{k-2}\right)\\
 &= \binom n k - \binom {n}{k-1} + \left(\binom {n}{k-2}-\binom {n-1}{k-3}\right)\\
 &= \binom n k - \binom {n}{k-1} + \binom {n}{k-2}-\left(\binom {n}{k-3}-\binom{n-1}{k-4}\right)\\
 &= \cdots\\
 &= \sum_{j=0}^k (-1)^{\,j} {\binom n {k-j}}.
\end{align*}$
