# combinatorial proof, still don't understand

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.

• 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

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?
HINT $$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}\Rightarrow k\binom{n}{k}=n\binom{n-1}{k-1}$$