I'm trying to see why the equation $(1-t)^{-d}= \Sigma_{k=0}^\infty {d+k-1 \choose d-1} t^k$ holds in the power series ring $\mathbb{Z}[[t]]$. I assume it's a counting argument about the number of ways to pick $k$ objects from $d$ barrels but I can't really see it. Any help would be greatly appreciated. This formula is used on page 117 of Atiyah Macdonald, btw. Thanks!
$(1-t)^{-d}= \Sigma_{k=0}^\infty {d+k-1 \choose d-1} t^k$?
3 Answers
Start with $ \frac1{1-t}=1+t+t^2+t^3+\cdots=\sum_{k=0}^\infty t^k. $ Differentiate both sides (w.r.t. $t$) $(d-1)$ times. Divide by $(d-1)!$.
-
0You can justify the validity of differentiating both sides by e.g. the uniqueness of power series result from calculus. – 2012-09-14
If you want the counting argument:
$(1-t)^{-d} = (1 + t + t^2 + ...)^d$
so a contribution to the $t^k$ term in the product comes from choosing terms $t^{a_1}, t^{a_2}, \dots, t^{a_d}$ in the various factors such that $a_1 + a_2 + \cdots a_d = k$. A solution to this equation, with each $a_i \geq 0$, can be encoded by a string of dashes and dots, where you write $a_1$ dashes, then a dot, $a_2$ dashes, a dot, ..., a dot, $a_d$ dashes. (E.g. $3 + 0 + 1 + 2 = 6$ produces $--- \cdot \cdot- \cdot --$.) Coversely, such a string determines a solution.
Therefore, the coefficient of $t^k$ is the number of such solutions, which is the number of strings of length $d - 1 + k$ containing $k$ dashes and $d-1$ dots, yielding the desired result.
-
0Just saw this. Thanks Michael. This is what I was hoping for. – 2012-09-18
I think you should see this identity as an extension of the binomial theorem to negative exponents: the binomial coefficient $\binom{d+k-1}{d-1}=\binom{d+k-1}k$ (which counts the $k$-multisets chosen out of $d$) is often written in terms of a binomial coeffcient with negative upper index: $ (-1)^k\binom{d+k-1}k=\binom{-d}k $ (you may take this as definition of $\binom{-d}k$, or easily prove it if you define $\binom nk=\frac{n(n-1)\cdots(n-k+1)}{k!}$ for any $n$, and $k\in\mathbf N$). The most basic thing that remains valid with this relation $\binom n{k-1}+\binom nk=\binom {n+1}k$ for $k>0$, as you can easily verify.
Your identity then becomes $ (1-t)^n=\sum_{k\geq0}\binom nk(-t)^k $ for $n=-d$.
While this just amounts to restating, the question differently, it suggest a proof by induction, just as you would probably do to prove the usual binomial theorem. The difference is that now decreasing induction starting at $n=0$ (for which the reformulated statement is true) is called for. So suppose $n<0$ and the result proved for $n+1$. Multiplying by the RHS $(1-t)$ one gets $ (1-t) \sum_{k\geq0}\binom nk(-t)^k =1(-t)^0+\sum_{k>0}(\binom n{k-1}+\binom nk)(-t)^k =\sum_{k\geq0}\binom {n+1}k(-t)^k = (1-t)^{n+1} $ by the induction hypothesis. Now divide both sides by $(1-t)$.
A small note, the original equation in the question does not hold for $d=0$, at least not with the usual convention for binomial coefficients with negative integer lower index (which is to take them $0$ always): the applied equation $\binom{d+k-1}{d-1}=\binom{d+k-1}k$ then fails for $d=0=k$. More generally this symmetry is no longer valid when binomial coefficients are extended to allow negative indices. For this reason I would prefer stating the relation with $\binom{d+k-1}k$ instead of $\binom{d+k-1}{d-1}$ if you insist on avoiding binomial coefficients with negative indices.
-
0Thanks Marc. Very illuminating – 2012-09-18