Proof of binomial formula to extract coefficients of a generating function

Question

A generating function ends up rearranged into a form:

\begin{align} (1+x+x^2+\dotsb)^n&=\frac{1}{(1-x)^n}\\[6px] &= 1+\binom{1+n-1}{1}x+\binom{2+n-1}{2}x^2+\binom{3+n-1}{3}x^3\\ &\phantom{=\;1}+\dots+\binom{r+n-1}{r}x^r+\dotsb \end{align}

used to extract coefficients.

I can't find a proof (some construction akin to Pascal's triangle, for example) of these coefficients working for all cases.

Probably, it is just a matter of knowing the term to include in the online search, and if this is the case, I'll be happy to delete the question.

Answer 1

For $n=1$ it’s just a geometric series:

$$\frac1{1-x}=\sum_{n\ge 0}x^n\;.$$

Now suppose that

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

Then

$$\begin{align*} \frac1{(1-x)^{n+1}}&=\frac1{(1-x)^n}\cdot\frac1{1-x}\\ &=\left(\sum_{k\ge 0}\binom{n-1+k}kx^k\right)\left(\sum_{k\ge 0}x^k\right)\\ &\overset{(1)}=\sum_{k\ge 0}\left(\sum_{j=0}^k\binom{n-1+j}j\right)x^k\\ &=\sum_{k\ge 0}\left(\sum_{j=0}^k\binom{n-1+j}{n-1}\right)x^k\\ &\overset{(2)}=\sum_{k\ge 0}\binom{n+k}nx^k\\ &=\sum_{k\ge 0}\binom{n+k}kx^k\;, \end{align*}$$

as desired. Here $(1)$ is just a Cauchy product, and $(2)$ is a form of the hockey-stick identity.

Answer 2

The statement is obviously true for $n=1$; suppose it is for $n$; then we can see that \begin{align} (1+x+\dotsb)^{n+1}=\frac{1}{n}D\frac{1}{(1-x)^n}= \frac{1}{n}\sum_{k\ge1}k\binom{k+n-1}{k}x^{k-1}= \sum_{k\ge0}\frac{k+1}{n}\binom{k+n}{k+1}x^k \end{align} and it's just a matter of proving that $$ \frac{k+1}{n}\binom{k+n}{k+1}=\binom{k+n}{k} $$ Indeed, $$ \frac{k+1}{n}\binom{k+n}{k+1}= \frac{k+1}{n}\frac{(k+n)(k+n-1)\dotsm(k+n-(k+1)+1)}{(k+1)!}= \binom{k+n}{k} $$

Answer 3

Or, if you write $\dfrac1{(1-x)^n} =(1-x)^{-n} $, you can use the generalized binomial series $(1+x)^a =\sum_{n=0}^{\infty} \binom{a}{n} x^n $ where, for any real (or complex) $a$, $\binom{a}{n} =\dfrac{\prod_{k=0}^{n-1}(a-k)}{n!} $. This converges whenever $|x| < 1$.

Note that, if $m$ is a positive integer,

$\begin{array}\\ \binom{-m}{n} &=\dfrac{\prod_{k=0}^{n-1}(-m-k)}{n!}\\ &=(-1)^n\dfrac{\prod_{k=0}^{n-1}(m+k)}{n!}\\ &=(-1)^n\dfrac{\prod_{k=0}^{n-1}(m+(n-1-k))}{n!}\\ &=(-1)^n\dfrac{\prod_{k=0}^{n-1}(m+n-1-k)}{n!}\\ &=(-1)^n \binom{m+n-1}{n}\\ &=(-1)^n \binom{m+n-1}{m-1}\\ \text{so that}\\ (1-x)^{-m} &=\sum_{n=0}^{\infty} \binom{-m}{n} (-x)^n\\ &=\sum_{n=0}^{\infty} (-1)^n \binom{m+n-1}{m-1} (-1)^n x^n\\ &=\sum_{n=0}^{\infty} \binom{m+n-1}{m-1} x^n\\ \end{array} $