2
$\begingroup$

While examining the product of two upper triangular matrices, I've found that the $(m,n)$'th entry of the resulting matrix amounts to: $$\sum_{k=m+1}^{n+1} \binom{k}{m} \binom{n+1}{k-1} $$ when $n \geq m$ (all other entries are zero).

Although I have found some summations of products of binomial coefficients here, identities for the sum-product as described above have so far eluded me. Do you know whether identities for this series -- or perhaps even for generalizations of it -- exist?

Improve this question
$\endgroup$
1
  • $\begingroup$ Can't you kinda disprove that a closed form exists by considering $n,m$ close together. Like if $n-m = 1$, you get something. If $n-m=2$, you get something. If $n-m = 3$, you get something. I bet finding a closed form / identity that covers these three cases is already very nontrivial (or maybe if you also consider $n-m=4$). $\endgroup$
    – mathworker21
    Commented Sep 19, 2020 at 12:01

1 Answer 1

Reset to default
3
$\begingroup$

$$\sum_{k}{{k\choose m} {n+1\choose k-1}}=\frac{1}{m}\sum_{k}k{k-1\choose m-1}{n+1\choose k-1} = \frac{n+1 \choose m-1}{m}\sum_{k}k{n-m+2 \choose k-m} = \frac{n+1 \choose m-1}{m}(\sum_{k}(k-m){n-m+2 \choose k-m}) + {n+1 \choose m-1}\sum_{k}{n-m+2 \choose k-m} = \frac{{n+1 \choose m-1}(n-m+2)}{m}(\sum_{k}{n-m+1 \choose k-m-1}) + {n+1 \choose m-1}2^{n-m+2} = \frac{{n+1 \choose m-1}2^{n-m+1}(n+m+2)}{m}$$

The identities I have used are ${n \choose k} = \frac{n}{k}{n-1 \choose k-1}, \sum_{k}{n \choose k} = 2^n, {a \choose b}{b \choose c} = {a \choose c}{a-c \choose b-c}$.

The summation in the question excludes $k=n+2,m$, so your answer is actually $$\frac{{n+1 \choose m-1}2^{n-m+1}(n+m+2)}{m}-{n+2\choose m}-{n+1\choose m-1} $$

Improve this answer
$\endgroup$
4
  • $\begingroup$ Nice. I had wrongly thought that nothing could be done with this type of sum. $\endgroup$
    – Mark Wildon
    Commented Sep 19, 2020 at 14:52
  • $\begingroup$ @Random thank you! When you write $\sum_{k}$, could you please indicate what you mean by that? What exactly are the lower and upper bounds of such a sum? $\endgroup$
    – Max Lonysa Muller
    Commented Sep 19, 2020 at 15:22
  • 1
    $\begingroup$ @Max Muller Technically, I am summing over $k$ between $m$ and $n+2$. I prefer to sum over all integer $k$ and just say that the binomial coefficient ${a \choose b}$ vanishes if $b > a$ or $b < 0$. I find that summing over all integers gives more natural looking results. $\endgroup$
    – Random
    Commented Sep 19, 2020 at 15:57
  • $\begingroup$ Indeed as you can see from Mark's comment, the "unnatural" bounds obscured the fact that the answer has only small prime factors. $\endgroup$
    – Random
    Commented Sep 19, 2020 at 16:00

You must log in to answer this question.

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