2
$\begingroup$

from the answer: Proof of the hockey stick/Zhu Shijie identity $\sum\limits_{t=0}^n \binom tk = \binom{n+1}{k+1}$

this happens from step 4 to 5:
$$ \sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}=\binom{-k-j-2}{n-j-k} $$

if I apply the identity on the result, I get:

$$ \binom{m+n}{r}=\sum_{k=0}^r\binom{m}{k}\binom{n}{r-k}\\\\ \binom{-k-j-2}{n-j-k}=\sum_{t=0}^{n-j-k}\binom{-k-1}{t}\binom{-j-1}{(n-j-k)-t} $$

my question is: how do you get $t-k$ on the bottom left ? (no variant of the identity seems to have that)
and what you do regarding the summation bounds ? ($(n-j-k)$ as upper bound doesn't seem equivalent)


(I copied the answer in case it gets edited):

$$ \binom{-n}{k}=(-1)^k\binom{n+k-1}{k}\tag{1} $$

Here is a generalization of the identity in question, proven using the Vandermonde Identity

\begin{align*} \sum_{t=0}^n\binom{t}{k}\binom{n-t}{j} &=\sum_{t=0}^n\binom{t}{t-k}\binom{n-t}{n-t-j}\tag{2}\\\\ &=\sum_{t=0}^n(-1)^{t-k}\binom{-k-1}{t-k}(-1)^{n-t-j}\binom{-j-1}{n-t-j}\tag{3}\\\\ &=(-1)^{n-j-k}\sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}\tag{4}\\\\ &=(-1)^{n-j-k}\binom{-k-j-2}{n-j-k}\tag{5}\\\\ &=\binom{n+1}{n-j-k}\tag{6}\\\\ &=\binom{n+1}{j+k+1}\tag{7} \end{align*}

Explanation:
$(2)$: $\binom{n}{k}=\binom{n}{n-k}$
$(3)$: apply $(1)$ to each binomial coefficient
$(4)$: combine the powers of $-1$ which can then be pulled out front
$(5)$: apply Vandermonde
$(6)$: apply $(1)$
$(7)$: $\binom{n}{k}=\binom{n}{n-k}$

$\endgroup$

1 Answer 1

3
$\begingroup$

Recall that

$$\binom{v}{m} = 0 \quad m>v \; \textrm{ or} \; m<0 $$

Note that in

$$S=\sum_{t=0}^n\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}$$

If $$ t<k \implies \displaystyle \binom{-k-1}{t-k}=0$$

and

$$ t>n-j \implies \binom{-j-1}{n-t-j}=0$$

Hence we can write our sum with the following indexes:

$$S=\sum_{\color{red}{t=k}}^{\color{red}{n-j}}\binom{-k-1}{t-k}\binom{-j-1}{n-t-j}$$

Now do the change of variable $m=t-k$. By Vandermonde's:

$$S=\sum_{t=k}^{n-j}\binom{-k-1}{t-k}\binom{-j-1}{n-t-j} = \sum_{\color{red}{m=0}}^{\color{green}{n-j-k}}\binom{-k-1}{\color{red}{m}}\binom{-j-1}{\color{green}{n-j-k}-\color{red}{m}} = \binom{-k-j-2}{\color{green}{n-j-k}}$$

$\endgroup$
3
  • $\begingroup$ thanks, I needed some explanation for variable substitution inside summation bounds, $\sum _{t=k}^{t=n-j}$, lower bound: $m=t-k\Leftrightarrow m=( k) -k\Leftrightarrow m=0$, upper bound: $m=t-k\Leftrightarrow m=( n-j) -k\Leftrightarrow m=n-j-k$, $\sum _{m=0}^{m=n-j-k}$, is this the optimal way or correct way to think about substitution inside summation bounds ? $\endgroup$
    – Mr. Doge
    Commented May 19 at 20:58
  • 1
    $\begingroup$ @Mr.Doge Hi, yes that is correct $\endgroup$
    – Bertrand87
    Commented May 19 at 23:46
  • 1
    $\begingroup$ See also properties 3 and 7 here (index shift): en.wikipedia.org/wiki/Summation#Identities $\endgroup$
    – Bertrand87
    Commented May 20 at 0:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .