Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

3 Answers 3

up vote 2 down vote accepted

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.

share|improve this answer

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

share|improve this answer

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

share|improve this answer
    
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 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 at 6:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.