Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

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

share|improve this answer
    
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
1  
@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.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.