Home » Uncategorized » Double binomial sum

Double binomial sum

Prove that

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

Solution

Summing diagonally we have that

\begin{aligned} \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}} \\ &\overset{(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} \\ &\overset{(2)}{=} \sum_{N=0}^{m+n} \binom{m+n}{N}^{-1} \binom{m+n}{N} \\ &= m+n+1 \end{aligned}

(1) It holds that

    \[\binom{m}{i}=0\]

for i=m+1, \dots, N.

(2) It holds that

    \[\sum_{i=0}^{N} \binom{m}{i} \binom{n}{N-i} = \binom{m+n}{N}\]

In general it holds that

    \[\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+\ldots+b_n}{a_1+a_2+\ldots+a_n}}=\sum_{i=1}^{n}b_i+1\]

Read more

Leave a comment

Who is Tolaso?

Find out more at his Encyclopedia Page.

Donate to Tolaso Network