Combinatorial proof for two identities [duplicate]
Solution 1:
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.
Solution 2:
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$.
- 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.
- 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.