# Give a combinatorial argument

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!

• The definition of $C$ is usually a great starting point. – Jonny Nov 10 '14 at 21:20
• Edited for clarification. – sanic Nov 10 '14 at 21:22
• A combinatorial argument means to count the same set of things two different ways. – Matthew Leingang Nov 11 '14 at 1:02

Hint

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

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$.

$$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.

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?

• as m changes, the number multiplying the combinations changes. That I see. I dont understand how the right hand side is formulated from that? Why do you focus on C(n, n - m)? – sanic Nov 10 '14 at 21:31
• I focus on $C(n, n-m)$ because you have a sum where, for a lot of $m$'s (about half), you have $(m\cdot C(n,m)) + ((n-m)\cdot C(n, n-m))$ by rearranging the order of additions. – nomen Nov 10 '14 at 21:45