1
$\begingroup$

I was learning generating functions, where faced following:

$$(1-x)^{-n}=\sum_{i=0}^\infty\binom{n+i-1}{i}x^i$$

I didn't get how is this arrived. I tried out to prove this to me. But failed. Using binomial theorem, I can get that

$$(1-x)^{-n}=\sum_{i=0}^\infty\binom{-n}{i}x^i$$

However I realize that, I am first time facing $-$ve $n$ in $\binom{-n}{i}$ and I dont know how to solve this. I tried but reached to something involving $-$ve factorial. Googling revealed that $(-n)!$ is somewhat undefined. Wolfram says $(-4)!$ is complex infinity. I also came across this thread which solves $$\binom{-4}{3}=\frac{(-4)_3}{3!}$$ I didnt get how this equality is arrived. Overall I am lost.

$\endgroup$
7
$\begingroup$

There are several ways to derive the result; I’ll start with the one using the binomial theorem. What you have isn’t quite right: the $x$ term in $1-x$ is negative, so it should be

$$(1-x)^{-n}=\sum_{k\ge 0}\binom{-n}k(-x)^k=\sum_{k\ge 0}\binom{-n}k(-1)^kx^k\;.$$

For $\binom{-n}k$ you need to know the full definition of the binomial coefficient: for all real $x$ and non-negative integers $k$ we define

$$\binom{x}k=\frac{x^{\underline k}}{k!}=\frac{x(x-1)(x-2)\ldots(x-k+1)}{k!}\;;$$

you can check that this agrees with the more familiar definition when $x$ is a non-negative integer. Now we have

$$\begin{align*} \binom{-n}k&=\frac{(-n)^{\underline k}}{k!}\\ &=\frac{(-n)(-n-1)(-n-2)\ldots(-n-k+1)}{k!}\\ &=(-1)^k\cdot\frac{n(n+1)(n+2)\ldots(n+k-1)}{k!}\\ &=(-1)^k\cdot\frac{(n+k-1)!}{k!(n-1)!}\\ &=(-1)^k\binom{n+k-1}k\;, \end{align*}$$

so that

$$(1-x)^{-n}=\sum_{k\ge 0}(-1)^k\binom{n+k-1}k(-1)^kx^k=\sum_{k\ge 0}\binom{n+k-1}kx^k\;,$$

since $(-1)^k(-1)^k=(-1)^{2k}=1$.


Another way is to start from the geometric series

$$\frac1{1-x}=\sum_{k\ge 0}x^k\tag{1}$$

and differentiate repeatedly. If I differentiate $(1-x)^{-1}$ with respect $x$ repeatedly, I get $(1-x)^{-2}$, $2(1-x)^{-3}$, $6(1-x)^{-4}$, $24(1-x)^{-5}$, and in general I have

$$\frac{d^n}{dx^n}(1-x)^{-1}=\frac{n!}{(1-x)^{n+1}}\;;$$

this is easy to prove by induction on $n$.

Differentiating the righthand side of $(1)$ $n$ times with respect to $x$, I get

$$\sum_{k\ge 0}k(k-1)(k-2)\ldots(k-n+1)x^{n-k}\;.$$

Setting $\ell=k-n$, so that $k=\ell+n$, I can rewrite this as

$$\sum_{\ell\ge 0}(\ell+n)(\ell+n-1)\ldots(\ell+1)x^\ell=\sum_{\ell\ge 0}\frac{(\ell+n)!}{\ell!}x^\ell\;.$$

Putting the two pieces together, we see that

$$\frac{n!}{(1-x)^{n+1}}=\sum_{\ell\ge 0}\frac{(\ell+n)!}{\ell!}x^\ell\;,$$

or, after dividing by $n!$,

$$\frac1{(1-x)^{n+1}}=\sum_{\ell\ge 0}\binom{\ell+n}\ell x^\ell\;.$$

Now just replace $n$ by $n-1$ throughout to get

$$(1-x)^{-n}=\sum_{\ell\ge 0}\binom{\ell+n-1}\ell x^\ell\;,$$

as desired.

$\endgroup$
  • $\begingroup$ Thanks that clear things up. Was just guessing if there is any intuitive logical / combinatorial connection between selecting $k$ things from $-n$ things i.e. $\binom{-n}{k}$ (though even that does not makes any straight sense) and dividing $k$ identical things among $n$ groups (if I am not wrong in interpreting $\binom{n+k-1}{k}$ as this, and yes there is $(-1)^k$ ). Or its just mathematical coincidence? $\endgroup$ – anir123 Feb 14 '16 at 7:47
  • $\begingroup$ @PardonMeForMySuperPoorMaths: You’re welcome. I can’t offhand see any combinatorial significance, but I have to admit that I’ve not given it a lot of thought. (And yes, your interpretation of $\binom{n+k-1}k$ is correct.) $\endgroup$ – Brian M. Scott Feb 14 '16 at 17:30
1
$\begingroup$

This is a comment on Brian M. Scott's excellent answer.

I like to write binomial coefficients and similar products directly in terms of the product notation and doing my manipulations without any "..."s.

For example,

$\begin{array}\\ \text{Since}\\ \binom{n}{m} &=\frac{\prod_{k=0}^{m-1}(n-k)}{m!}\\ \text{we have}\\ \binom{-n}{m} &=\frac{\prod_{k=0}^{m-1}(-n-k)}{m!}\\ &=\frac{(-1)^m\prod_{k=0}^{m-1}(n+k)}{m!}\\ &=(-1)^m\frac{\prod_{k=0}^{m-1}(n+m-1-k)}{m!} \qquad\text{(reversing the order of the product)}\\ &=(-1)^m\binom{n+m-1}{m}\\ \end{array} $

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.