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.


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?

| cite | improve this answer | |
  • $\begingroup$ ...I just found what I was looking for on page 4, but still good answer, so +1. $\endgroup$ – NaN Dec 22 '13 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$ – GaussianInteger Dec 22 '13 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 Dec 22 '13 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$ – GaussianInteger Dec 22 '13 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$ – GaussianInteger Dec 22 '13 at 23:25

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.