Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There are plenty of questions regarding combinatorial proofs up, but I'm not understanding them very well.

Basic understanding: Count something on the RHS (show WHAT it is counting), and show that it's counting the same thing on the LHS.

My problem is:

$$\sum_{k=0}^{n}\binom{n}{k}kx^{k-1}y^{n-k} = n(x+y)^{n-1}$$

So, I started out with:

$$n(x+y)^{n-1} = n[(x+y)(x+y)...(x+y)]$$

But I'm not sure if this even helps me, and I'm not even sure if my basic understanding is correct. Could someone give me some direction? This is homework, so don't provide a direct answer to the problem, please.

EDIT: We can assume x and y are positive integers.

share|cite|improve this question
Your basic understanding of what is meant by a combinatorial proof is correct. That doesn’t seem a particularly natural way to prove this identity, though, especially if nothing is assumed about $x$ and $y$. – Brian M. Scott Jan 27 '13 at 23:54
Check my edit. We can assume x and y are positive integers. – intervade Jan 27 '13 at 23:56
up vote 2 down vote accepted

Hint: For a counting argument, suppose $\mathcal{X}$ is a set of $x$ different elements, and $\mathcal{Y}$ is a set of $y$ elements. You want to show that (I moved the $n$ to the left)

$$\sum_{k=0}^{n}\binom{n}{k}\frac{k}{n}x^{k-1}y^{n-k} = (x+y)^{n-1}.$$

The term on the right counts in how many ways you can select $n - 1$ items from $\mathcal{X} \cup \mathcal{Y}$ with replacement (why?). Can you show (with the help of Adi's hint) that the left hand side is also counting this quantity?

share|cite|improve this answer

HINT $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}\Rightarrow k\binom{n}{k}=n\binom{n-1}{k-1}$$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.