combinatoric sum (generating functions)

Question

Given the generating functions:

$f(x) = (1-x)^r = \Sigma_{i=0}^\infty a_i x^i$

$g(x) = \frac{1}{(1-x)^{r+1}} = \Sigma_{i=0}^\infty b_i x^i$

$h(x) = f(x) \cdot g(x) = \frac{1}{1-x}$

The factor of $x^k$ in $h(x)$ is $1$ according to:

$\frac{1}{1-x} = \Sigma_{i=0}^\infty x^i$

On the other hand, if

$h(x) = \Sigma_{i=0}^\infty c_i x^i$

then by multiplication of generating functions:

$c_k = \Sigma_{i=0}^k a_i b_{k-i}$

How can we show that $c_k = 1$ based on the a's and the b's?

Hint:

$a_i = (-1)^i \left(r \atop i\right)$ if $0 \leq i \leq r$, and $a_i=0$ for $i > r$

also:

$(\frac{1}{1-x})^{n} = [\Sigma_{i=0}^\infty x^i]^{n} = \Sigma_{i=0}^\infty D(n,i)x^i$

where: $D(n,i) = \left(n-1+i \atop i\right)$

so: $b_i = D(r+1, i) = \left(r+i \atop i\right)$

How can we show $c_k = \Sigma_{i=0}^k a_i b_{k-i}$ is equal to $1$?

Answer 1

I will state the identity as follows:

$$ \sum_{i+j = n} (-1)^i \binom{r}{i} \binom{r+j}{r} = 1.$$

For any subset $A$ of $\{ 1,2, ... , r \}$, let $S_A$ be the set of solutions to the inequality $x_1 + ... + x_r \le n$ with $x_i$ non negative integers (for any $i$) and $x_i$ is positive for any $i \in A$.

By the principal of inclusion exclusion, we have

$$ \sum_{ A \subseteq \{ 1,2, ... , r\} } (-)^{ |A|} |S_A| = | ( S_{ \{ 1 \} } \cup S_{ \{ 2 \} } \cup ... \cup S_{ \{ r \}})^c |,$$ where the complement is with respect to the set of all non-negative solutions to $x_1 + ... + x_r \le n$.

I claim that this is equivalent to your identity. The RHS is 1 because the complement of $S_{\{ 1 \} } \cup ... \cup S_{\{ r \} }$ is the set consisting of the "trivial" solution $x_1=x_2=...=x_r=0 $. This is the RHS of your identity - it counts the size of this complement.

To see that the LHS's agree, think of the index $i$ as the size of $A$ (I leave this as an exercise).

Answer 2

$\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle} \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{\half}{{1 \over 2}} \newcommand{\ic}{\mathrm{i}} \newcommand{\iff}{\Leftrightarrow} \newcommand{\imp}{\Longrightarrow} \newcommand{\ol}[1]{\overline{#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} \color{#f00}{\pars{1 - x}^{r}\,{1 \over \pars{1 - x}^{r + 1}}} & = \sum_{k = 0}^{r}{r \choose k}\pars{-x}^{k}\sum_{n = 0}^{\infty} {-r - 1 \choose n}\pars{-x}^{n} \\[3mm] & = \sum_{k = 0}^{\infty}\sum_{n = 0}^{\infty} {r \choose k}{-r - 1 \choose n}\pars{-x}^{k + n} \\[3mm] & = \sum_{k = 0}^{\infty}\sum_{n = k}^{\infty} {r \choose k}{-r - 1 \choose n - k}\pars{-x}^{n} = \sum_{n = 0}^{\infty}\pars{-x}^{n}\ \underbrace{\sum_{k = 0}^{n}{r \choose k}{-r - 1 \choose n - k}} _{\ds{\equiv\ \mathcal{I}}}\tag{1} \end{align}

---

\begin{align} \mathcal{I} & = \sum_{k = 0}^{n}{r \choose k}{-r - 1 \choose n - k} = \sum_{k = 0}^{n}{r \choose k}{r + n - k \choose r}\pars{-1}^{n - k} \\[3mm] & = \pars{-1}^{n}\sum_{k = 0}^{\infty}{r \choose k}\pars{-1}^{k} \oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{r + n - k} \over z^{r + 1}}\,{\dd z \over 2\pi\ic} \\[3mm] & = \pars{-1}^{n}\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{r + n} \over z^{r + 1}} \sum_{k = 0}^{r}{r \choose k}\bracks{1 + \pars{-\,{1 \over 1 + z}}}^{k} \,{\dd z \over 2\pi\ic} \\[3mm] & = \pars{-1}^{n}\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{r + n} \over z^{r + 1}} \pars{{z \over 1 + z}}^{r}\,{\dd z \over 2\pi\ic} = \pars{-1}^{n}\ \overbrace{\oint_{\verts{z} = 1^{-}}{\pars{1 + z}^{n} \over z}\,{\dd z \over 2\pi\ic}} ^{\ds{=\ {n \choose 0}\ =\ 1}} \\[3mm] & = {n \choose n}\pars{-1}^{n} = {-n + n - 1 \choose n}\pars{-1}^{n}\pars{-1}^{n} \quad\imp\quad \fbox{$\ds{\quad\mathcal{I} = {-1 \choose n}\quad}$} \end{align}

---

Replace this result in $\pars{1}$: $$ \color{#f00}{\pars{1 - x}^{r}\,{1 \over \pars{1 - x}^{r + 1}}} = \sum_{n = 0}^{\infty}{-1 \choose n}\pars{-x}^{n} = \color{#f00}{{1 \over 1 - x}} $$

Answer 3

We can find the result by nearly reverting the way $c_k$, the series with binomial coefficients was obtained. We use the coefficient of operator $[x^i]$ to denote the coefficient of $x^i$ in a series. This way we can write e.g. \begin{align*} [x^i](1+x)^n=\binom{n}{i} \end{align*}

We obtain \begin{align*} c_k&=\sum_{i=0}^ka_ib_{k-i}\\ &=\sum_{i=0}^k(-1)^i\binom{r}{i}\binom{r+k-i}{k-i}\\ &=\sum_{i=0}^\infty(-1)^i[x^i](1+x)^r[y^{k-i}](1+y)^{r+k-i}\tag{1}\\ &=[y^k](1+y)^{r+k}\sum_{i=0}^\infty\left(-\frac{y}{1+y}\right)^i[x^i](1+x)^r\tag{2}\\ &=[y^k](1+y)^{r+k}(1-\frac{y}{1+y})^r\tag{3}\\ &=[y^k](1+y)^k\tag{4}\\ &=1 \end{align*}

Comment:

• In (1) we apply the coefficient of operator twice. We write $\infty$ as upper limit of the series without changing anything since we add only zeros.

• In (2) we use the linearity of the coefficient of operator and apply the rule \begin{align*} [y^{k-i}]A(y)=[y^k]y^iA(y) \end{align*} We rearrange the series and collect the factors with power $i$.

• In (3) we use the substitution rule of the coeffcient of operator \begin{align*} A(x)=\sum_{i=0}^\infty a_i x^i=\sum_{i=0}^\infty x^i [y^i]A(y) \end{align*} and substitute $x$ in $A(x)=(1+x)^k$ with $-\frac{y}{1+y}$.

• In (4) we can simplify the expression to $(1+y)^k$ and have now to select the coefficient of $y^k$ which is equal to $1$.