Proof that $(1-x)^n\cdot \left ( \frac{1}{1-x} \right )^n=1$

331 Views Asked by At

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$$

2

There are 2 best solutions below

9
On

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
On

$$\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.)