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

| cite | improve this answer | |
$\endgroup$
6
$\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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Finally I found that $\binom{i}{i}=\binom{-1}{i}(-1)^i$ also uses negative binomial coefficients. I always learn a lot from your answer! $\endgroup$ – linear_combinatori_probabi Sep 5 at 9:26
  • 2
    $\begingroup$ @FtyRain: Indeed. In $(7)$ of this answer, I state $\binom{-1}{i}=(-1)^i[i\ge0]$, and of course, $\binom{i}{i}=[i\ge0]$. $\endgroup$ – robjohn Sep 5 at 9:57

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.