Finishing proof of identity $\sum_{k=b}^{n} \binom{n}{k} \binom{k}{b} = 2^{n-b} \binom{n}{b}$

Question

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.

Answer 1

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?

Answer 2

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.

Answer 3

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