Proving a Newton generalized version of a binomial theorem identity

259 Views Asked by At

I am wanting to prove that

$$\prod_{k=0}^{m-1}\frac{1}{1-zq^k} = \sum_{n \geq 0}{m+n-1 \brack n}_qz^n$$

which is found on this page.

I've tried a few approaches. I was able to get a proof by taking the derivative of both sides with respect to $q$, but that did not make much combinatorial intuitive sense to me. Any help is greatly appreciated!

1

There are 1 best solutions below

0
On BEST ANSWER

First consider the specialisation $q=1$, in other words ignore the powers of $q$ for now. Now we must show that the coefficient of $z^n$ in $(1-z)^{-m}$ is $\binom{m+n-1}n$. From the geometric series $(1-z)^{-1}=\sum_{i\geq0}z^i$ it follows that the left hand coefficient is the number of ways to obtain $n$ as an ordered sum of $m$ nonnegative integers. This is a classical combinatorics question, and many will immediately cry "star and bars!", but there is a slightly better point of view. Make the sum into a lattice path, by converting every term into that many up-steps, and every "+" between terms into a single right-step. So $n=8=2+0+1+1+4+0$ (with $m=6$) for instance becomes a path from $(0,0)$ to $(m-1,n)=(5,8)$ with steps UURRURURUUUUR. It is easy to see (and well known) that there are $\binom{m-1+n}n$ such paths.

This path cuts across a $n\times(m-1)$ rectangle, splitting off a Young diagram above and to the left of it; in the example this is the diagram of the partition $(4,4,4,4,3,2)$. One gets from the binomial coefficient $\binom{m-1+n}n$ to the Gaussian coefficient $\def\Gauss{\genfrac[]{0pt}{}}\Gauss{m-1+n}n_q$ by not just counting paths, but contributing for each path a power of $q$ equal to the area above the path, so in the example $q^{4+4+4+4+3+2}=q^{21}$. Now if we associate the area of each row of the Young diagram to the up-step that closes the row, we are weighting each vertical step by the number of right-steps that precedes it. That means we can get the total weight from the original sum that made $n$ by multiplying each term by the number of "+" signs to its left; in the example this transforms $8=2+0+1+1+4+0$ into $\def\r{\color{red}}\r2\times0+\r0\times1+\r1\times2+\r1\times3+\r4\times4+\r0\times5=21$. These original (red) terms mark a term chosen from the series $(1-z)^{-1}$; if we replace in the $m$ factors of the product the $z$ by $zq^k$ for $k=0,1,2,\ldots,m-1$ respectively, then the power of $q$ in any contribution to the product of those series can easily be seen to be the value of the "transformed sum" above, in other words the area above the path that identifies that contribution. This gives you a combinatorial proof of the identity.