Rising factorial power

Question

How the expression below can ve proved:

$(a + b)^{\overline{n}} = \sum\limits_{j=0}^{n}C_n^j a^{\overline{n-j}}b^{\overline{j}}$

where $x^{\overline{n}}$ - is rising factorial power:

$x^{\overline{n}} = (x)\cdot (x+1)\cdot (x+2) \cdots (x+n-1)$

Answer 1

It can be proved both algebraically, by induction on $n$, and combinatorially.

Here’s a hint for the induction argument: if you set up the induction hypothesis correctly, it gives you both

$$(a+b+1)^{\overline{n-1}}=\sum_{j=0}^{n-1}\binom{n-1}ja^{\overline{n-1-j}}(b+1)^{\overline j}$$

and

$$(a+b+1)^{\overline{n-1}}=\sum_{j=0}^{n-1}\binom{n-1}j(a+1)^{\overline{n-1-j}}b^{\overline j}\;.$$

Multiply the first by $a$ and the second by $b$ and add, noting that

$$(a+b)^{\overline n}=(a+b)(a+b+1)^{\overline{n-1}}\;.$$

You’ll need to use the Pascal’s triangle identity on the binomial coefficients.

I don’t see a good way to give a hint for the combinatorial argument, so I’m spoiler-protecting it.

The combinatorial argument is for positive integer $a$ and $b$. For a fixed $n$, however, both sides of the identity are polynomials in $a$ and $b$, and if two polynomials agree at infinitely many values of the arguments, they’re identically equal and therefore agree at all values. The lefthand side is the cardinality of $$A=[a+b]\times[a+b+1]\times\ldots\times[a+b+n-1]\;,$$ where as usual $[m]=\{1,2,\ldots,m\}$. We can construct the members of $A$ in two ways. First, we can put the numbers $1,2,\ldots,a+b$ into a hat. To pick the first coordinate of a member of $A$, you choose one number from the hat. You repeat the procedure $n-1$ more times, but before the $k$-th pick I add the number $a+b+k-1$ to the hat. You can also do it the following way. Put the $1,2,\ldots,a$ in Hat $A$ and the numbers $a+1,a+2,\ldots,a+b$ in Hat $B$. You’ll choose the $n$ coordinates of a member of $A$ in order from left to right. To pick the first coordinate of a member of $A$, you choose one number from either hat. Before picking the second coordinate you specify whether you will choose from Hat $A$ or from Hat $B$, and I put the number $a+b+1$ into the specified hat. We repeat this for each of the remaining $n-2$ choices: on the $k$-th choice you specify from which hat you’ll make the next choice, and I add the number $a+b+k-1$ to the specified hat. The parameter $j$ in the sum $$\sum_{j=0}^n\binom{n}ja^{\overline{n-j}}b^{\overline j}$$ is the number of times that you specify Hat $B$.