2
$\begingroup$

So, I try to manipulate some series and this sum came up in the coefficients $$\sum_{k=m}^{l-n+m}\binom{k}{m}\binom{l-k}{n-m}$$ whith $l\ge n$.

I've seen the identities of the binomial coefficients but I couldn't figure any way to simplify it. Any ideas?

$\endgroup$
2
  • $\begingroup$ What is the question? $\endgroup$
    – user122283
    Commented Apr 27, 2014 at 16:30
  • $\begingroup$ Oh! The question is "can this sum be simplified to something nicer?" $\endgroup$
    – tst
    Commented Apr 27, 2014 at 17:39

2 Answers 2

Reset to default
5
$\begingroup$

We have $$ \sum_{k=m}^{l-n+m} \binom km \binom{l-k}{n-m} = \begin{cases} \binom{l+1}{n+1} &\text{if $0\le m\le n$} \\ 0 &\text{otherwise} \end{cases} $$ Here's the bulk of a proof by generating functions: equation (1.5.5) in generatingfunctionology gives $$ \sum_{k=0}^\infty \binom kn x^k = \frac{x^n}{(1-x)^{n+1}} $$ if $n\ge 0$. Thus \begin{align*} \sum_{l=0}^\infty \left(\sum_{k=m}^{l-n+m} \binom km \binom{l-k}{n-m}\right) x^{l+1} &= x\left(\sum_{k=0}^\infty \binom km x^k\right) \left(\sum_{k=0}^\infty \binom k{n-m} x^k\right) \\ &= x\cdot\frac{x^m}{(1-x)^{m+1}}\cdot\frac{x^{n-m}}{(1-x)^{n-m+1}} \\ &= \frac{x^{n+1}}{(1-x)^{n+2}} \\ &= \sum_{l=0}^\infty \binom l{n+1} x^l \end{align*} Now identify coefficients (noting that there's $x^l$ on one side and $x^{l+1}$ on the other).

(If you want a more elementary proof, I'd suggest looking at some proof of the well-known identity $$ \sum_{k=n}^l \binom kn = \binom{l+1}{n+1} $$ (which is the case $m=n$ of your sum) and seeing if you can adapt the ideas.)

$\endgroup$
5
  • $\begingroup$ Yes, I forgot to write that $m\le n$. Thank you very much for the answer and for generatingfunctionology, I wasn't aware of its existence. $\endgroup$
    – tst
    Commented Apr 27, 2014 at 20:06
  • $\begingroup$ Just a question, how do you get your first equality? I mean where you split the infinite sum into 2 infinite sums. $\endgroup$
    – tst
    Commented Apr 27, 2014 at 20:08
  • $\begingroup$ It's convolution of power series: $(\sum_{m=0}^\infty a_m x^m)(\sum_{n=0}^\infty b_n x^n) = \sum_{m=0}^\infty \sum_{n=0}^\infty a_m b_n x^{m+n}$; now group like terms, i.e., group by the value of the exponent $m+n$ (call that $l$), getting $\sum_{l=0}^\infty \big(\sum_{m=0}^l a_m b_{l-m}\big) x^l$. (Your indices are a bit different, but the missing terms are all zero.) $\endgroup$
    – user21467
    Commented Apr 27, 2014 at 20:26
  • $\begingroup$ Well, it's not convolution of power series, sorry — it's just multiplication of power series, which corresponds to convolution of their coefficient sequences. $\endgroup$
    – user21467
    Commented Apr 27, 2014 at 20:29
  • $\begingroup$ I would not be able to see that ever. Thank you very much indeed. $\endgroup$
    – tst
    Commented Apr 27, 2014 at 23:38
2
$\begingroup$

Let us consider $0 \le m \le n$ and count in two ways:

What is the number of ways of choosing $n+1$ balls in a set of $l+1$ balls? (the balls are enumerated 1,2,...,l+1)

On one hand, the answer is $\binom{l+1}{n+1}$.

On the other hand, let $a_1 < a_2 <\cdots <a_{n+1}$ be a choice of numbers. Let count the number of choices of $n+1$ elements, where $a_{m+1}=k+1$: $\binom{k}{m} \cdot \binom{l+1-(k+1)}{n-m}$. So, follow that

$\sum_{k=m}^{l-n+m}\binom{k}{m}\binom{l-k}{n-m}=\binom{l+1}{n+1}$

$\endgroup$

You must log in to answer this question.

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