# 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}$$

-

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.

-

$\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}

-

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*}

-
That is the inductive proof that I was referring to... I'm hoping for a counting argument, and also feel that the 'snake oil' method I tried can be completed. Are you saying it can't be done? – Leullame Feb 1 '14 at 18:51
The counting argument is to repeat the argument I gave for step 1. The number of $k$-subsets of $\{1\dots n-1\}$ is the number of $k$-subsets of $\{1\dots n\}$ minus the number of $k$-subsets of $\{1\dots n\}$ that contain the integer $n$. The latter value is the number of $(k-1)$-subsets of $\{1\dots n-1\}$, which equals the number of $(k-1)$-subsets of $\{1\dots n\}$ minus the number of $(k-1)$-subsets of $\{1\dots n-1\}$ that contain the integer $n-1$, the latter number being... It’s recursive, but purely combinatorical in that it just counts sets. Amit gave the same solution. – Steve Kass Feb 2 '14 at 6:50