Waste less time on Facebook — follow Brilliant.
×

Prove that \(\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+...+n\binom{n}{n}=n2^{n-1}\).

Whilst any proof would be nice, I would prefer a combinatorial proof if possible.\(n2^{n-1}\) is the number of ways of placing \(n-1\) balls (each of which can be red or green) into \(n\) bins such that each bin has a maximum of \(1\) balls inside, and I wonder whether it's possible to directly show that \(\binom{n}{1}+2\binom{n}{2}+3\binom{n}{3}+...+n\binom{n}{n}\) is also that number of ways.

Note by A L
4 years ago

No vote yet
4 votes

Comments

Sort by:

Top Newest

From the binomial theorem, we know that

\[ {n \choose 0} + {n \choose 1}x + {n \choose 2}x^2 + \dots + {n \choose n}x^n = (x+1)^n. \]

If we differentiate both sides with respect to \(x\), we get

\[ {n \choose 1} + 2{n \choose 2}x + 3{n \choose 3}x^2 + \dots + n{n \choose n}x^{n-1} = n(x+1)^{n-1}. \]

Now plug in \(x=1\), and we get

\[ {n \choose 1} + 2{n \choose 2} + 3{n \choose 3} + \dots + n{n \choose n} = n2^{n-1}. \] Tim Vermeulen · 4 years ago

Log in to reply

@Tim Vermeulen I've always felt more at home with calculus, thanks for that neat approach. A L · 4 years ago

Log in to reply

Among \(n\) people, choose a team of any number of people and choose a leader among the chosen ones.

LHS: \(\binom{n}{i}\) indicates how many ways we can choose a team of \(i\) people from \(n\) people. We then choose one leader among these \(i\) people, so we get \(i \binom{n}{i} \). Summing over all \(i\) gives the LHS.

RHS: We choose the leader first; there are \(n\) ways to do this. After we choose the leader, for every remaining person, we choose whether that person goes into the team or not. There are \(2^{n-1}\) ways for this, so multiplying gives the RHS.

This is...err...an intermediate double counting problem. Definitely more advanced than the usual \(\binom{n}{0} + \binom{n}{1} + \ldots + \binom{n}{n} = 2^n\), but still pretty well-known to Olympiad students nevertheless. Ivan Koswara · 4 years ago

Log in to reply

@Ivan Koswara Thanks, but it was only the LHS I was having trouble with. A L · 4 years ago

Log in to reply

@A L The problem with double counting is that if you only get one side working, it's still possible that your approach is completely incorrect.

This is the best continuation of your attempt that I get: Instead of putting only \(n-1\) balls, we put \(n\) balls, at least one of them is green. (Still with each box having at most one ball each.) Fix the number of green balls to be \(i\). Now, after putting them all, pick any of the \(i\) green balls to be removed. This way, we have \(\binom{n}{i}\) ways to put the balls, and \(i\) ways to pick the removed ball, for a total of \(i\binom{n}{i}\) ways. Sum over all \(i\) to get LHS. Ivan Koswara · 4 years ago

Log in to reply

@Ivan Koswara You my have misunderstood me, your method is identical to mine, and I was just saying you could have cut down your answer and saved yourself some time. It's probably my fault for not being clear enough about what I was having trouble with. Thanks again! A L · 4 years ago

Log in to reply

here is probably the shortest one: \(\displaystyle \sum_{i=1}^n i{n \choose i} = \displaystyle \sum_{i=1}^n n{n-1 \choose i-1} = n\displaystyle \sum_{i=1}^n {n-1 \choose i-1} = n2^{n-1} \) Jatin Yadav · 4 years ago

Log in to reply

@Jatin Yadav I quite like this one. A L · 4 years ago

Log in to reply

@Jatin Yadav Well, I'd say you still need to show \(\dbinom{n}{i} = \dfrac{n}{i} \dbinom{n-1}{i-1}\) first (not that obvious even though it's easy), but that doesn't add too much lines. Ivan Koswara · 4 years ago

Log in to reply

@Ivan Koswara \( {n \choose i} = \frac{n!}{i!(n - i)!} = \frac{n}{i}\frac{(n - 1)!}{(i - 1)!(n - i)!} = \frac{n}{i}{n-1 \choose i-1} \) Jatin Yadav · 4 years ago

Log in to reply

In your attempt, are the balls distinguished or undistinguished? Can you explain why you applied the rule of product?

If the balls are indistinguishable, then there are only \(n\) ways to color \(n-1\) indistinguishable balls red or green.
If the balls are distinguished, then how are you accounting for the multiple of \(n\), even with the restriction of only placing 1 ball?

Being clear with what you are counting, can tell you exactly what you are counting. Calvin Lin Staff · 4 years ago

Log in to reply

@Calvin Lin "placing \(n - 1\) balls (each of which can be red or green) into \(n\) bins such that each bin has a maximum of 1 balls inside"

I believe the balls are indistinguishable, but the bins are (so that the answer \(n2^{n-1}\) can appear). The \(n\) most likely appears from \(\binom{n}{n-1}\) on choosing the bins that receive the balls, and the \(2^{n-1}\) most likely appears from \(2\) colors possible for the ball in each filled bin, raised to the \(n-1\)-th power because there are \(n-1\) filled bins. Ivan Koswara · 4 years ago

Log in to reply

@Ivan Koswara Ivan's interpretation is correct. Again, it was my fault for not being clear enough. A L · 4 years ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...