Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.
  • Does exist a combinatorial proof for the following two identities ?

    • $\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$

    • $\sum_{k = 0}^{n} k\binom{n}{k} = n2^{n-1}$

I know how to derive the identites from $(1+x)^n$ , but I am searching for a combinatorial proof ?

share|improve this question

marked as duplicate by tetori, Johannes Kloos, Dennis Gulko, Matthew Pressland, Math_overview Nov 17 '13 at 11:03

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

For what it's worth, there are several proofs of the second identity here: How to prove this binomial identity $\sum_{r=0}^n {r {n \choose r}} = n2^{n-1}$? –  Mike Spivey Sep 23 '11 at 22:47
My solution is identical to acarchau's answer. –  Srivatsan Sep 23 '11 at 22:52

3 Answers 3

up vote 8 down vote accepted

The second identity counts the number of nonempty sets with a distinguished representative; that is, all pairs $(x,S)$ such that $S \subseteq [n]$ with $x \in S$.

  1. You can pick a set consisting of $k$ elements (in $\binom n k$ ways) and pick the representative in $k$ ways for each choice of the set.
  2. You can pick the representative $x \in [n]$ first, and then choose the other members of the set in $2^{n-1}$ ways.

Equating these two counts, we are done.

share|improve this answer

For the first identity:

$\sum_{k = 0}^{n} \binom{x+k}{k} = \binom{x+n+1}{n}$

The left-hand side is the number of sequences of blue and yellow balls you can make such that there are exactly $x$ blue balls and at most $n$ yellow balls.

The right-hand side creates the same sequences by enumerating all sequences with $x+1$ blue balls and $n$ yellow balls, and then always removing the rightmost blue ball and all yellow balls to the right of it.

share|improve this answer
Nice. Actually, this same identity came up implicitly in a recent post: math.stackexchange.com/questions/65947/… . (Well, I got the right hand side as the answer, and Thijs' answer gets the left hand side sum; so the two sides must match. :-)) –  Srivatsan Sep 23 '11 at 22:55
And I used it here a few days earlier, but couldn't think of anything but an appeal to Pascal's triangle then. –  Henning Makholm Sep 23 '11 at 22:59

You are choosing $n$ people from $x+n+1$ people who are lined up in a row. The right side counts the number of choices.

The left side counts the choices in another way. For any $k$ from $0$ to $n$, select all of the first $n-k$ people (from the left), then not the next one, then choose $k$ people from the remaining $x+n+1-(n-k+1)$, that is from the remaining $x+k$. There are $\binom{x+k}{k}$ ways to do this. The sum of the $\binom{x+k}{k}$ thus counts the choices of $n$ people from the $x+n+1$.

share|improve this answer

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