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$

2 Answers 2

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$
2
  • $\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$
    – Mahesha999
    Commented Feb 14, 2016 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$ Commented Feb 14, 2016 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .