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

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

-
Could someone please explain to me why this requires a proof? Surely $(a)^{n} (b)^{n} \equiv (ab)^{n}$, so if $a=1-x$ and $b=\frac {1}{1-x}, ab=1$ for all x? Apologies if I just don't understand. –  Daniel Littlewood Mar 18 '12 at 16:20
@Dan: I think the idea is just to verify that a direct proof is possible. –  Qiaochu Yuan Mar 19 '12 at 5:39
Satisfied by an answer below? –  Did Jun 17 '12 at 6:44

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

-
Fine, but why does $\sum_{i=0}^k(-1)^i\binom{n}{i}D(n,k-i))=0$ –  Robert S. Barnes Jan 19 '12 at 11:08
You might recognize in your situation the product of an $a$-series by a $b$-series and conclude that the conclusion you are after follows from the fact that $c_k=0$ for every $k\geqslant1$ (by the way, the sum you are interested in is not $0$ when $k=0$). –  Did Jan 19 '12 at 11:13
@DidierPiau , it seems like you're explaining why the identity in the title of the question would follow from $\sum_i (-1)^i \binom{n}{i} D(n,k-i) = 0$, but the OP has asked how to prove that $\sum_i (-1)^i \binom{n}{i} D(n,k-i) = 0$. –  Steven Taschuk Mar 17 '12 at 16:14
@StevenTaschuk: Not. At. All. –  Did Mar 17 '12 at 16:30
Thanks for amplifying your explanation. But I don't understand how it addresses my concern. The first thing the OP says is "as part of a proof that $(1-x)^n (1/(1-x))^n = 1$", but then you use this fact in your answer. (I think it probable that the OP is as confused about your answer as I am.) –  Steven Taschuk Mar 17 '12 at 16:35

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

-