How to prove that generating function of series ($1 ,\binom{m}{1},\binom{m+1}{2},\binom{m+2}{3},...$ ) equals $\frac{1}{(1-z)^m}$ .

Question

How to prove that generating function of series ($1 ,\binom{m}{1},\binom{m+1}{2},\binom{m+2}{3},...$ ) equals $\frac{1}{(1-z)^m}$ .

How do I do this? I know that I have to use some differentiation somewhere but what series do I use to start?

Answer 1

First a couple of preliminary notes before we get to the proof.

Lemma

$$\sum_{i=k}^n\binom{i}{k}=\binom{n+1}{k+1}$$

Proof of Lemma

The RHS counts the number of $k+1$ element subsets of $U=\{0\,\dotsc, n\}$. The RHS counts the same thing as the number of $k+1$ element subsets of $U$ with maximum element $i$ is $\binom{i}{k}$.$\blacksquare$

Note on Multiplication of Formal Power Series

In general if $$ A(x)=\sum_{n\geq0}a_n x^n;\quad B(x)=\sum_{n\geq0}b_n x^n $$ are two formal power series then their product is given by $$ A(x)B(x)=\sum_{n\geq0}\left(\sum_{k=0}^na_kb_{n-k}\right)x^n. $$ In particular since $(1-x)^{-1}=\sum_{n\geq 0} x^n$, it follows that $$ A(x)(1-x)^{-1}=\sum_{n\geq0}\left(\sum_{k=0}^na_k\right)x^n\tag{1} $$ The Problem

We claim that $$ (1-z)^{-m}=\sum_{n\geq0}\binom{m+n-1}{n}z^{n} \quad (m\ge 1) $$

Proof by Induction

The base case holds since $$ (1-z)^{-1}=\sum_{n\geq0} z^n=\sum_{n\geq0}\binom{1+n-1}{n}z^n $$ as desired. Suppose that the result holds for all integers at most $m$. Then $$ (1-z)^{-m-1}=(1-z)^{-m}\times(1-z)^{-1}=\sum_{n\geq0}\left( \sum_{k=0}^n\binom{m+k-1}{k} \right) x^n $$ by (1) and the induction hypothesis. But $$ \sum_{k=0}^n\binom{m+k-1}{k}=\sum_{k=0}^n\binom{m+k-1}{m-1}=\sum_{i=m-1}^{n+m-1}\binom{i}{m-1}=\binom{n+m}{m}=\binom{m+n}{n} $$ as desired where we have used the lemma.

Answer 2

One way is to take $\frac{1}{1-z} = 1 + z + z^2 + \cdots$ and raise both sides to the $m$th power. To find the coefficient of $z^k$ in the resulting series, you need to solve a combinatorics problem (the stars and bars approach may help).

Another way is to start with $\frac{1}{1-z} = 1 + z + z^2 + \cdots$, differentiate both sides $m - 1$ times, and do some rearranging.

Answer 3

Just use the fact that the coefficient of $z^n$ in the power series expansion near $0$ of a holomorphic function $f(z)$ is equal to $\;\dfrac{f^{(n)}(0)}{n!}$.

For $f(z)=\dfrac1{(1-z)^m}$, we see by an easy induction that \begin{alignat}{2} &&\biggl(\frac1{(1-z)^m}\biggr)^{\mkern-5mu(n)}&=\frac{m(m+1)\dotsm(m+n-1)}{(1-z)^{m+n}},\\ &\text{so }&f^{(n)}(0)&=m(m+1)\dotsm(m+n-1)=\frac{(m+n-1)!}{(m-1)!}\\ &\text{and eventually}\mkern-20mu &\frac{f^{(n)}(0)}{n!}&=\frac{(m+n-1)!}{(m-1)!\:n!}=\binom{m+n-1}{n}. \end{alignat}

Answer 4

$\newcommand{\bbx}[1]{\,\bbox[15px,border:1px groove navy]{\displaystyle{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$ \begin{align} \sum_{k = 0}^{\infty}{m + k - 1 \choose k}z^{k} & = \sum_{k = 0}^{\infty}\overbrace{{-\bracks{m + k - 1} + k - 1 \choose k}\pars{-1}^{k}}^{\ds{Negating\ \mbox{the Binomial}}}\,\,\, z^{k} = \sum_{k = 0}^{\infty}{-m \choose k}\pars{-z}^{k} \\[5mm] & = \bracks{\rule{0pt}{4mm}1 + \pars{-z}}^{\, -m} = \bbx{1 \over \pars{1 - z}^{m}} \end{align}