# How i can prove that $\sum_{i=0}^{r+1}\binom{n-i}{r-i+1} = \binom{n}{r}$

I'm trying to prove this binomial coefficient identity. $$\sum_{i=0}^{r+1}\binom{n-i}{r-i+1} = \binom{n}{r}$$

The textbook's hint is about using the identity $$\binom{n}{r} =\binom{n}{n-r}$$

I've only reached this $$\frac{1}{(n-1-r)!}\left(\frac{(n-2)!}{(r-1)!}+\frac{(n-3)!}{(r-2)!}+\dots+\frac{(n-r-1)!}{0!}\right)$$

• try looking up Vandermonde’s identity Apr 24, 2017 at 22:07

You can use the Identity:

$$\begin{pmatrix} n \\ r \end{pmatrix} = \begin{pmatrix} n - 1 \\ r \end{pmatrix} + \begin{pmatrix} n - 1 \\ r - 1 \end{pmatrix}$$

Recursively in the last term { $C(n - 1, r - 1)$ }. Doing this you will have:

$$\begin{pmatrix} n \\r \end{pmatrix} = \begin{pmatrix} n - 1 \\r \end{pmatrix} + \begin{pmatrix} n - 1 \\r -1 \end{pmatrix}$$

for the first iteration, then:

$$\begin{pmatrix} n \\r \end{pmatrix} = \begin{pmatrix} n - 1 \\r \end{pmatrix} + \begin{pmatrix} n - 2 \\r -1 \end{pmatrix} + \begin{pmatrix} n - 2 \\r - 2 \end{pmatrix}$$

$$\begin{pmatrix} n \\r \end{pmatrix} = \begin{pmatrix} n - 1 \\r \end{pmatrix} + \begin{pmatrix} n - 2 \\r -1 \end{pmatrix} + \begin{pmatrix} n - 3 \\r - 2 \end{pmatrix} + \begin{pmatrix} n - 4 \\r - 3 \end{pmatrix} + ... + \begin{pmatrix} n - r + 1 \\r - r \end{pmatrix}$$

For all other coming values the terms vanishes to zero ($C(n, r) = 0 \hspace{2mm} \forall \hspace{2mm} r > n$)

this can be written is sigma notation as:

$$\begin{pmatrix} n \\r \end{pmatrix} = \sum_{i=0}^{r} \begin{pmatrix} n - 1 - i \\r - i \end{pmatrix}$$

Changing the index

$$j = i + 1$$

We can write the summation as fallows:

$$\sum_{i=0}^{r} \begin{pmatrix} n - 1 - i \\r - i \end{pmatrix} = \sum_{j = 1}^{r + 1} \begin{pmatrix} n - 1 - (j - 1) \\r - (j - 1) \end{pmatrix}$$

This is:

$$\sum_{j = 1}^{r + 1} \begin{pmatrix} n - j \\r - j + 1 \end{pmatrix}$$

And obviously we can change the dummie index as $j \longrightarrow i$ .

Use the hint to write $\binom{n-i}{r-i+1}=\binom{n-i}{n-r-1}$ and $\binom{n}{r} = \binom{n}{n-r}$, then use the Hockey Stick Identity.

For the proof of the Hockey Stick Identity, I recommend this combinatorial approach if you do not like the algebraic approach in the accepted answer.