1
$\begingroup$

As part of a proof that $(1-x)^n\cdot \left ( \frac{1}{1-x} \right )^n=1$ in the context of generating functions it states that $\sum_{i=0}^k(-1)^i\binom{n}{i}D(n,k-i))=0$ where $D(n,k)$ is defined as $D(n,k)=\binom{n-1+k}{k}=\binom{n-1+k}{n-1}\;.$

I don't understand the above step, which is the last in the proof.

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

and

$\left ( \frac{1}{1-x} \right )^n=\sum_{i=0}^{\infty}D(n,i)x^i$

  • 0
    Satisfied by an answer below?2012-06-17

2 Answers 2

2

In general, $ \left(\sum\limits_{k=0}^{+\infty}a_kx^k\right)\cdot\left(\sum\limits_{k=0}^{+\infty}b_kx^k\right)=\sum\limits_{k=0}^{+\infty}c_kx^k\qquad\text{with}\qquad c_k=\sum\limits_{i=0}^ka_ib_{k-i}. $ In your case, $ \sum\limits_{k=0}^{+\infty}c_kx^k=1\qquad\text{if and only if}\qquad c_0=1\ \text{and}\ c_k=0\ \text{for every}\ k\geqslant1. $


Edit: Here, choosing $a_k=(-1)^k{n\choose k}$ and $b_k=D(n,k)$, one gets $(1-x)^n=\sum\limits_{k=0}^{+\infty}a_kx^k$ and $\dfrac1{(1-x)^n}=\sum\limits_{k=0}^{+\infty}b_kx^k$ hence $(1-x)^n\cdot\dfrac1{(1-x)^n}=1=\sum\limits_{k=0}^{+\infty}c_kx^k$ with $c_k=\sum\limits_{i=0}^ka_ib_{k-i}$ for every $k\geqslant0$. Since the series expansion of the function $x\mapsto 1$ is $1=1+0\cdot x+0\cdot x^2+0\cdot x^3+\cdots$, one gets $c_0=1$ and $c_k=0$ for every $k\geqslant1$.

  • 0
    let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/2809/discussion-between-steven-taschuk-and-didier-piau)2012-03-17
0

$\begin{align} \sum_i (-1)^i \binom{n}{i} D(n,k-i) &= \sum_i (-1)^i \binom{n}{i} \binom{n-1+k-i}{k-i} \\ &= (-1)^k \sum_i \binom{n}{i} \binom{-n}{k-i} \tag{1} \\ &= (-1)^k \binom{0}{k} \tag{2} \end{align}$ which is 1 if $k=0$ and 0 otherwise.

On step (1): I interpret the binomial coefficient $\binom{x}{j}$ as a polynomial in $x$ of degree $j$, via $ \binom{x}{j} = \frac1{j!} \prod_{i=0}^{j-1} (x-i) $ One can check that, under this convention, $\binom{-x}{j} = (-1)^j \binom{x+j-1}{j}$, which gives step (1).

Step (2) uses Vandermonde's convolution, which asserts $ \binom{n+m}{k} = \sum_i \binom{n}{i} \binom{m}{k-i} $ Often this is stated only for nonnegative integers $n$ and $m$; for such values it can be proved combinatorially. To extend it to real $m$, note that under the convention stated above, both sides are polynomials in $m$ of degree $k$, so the fact that they agree at all nonnegative integer values of $m$ implies that they agree for all real $m$. (It would be enough that they agree at $k+1$ distinct values.)

(The best source I know of for techniques like this is Graham, Knuth, and Patashnik's Concrete Mathematics.)