Give a combinatorial argument

Question

Give a combinatorial argument to show that $$\binom{6}{1} + 2 \binom{6}{2} + 3\binom{6}{3} + 4 \binom{6}{4} + 5 \binom{6}{5} + 6 \binom{6}{6} = 6\cdot2^5$$

Not quite where to starting proving this one. Thanks!

Answer 1

Hint

From $6$ candidate, how many ways do we have to form a team and pick a team leader?

Answer 2

Hint: $C(n,m)$ counts the number of $m$ element subsets of a set with $n$ elements. What are you changing as you change $m$? How does $C(n,m)$ relate to $C(n,n-m)$? How does that let you simplify your sum?

Answer 3

For whatever it's worth, here's a standard probabilistic argument: The number of ways to get $k$ heads in six trials when tossing a coin is $\dbinom 6 k$. If all $2^6=64$ sequences are equally likely (as they are when the coin is "fair", i.e. gives heads and tails equally often) then the probability of exactly $k$ successes in $6$ trials is $\dbinom 6 k \cdot \dfrac 1 {64}$. So the average number of successes in $6$ trials is $$ \frac{\binom{6}{1} + 2 \binom{6}{2} + 3\binom{6}{3} + 4 \binom{6}{4} + 5 \binom{6}{5} + 6 \binom{6}{6}}{64}. $$

But the average number of successes in $6$ trials, with probability $1/2$ of success on each trial, is $6\cdot\frac 1 2=3$, so the sum above equals $3$.

On way of showing that the average number of successes with six trials is three is to observe that the average number of successes in one trial is $1/2$, so you're just adding up $1/2$ six times, getting $3$.

Answer 4

$$2^5$$ is just a way to count the elements in a 5 member set. (For each member of the set you make a binary decision to include it or not)

Now let's say you have a six element set.

Let's look at $$ \binom{6}{1} $$ Fix any member of the 6 element set. Now you have 5 members left. So that is $$ \binom{5}{1} $$ But you could have choosen that fixed member in 6 ways. So that is effectively $$ 6\cdot\binom{5}{1} $$ Repeat the same argument for each binomial and we get:

$$ 6(\binom{5}{1} + \binom{5}{2} +\binom{5}{3} + \binom{5}{4} + \binom{5}{5} + \binom{5}{6}) $$

But what is inside the parenthesis is simply another way of counting the sub-sets of a set of 5 elements.