5
$\begingroup$

The identity

$$ \sum_{k=b}^{n} \binom{n}{k} \binom{k}{b} = 2^{n-b} \binom{n}{b}\ $$

is one of a few combinatorial identities I having been trying to prove, and it has taken me way too long. I am using the principles most familiar to me (which are algebra, some basic combinatorial identities, but not applying differentiation or proof by bijection).

First I tried to see whether finding an identity for $\sum\limits_{k=0}^n \binom{n}{k}$ leads anywhere.

$$\begin{align} &\sum_{k=0}^{n} \binom{n}{k} = \sum_{0 \le k \lt b} \binom{n}{k} + \sum_{b \lt k \lt n} \binom{n}{k} \tag{1} \\ \\ \end{align}$$

But it didn't for me, so I started over and next tried

$$\begin{align} &\sum_{k=b}^{n} \binom{n}{k} \binom{k}{b} = \sum_{k=b}^{n} \left( \frac{n!}{k! (n-k)! } \right) \left( \frac{k!}{(k-b)!} \right) \tag{2} \\ \\ \end{align}$$

but this also fell short of a proof.

It is really hard for me to step away from the problem. I was just hoping for a really a big hint on how to proceed.

$\endgroup$

3 Answers 3

6
$\begingroup$

Try thinking of this in terms of what it's counting, instead of algebraically. If we view this as counting committees, we're picking some big committee (of size at least b) of our n employees, and then choosing a subcommittee of that with b employees. However, what if we try picking the b employees first, and then choosing some extra people for the bigger committee?

$\endgroup$
9
  • $\begingroup$ ...I just found what I was looking for on page 4, but still good answer, so +1. $\endgroup$
    – NaN
    Commented Dec 22, 2013 at 22:40
  • $\begingroup$ I still think that committee counting might be the better solution, since it's intuitive and easy to think of: if I were trying to use algebra I'd probably be stuck too. If you haven't figured out the committee-counting solution I'd encourage you to try it out (and ask for more hints if you want). $\endgroup$ Commented Dec 22, 2013 at 23:01
  • $\begingroup$ O.K. yeah the algebra turns out to be a bit lengthy. I only glanced at your solution at first, but will try it now. Please be patient though, as I'm also working (but stuck) on another combinatorial identity proof. $\endgroup$
    – NaN
    Commented Dec 22, 2013 at 23:10
  • $\begingroup$ I'm not entirely sure if I understand which parts you're referring to. Is it clear why the given sum is equivalent to choosing a big committee of size at least b from our n people and then choosing a smaller subcommittee of size exactly b from the big committee? The idea is that the sum cases over all possible sizes k for the big committee. $\endgroup$ Commented Dec 22, 2013 at 23:23
  • $\begingroup$ If that's clear, then what if we try picking the small committee first and then add some extra people for the big committee? How many ways can we choose the small committee from our n employees? How many ways are there to add some number (possibly 0) of extra employees to this small committee? $\endgroup$ Commented Dec 22, 2013 at 23:25
1
$\begingroup$

I'm answering this after many years, but someone might want to see a (mostly) complete algebraic proof.

Begin by expanding the binomial coefficients on the interior of this sum as

$\sum_{k = b}^n \binom{n}{k}\binom{k}{b} = \sum_{k = b}^n \dfrac{n!}{k!(n-b)!} \dfrac{k!}{b!(k-b)!}$

Now pull out everything that doesn't depend on $k$ to get

$\dfrac{n!}{b!} \sum_{k = b}^n \dfrac{1}{(n-k)!(k-b)!}$

Now comes the non-obvious step. Notice that the fraction on the interior is exactly $\binom{n-b}{n-k} \cdot \frac{1}{(n-b)!}$

So, make this substitution then re-index thusly:

$\dfrac{n!}{b!(n-b)!} \sum_{k = b}^n \binom{n-b}{n-k} = \binom{n}{b} \sum_{k = 0}^{n-b} \binom{n-b}{k}$

Finally, apply the binomial theorem to get your result.

$\endgroup$
1
$\begingroup$

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{{\displaystyle #1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\on}[1]{\operatorname{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\sr}[2]{\,\,\,\stackrel{{#1}}{{#2}}\,\,\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} & \color{#44f}{\sum_{k = b}^{n}{n \choose k} {k \choose b}} = \sum_{k = b}^{\infty}{n! \over k!\pars{n - k}!}{k! \over b!\pars{k - b}!} \\[5mm] = & \ \sum_{k = b}^{\infty}{n! \over b!\pars{n - b}!} {\pars{n - b}! \over \pars{n - k}!\pars{k - b}!} = {n \choose b}\sum_{k = b}^{\infty} {n - b \choose k - b} \\[5mm] = & \ {n \choose b}\sum_{k = 0}^{\infty} {n - b \choose k} = \bbx{\color{#44f}{2^{n - b}\,{n \choose b}}} \\ & \end{align}

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .