Home » Uncategorized » Nested binomial sum

Nested binomial sum

Prove 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}}=b_1+b_2+\cdots+b_n+1\]

Solution

We may begin with the beta function identity for non negative integer values of a, b.

    \[\int_0^1 x^{b-a}(1-x)^a \, \mathrm{d}x = \frac{1}{(b+1)\binom{b}{a}}\]

Hence, for non-negative integers a', b'

    \begin{align*} \sum_{a = 0}^{b}\frac{\binom{b}{a}}{\binom{b+b'}{a+a'}} &= (b+b'+1)\sum_{a = 0}^{b}\binom{b}{a}\int_0^1 x^{b+b'-a-a'}(1-x)^{a+a'}\,\mathrm{d}x\\ &= (b+b'+1)\int_0^1 x^{b'-a'}(1-x)^{a'}\, \mathrm{d}x\\ &= \frac{b+b'+1}{(b'+1)\binom{b'}{a'}} \end{align*}

As a result we may compute the nested summation as,

\begin{aligned} \sum_{a_1 = 0}^{b_1}\cdots \sum_{a_n = 0}^{b_n}\frac{\binom{b_1}{a_1}\cdots \binom{b_n}{a_n}}{\binom{b_1+\cdots+b_n}{a_1+\cdots+a_n}} &= \frac{b_1+\cdots + b_n +1}{b_1+\cdots+b_{n-1}+1}\sum_{a_1 = 0}^{b_1}\cdots \sum_{a_{n-1} = 0}^{b_{n-1}}\frac{\binom{b_1}{a_1}\cdots \binom{b_{n-1}}{a_{n-1}}}{\binom{b_1+\cdots+b_{n-1}}{a_1+\cdots+a_{n-1}}} \\ &= \cdots \\ &= \prod_{j=0}^{n-2}\frac{b_1+\cdots+b_{n-j}+1}{b_1+\cdots+b_{n-j-1}+1}\sum_{a_1=0}^{b_1}\frac{\binom{b_1}{a_1}}{\binom{b_1}{a_1}}\\ &= b_1+\cdots+b_n+1 \end{aligned}

Read more

Leave a comment

Donate to Tolaso Network