4
$\begingroup$

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.

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

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

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

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

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