# binomial coefficient equal to sum

I have observed the following relation

$$\binom{n}{k}=\sum\limits_{i=0}^{k} \binom{n-i-1}{k-i}, \quad \frac{n}2\leq k \leq n-1$$

Numerical example with $$n=5$$ and $$k=3$$

$$\binom{\color{red}5}{\color{blueviolet}3}= \binom{\color{Magenta}4}{\color{blueviolet}3}+\binom{\color{blueviolet}3}{\color{Orange}2}+\binom{\color{Orange}2}{\color{YellowGreen}1}+\binom{\color{YellowGreen}1}{\color{Brown}0}$$

$$10\ \ \ = \ \ \ 4 \ \ \ +\ \ \ 3 \ \ \ + \ \ \ 2 \ \ \ \ + \ \ 1$$

Is this relation true? If yes, is there a name for it?

I´ve used identities like $$\binom{n+1}{k+1} = \binom nk + \binom n{k+1}$$ to show the relation above, but I failed. Does anyone have an idea how to manage it?

Thanks for taking time to read the question.

• It is an instance of the hockeystick identity. For a proof of it see here. – drhab Dec 8 '19 at 10:38
• @drhab Yes, it seems that it has something to do with it-thanks. But I don´t know how to use it here. – callculus Dec 8 '19 at 10:44

See my comment on your question.

The hockeystick identity tells us that: $$\sum_{i=r}^{n}\binom{i}{r}=\binom{n+1}{r+1}$$

Applying this we find:

$$\sum_{i=0}^{k}\binom{n-i-1}{k-i}=\sum_{i=n-1-k}^{n-1}\binom{i}{n-1-k}=\binom{n}{n-k}=\binom{n}{k}$$

• Oh yeah. With the this kind of index shift it works. Thanks for the answer. – callculus Dec 8 '19 at 10:53
• You are very welcome. – drhab Dec 8 '19 at 10:53

This can also be shown with negative binomial coefficients and Vandermonde's Identity: \begin{align} \sum_{i=0}^k\binom{n-i-1}{k-i} &=\sum_i\binom{n-i-1}{k-i}\binom{i}{i}\tag1\\ &=\sum_i\binom{k-n}{k-i}(-1)^{k-i}\binom{-1}{i}(-1)^i\tag2\\ &=(-1)^k\binom{k-n-1}{k}\tag3\\[3pt] &=\binom{n}{k}\tag4 \end{align} Explanation:
$$(1)$$: remove the limits from the summation
$$(2)$$: negative binomial coefficients
$$(3)$$: Vandermonde Identity
$$(4)$$: negative binomial coefficients