Posted by tpc at March 23rd, 2009

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.