Prove that (n1)+2(n2)+3(n3)+...+n(nn)=n2n1\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.n2n1n2^{n-1} is the number of ways of placing n1n-1 balls (each of which can be red or green) into nn bins such that each bin has a maximum of 11 balls inside, and I wonder whether it's possible to directly show that (n1)+2(n2)+3(n3)+...+n(nn)\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
6 years, 1 month ago

No vote yet
4 votes

  Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

  • Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
  • Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
  • Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
  • Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold

- bulleted
- list

  • bulleted
  • list

1. numbered
2. list

  1. numbered
  2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1

paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
    # 4 spaces, and now they show
    # up as a code block.

    print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.
2 \times 3 2×3 2 \times 3
2^{34} 234 2^{34}
a_{i-1} ai1 a_{i-1}
\frac{2}{3} 23 \frac{2}{3}
\sqrt{2} 2 \sqrt{2}
\sum_{i=1}^3 i=13 \sum_{i=1}^3
\sin \theta sinθ \sin \theta
\boxed{123} 123 \boxed{123}

Comments

Sort by:

Top Newest

Among nn people, choose a team of any number of people and choose a leader among the chosen ones.

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

RHS: We choose the leader first; there are nn 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 2n12^{n-1} ways for this, so multiplying gives the RHS.

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

Ivan Koswara - 6 years, 1 month ago

Log in to reply

Thanks, but it was only the LHS I was having trouble with.

A L - 6 years, 1 month ago

Log in to reply

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 n1n-1 balls, we put nn 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 ii. Now, after putting them all, pick any of the ii green balls to be removed. This way, we have (ni)\binom{n}{i} ways to put the balls, and ii ways to pick the removed ball, for a total of i(ni)i\binom{n}{i} ways. Sum over all ii to get LHS.

Ivan Koswara - 6 years, 1 month 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 - 6 years, 1 month ago

Log in to reply

From the binomial theorem, we know that

(n0)+(n1)x+(n2)x2++(nn)xn=(x+1)n. {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 xx, we get

(n1)+2(n2)x+3(n3)x2++n(nn)xn1=n(x+1)n1. {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=1x=1, and we get

(n1)+2(n2)+3(n3)++n(nn)=n2n1. {n \choose 1} + 2{n \choose 2} + 3{n \choose 3} + \dots + n{n \choose n} = n2^{n-1}.

Tim Vermeulen - 6 years, 1 month ago

Log in to reply

I've always felt more at home with calculus, thanks for that neat approach.

A L - 6 years, 1 month ago

Log in to reply

here is probably the shortest one: i=1ni(ni)=i=1nn(n1i1)=ni=1n(n1i1)=n2n1\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 - 6 years, 1 month ago

Log in to reply

Well, I'd say you still need to show (ni)=ni(n1i1)\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 - 6 years, 1 month ago

Log in to reply

(ni)=n!i!(ni)!=ni(n1)!(i1)!(ni)!=ni(n1i1) {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 - 6 years, 1 month ago

Log in to reply

I quite like this one.

A L - 6 years, 1 month 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 nn ways to color n1n-1 indistinguishable balls red or green.
If the balls are distinguished, then how are you accounting for the multiple of nn, 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 - 6 years, 1 month ago

Log in to reply

"placing n1n - 1 balls (each of which can be red or green) into nn 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 n2n1n2^{n-1} can appear). The nn most likely appears from (nn1)\binom{n}{n-1} on choosing the bins that receive the balls, and the 2n12^{n-1} most likely appears from 22 colors possible for the ball in each filled bin, raised to the n1n-1-th power because there are n1n-1 filled bins.

Ivan Koswara - 6 years, 1 month ago

Log in to reply

Ivan's interpretation is correct. Again, it was my fault for not being clear enough.

A L - 6 years, 1 month ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...