Exercise 1.18

Question

Give a story proof that
$$\sum_{k=1}^{n} k{n \choose k}^2 = n{2n-1 \choose n-1}$$
for all positive integers $n$.

fifthist x · Accepted Answer

Consider the right hand side of the equation. Since a committe chair can only 
be selected from the first group, there are $n$ ways to choose them. Then, for 
each choice of a committee chair, there are ${2n-1 \choose n-1}$ ways to choose 
the remaining members. Hence, the total number of committees is $n{2n-1 \choose n-1}$.

Now consider the left side of the equation. Suppose we pick $k$ people from the 
first group and $n-k$ people from the second group, then there are $k$ ways to 
assign a chair from the members of the first group we have picked. $k$ can range 
from $1$ to $n$ giving us a total of 
$\sum_{k=1}^{n} k{n \choose k}{n \choose n-k} = \sum_{k=1}^{n} k{n \choose k}^{2}$ 
possible committees.

Since, both sides of the equation count the same thing, they are equal.

Exercise 1.18

Answers

Comments

Exercise 1.18

Answers

Comments

Add answer