Home » Uncategorized » Double binomial sum

Double binomial sum

Evaluate the double sum

    \[\mathcal{S} = \sum_{i=0}^m \sum_{j=0}^n \frac{\binom{m}{i}\binom{n}{j}}{\binom{m+n}{i+j}}\]

Solution

We sum diagonally , hence:

    \begin{align*} \sum_{i=0}^{m}\sum_{j=0}^{n}\frac{\binom{m}{i}\binom{n}{j}}{\binom{m+n}{i+j}}&\overset{i+j=N}{=\! =\! =\! =\!}\sum_{N=0}^{m+n}\sum_{i=0}^m\frac{\binom{m}{i}\binom{n}{N-i}}{\binom{m+n}{N}}\\ &\stackrel{(1)}{=}\sum_{N=0}^{m+n}\sum_{i=0}^{N}\frac{\binom{m}{i}\binom{n}{N-i}}{\binom{m+n}{N}}\\ &=\sum_{N=0}^{m+n}\binom{m+n}{N}^{-1}\sum_{i=0}^{N}\binom{m}{i}\binom{n}{N-i}\\ &\stackrel{(2)}{=} \sum_{N=0}^{m+n}\binom{m+n}{N}^{-1}\binom{m+n}{N}\\ &=m+n+1 \end{align*}

(1): For i=m+1,\ldots,N it holds \binom{m}{i}=0.

(2): \displaystyle \sum_{i=0}^{N}\binom{m}{i}\binom{n}{N-i}=[x^N](1+x)^{m+n}=\binom{m+n}{N}.

Conjecture: Does the following equality

    \[\sum_{a_1=0}^{b_1}\sum_{a_2=0}^{b_2}\cdots\sum_{a_n=0}^{b_n}\frac{\binom{b_1}{a_1}\binom{b_2}{a_2}\cdots\binom{b_n}{a_n}}{\binom{b_1+b_2+\cdots+b_n}{a_1+a_2+\cdots+a_n}}=b_1+b_2+\cdots+b_n+1\]

hold?

Read more

Leave a comment

Who is Tolaso?

Find out more at his Encyclopedia Page.

Donate to Tolaso Network