3
$\begingroup$

Let $n$ and $k$ be integers with $1 \leq k \leq n$. Use proof by double counting to show that $$\sum_{k=0}^{n}\binom{n}{k}\binom{n}{k -1} = \binom{2n}{n+1}.$$

I have this so far:

Suppose we want to form a committee. We can choose members from a group of $n$ math professors and $n$ computer science professors, and we must have one more math professor than computer science professors. The committee can be of any size, as long as there is one more math professor than there are computer science professors.

Let $k$ be the number of math professors we choose for the committee. There are $\binom{n}{k}$ ways to choose them. Because we must have one more math professor than computer science professors let $k-1$ be the number of computer science professors. There are $\binom{n}{k-1}$ ways to choose them. This gives us $\binom{n}{k}\binom{n}{k-1}$ by the product rule and we sum over all choices of $k$.

I get stuck when I try to prove the right side.

$\endgroup$
  • 1
    $\begingroup$ think of $\binom{n}{k-1}$ as $\binom{n}{n-k+1}$ instead. $\endgroup$ – cats Dec 7 '16 at 5:56
  • $\begingroup$ Please see my comment to the excellent answer by Robert Z. $\endgroup$ – Andreas Caranti Dec 7 '16 at 7:03
1
$\begingroup$

Note that by symmetry $\binom{n}{k -1}=\binom{n}{n-(k -1)}=\binom{n}{n+1-k}$ (see also cat's comment).

Hence we have to show that $$\sum_{k=0}^{n}\binom{n}{k}\binom{n}{n+1-k} = \binom{2n}{n+1}.$$ Consider a set of $2n$ guys: $n$ boys and $n$ girls. In the RHS we enumerate the subsets of $n+1$ people taken from the above set. In the LHS we enumerate the same subsets as union of $k$ boys and $(n+1-k)$ girls, with $0\leq k\leq n$.

$\endgroup$
  • 1
    $\begingroup$ From the OP point of view, what is being done is to reformulate the combinatorial problem as follows. On the left hand side, for each $k$ you choose the $k$ maths professors in the committee, and then you choose the $n - (k-1)$ CS professors who do not sit in the committee. This explain the right hand side: you are choosing $k + (n - (k-1)) = n + 1$ people out of $2 n$. (Aside: unfortunately the problem is far from realistic - I always get outnumbered by my CS colleagues.) $\endgroup$ – Andreas Caranti Dec 7 '16 at 7:02
1
$\begingroup$

The left hand side is the coefficient of $t$ in $$(1+t)^n \left(1+\frac{1}{t}\right)^n$$ and hence the coefficient of $t$ in $$\frac{(1+t)^{2n}}{t^n}$$ This is clearly $\binom{2n}{n+1}$

$\endgroup$

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.