2
$\begingroup$

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)$$

$\endgroup$
1
  • 1
    $\begingroup$ try looking up Vandermonde’s identity $\endgroup$
    – lstbl
    Apr 24, 2017 at 22:07

2 Answers 2

1
$\begingroup$

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}$$

Recursively this leads to:

$$\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 $ .

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.