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}$$
 A: 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.
A: $\newcommand{\+}{^{\dagger}}%
 \newcommand{\angles}[1]{\left\langle #1 \right\rangle}%
 \newcommand{\braces}[1]{\left\lbrace #1 \right\rbrace}%
 \newcommand{\bracks}[1]{\left\lbrack #1 \right\rbrack}%
 \newcommand{\ceil}[1]{\,\left\lceil #1 \right\rceil\,}%
 \newcommand{\dd}{{\rm d}}%
 \newcommand{\down}{\downarrow}%
 \newcommand{\ds}[1]{\displaystyle{#1}}%
 \newcommand{\equalby}[1]{{#1 \atop {= \atop \vphantom{\huge A}}}}%
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}%
 \newcommand{\fermi}{\,{\rm f}}%
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}%
 \newcommand{\half}{{1 \over 2}}%
 \newcommand{\ic}{{\rm i}}%
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}%
 \newcommand{\isdiv}{\,\left.\right\vert\,}%
 \newcommand{\ket}[1]{\left\vert #1\right\rangle}%
 \newcommand{\ol}[1]{\overline{#1}}%
 \newcommand{\pars}[1]{\left( #1 \right)}%
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}%
 \newcommand{\root}[2][]{\,\sqrt[#1]{\,#2\,}\,}%
 \newcommand{\sech}{\,{\rm sech}}%
 \newcommand{\sgn}{\,{\rm sgn}}%
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\ul}[1]{\underline{#1}}%
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{\sum_{j=0}^{k}\pars{-1}^{j}{n \choose j} = \pars{-1}^{k}{n - 1 \choose k}:\ {\large ?}}$

\begin{align}
\color{#00f}{\large\sum_{j=0}^{k}\pars{-1}^{j}{n \choose j}} &=
\sum_{j=0}^{k}\pars{-1}^{j}\
\overbrace{\int_{\verts{z}\ =\ 1}{\pars{1 + z}^{n} \over z^{j + 1}}\,
{\dd z \over 2\pi\ic}}^{\ds{=\ {n \choose j}}}
=
\int_{\verts{z}\ =\ 1}{\dd z \over 2\pi\ic}\,\pars{1 + z}^{n}
\bracks{{1 \over z}\sum_{j=0}^{k}{\pars{-1}^{j} \over z^{j}}}\,
\\[3mm]&=
\int_{\verts{z}\ =\ 1}{\dd z \over 2\pi\ic}\,\pars{1 + z}^{n}\,
\bracks{{1 \over z}\,{\pars{-1/z}^{k + 1} - 1 \over -1/z - 1}}
\\[3mm]&=
\pars{-1}^{k}\int_{\verts{z}\ =\ 1}{\dd z \over 2\pi\ic}\,
{\pars{1 + z}^{n - 1} \over z^{k + 1}}
+\
\overbrace{\int_{\verts{z}\ =\ 1}{\dd z \over 2\pi\ic}\,\pars{1 + z}^{n - 1}}
^{\ds{=\ 0}}
\\[3mm]&=
\pars{-1}^{k}\int_{\verts{z}\ =\ 1}{\dd z \over 2\pi\ic}\,
\sum_{\ell = 0}^{n - 1}{n - 1 \choose \ell}{1 \over z^{\pars{k - \ell} + 1}}
\\[3mm]&=
\pars{-1}^{k}\sum_{\ell = 0}^{n - 1}{n - 1 \choose \ell}
\overbrace{%
\int_{\verts{z}\ =\ 1}{\dd z \over 2\pi\ic}\,{1 \over z^{\pars{k - \ell} + 1}}}
^{\ds{=\ \delta_{\ell,k}}}
=
\color{#00f}{\large\pars{-1}^{k}{n - 1 \choose k}}
\end{align}

A: 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*}$
