# A combinatorial identity

I came across the following identity today.
$\displaystyle{1 \choose k} + {2 \choose k} + \ldots + {99 \choose k} = {100 \choose k+1}$
It is not exactly difficult to establish if one uses the Pascal relation repeatedly.
$\displaystyle{m \choose k+1} = {m-1 \choose k} + {m-1 \choose k+1}$
$\displaystyle = {m-1 \choose k} + {m-2 \choose k} + {m-2 \choose k+1} = \ldots$
$\displaystyle = \sum_{j=1}^{m-1} {m-j \choose k} + {0 \choose k+1}$

An alternative proof is to extract the coefficient of $x^k$ from the generating function identity:
$\displaystyle \sum_{j=0}^{99} (x+1)^j = \frac{ (x+1)^{100} – 1}{ (x+1)-1}.$

I’m thinking that this must have a nice combinatorial proof, but all my references are in my office.

This entry was posted in Combinatorics. Bookmark the permalink.

### 2 Responses to A combinatorial identity

1. Brent Yorgey says:

One combinatorial interpretation is as follows: if you are picking (k 1) out of m items, given some ordering of the m items you can break your choices up into disjoint cases based on how many of the items you pass up before choosing the first. After choosing the jth item (and passing up the first j-1) you have exactly (m – j) \choose k ways to choose the rest.

2. tpc says:

Thanks Brent. That was neat.