0
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Emolga Feb 1 '14 at 18:51
  • $\begingroup$ 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. $\endgroup$ – Steve Kass Feb 2 '14 at 6:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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