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
    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.2012-03-18
  • 0
    @Dan: I think the idea is just to verify that a direct proof is possible.2012-03-19
  • 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
    Fine, but why does $\sum_{i=0}^k(-1)^i\binom{n}{i}D(n,k-i))=0$2012-01-19
  • 0
    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$).2012-01-19
  • 0
    @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$.2012-03-17
  • 1
    @StevenTaschuk: Not. At. All.2012-03-17
  • 0
    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.)2012-03-17
  • 0
    @StevenTaschuk: Please make up your mind... First, you complain that I prove $\sum_i(-1)^i{n\choose i}D(n,k-i)=0$ $(1)$ implies $(1-x)^n1/(1-x)^n=1$ $(2)$ instead of proving $(1)$, then you complain that I prove $(1)$ instead of proving $(2)$. Now, I am confused... :-) But I agree the question is worded oddly. I sticked to the question in the post (how to deduce $(1)$ from $(2)$) rather than to the rather absurd one in the title (how to show $(2)$). Let me suggest we now let the (until now, silent) OP speak for themselves instead of putting words in their mouth.2012-03-17
  • 0
    It should not surprise you that when you amplify your answer I discover that my guesses about what you meant are wrong and have to revise my complaint. I did not say that the question is worded oddly. I do agree that it would be best to hear from the OP. [Edit: And I do not agree that the question in the title is absurd, given the amplification in the text, and I suspect this is our fundamental disagreement.]2012-03-17
  • 0
    @StevenTaschuk: Your logic is a little difficult to follow... First you state that the OP is asking for a proof of (1) and that I am not providing it, then you complain that I prove (1) (the question by the OP being unchanged). O well.2012-03-17
  • 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.)