Combinatorial Sum Identity

For $m,n > 0$ prove that

$\displaystyle 1 + \sum_{k=1}^{m} \binom{k+n}{k} = \binom{m+n+1}{m}$

Harder version:

$\displaystyle \sum_{k=l}^{m} \binom{k+n}{k} = \binom{m+n+1}{n+1} - \binom{n+l}{n+1}$

First Solution

Note that

$\displaystyle \binom{k+n}{k} = \frac{k+n+1}{n+1}\binom{k+n}{k} - \frac{k}{n+1}\binom{k+n}{k}$

$\displaystyle = \binom{k+n+1}{n+1} - \binom{k+n}{n+1}$

So

$\displaystyle \sum_{k=l}^{m} \binom{k+n}{k} = \binom{n+m}{m} + \cdots + \binom{n+k}{k} + \cdots + \binom{n+l}{l}$

$\displaystyle = \binom{n+m+1}{n+1} - \binom{n+m}{n+1} + \binom{n+m}{n+1} - \binom{n+m-1}{n+1} + \cdots + \binom{n+l+1}{n+l} - \binom{n+l}{n+1}$

$\displaystyle = \binom{m+n+1}{m} - \binom{n+l}{n+1}$

Second Solution

For the normal version, suppose in the Cartesian lattice we walk from $(0,0)$ to $(m, n+1)$ where we can only move 1 unit to the right or to the top. There are $\binom{m+n+1}{m}$ possible paths.

Consider the last upwards motion that we make, say from $(k,n)$ to $(k,n+1)$. There is only one possible path to complete after this motion, that is, all horizontal motions. But in order to get here, we may use any possible path from $(0,0)$ to $(k,n)$. There are $\binom{k+n}{k}$ such paths. Note that $k$ can range from $0$ to $m$, so the 1 term in the LHS accounts for the case where $k=0$.

For the harder version, suppose now we limit ourselves for $k \geq l$. The LHS describes the number of paths where the last upward motion happens at or after $l$. The negative term in the RHS describes the number of paths where the last upward motion happen before $l$, because that means the path must pass through $(l-1, n+1)$.