Formal power series question

Question

$$(1-t)^d \sum_{k = 0}^{\infty} \binom{d+k-1}{d-1} t^k = 1$$

How can this be proven? Thanks in advance.

Answer 1

Use $$\begin{align} (1-t)\sum_{k=0}^\infty{d+k-1\choose d-1}t^k&=\sum_{k=0}^\infty\left({d+k-1\choose d-1}-{d+k-2\choose d-1}\right)t^k\\&=\sum_{k=0}^\infty{d+k-2\choose d-2}t^k\end{align}$$ and $$ \sum_{k=0}^\infty{k\choose 0}t^k=\sum_{k=0}^\infty t^k=\frac1{1-t}$$

Answer 2

The number of ways you can color k identical objects with d colors is given by

$$\binom{d+k-1}{d-1}$$

To see this consider representing colorings as a string of the form oo|o|ooo|o|o|... where the "o" are the objects and the "|" are the separations between regions where the "o" get different colors. The number of different strings is then clearly given by the above binomial coefficient.

We can also tackle the problem using generating functions. If we denote the number of objects with the rth color as $n_r$, then since there are $k$ objects, we have that

$$\sum_{r=1}^{d} n_r = k$$

The number of solutions to this equations is then equal to the total number of colorings. But if we sum

$$\sum_{n_1,n_2,n_3\cdots n_d}x^{\sum_{r=1}^{d}n_r}$$

then the coefficient of $x^k$ is precisely equal to the number of solutions of the equation and is thus equal to the above binomial coefficient. It is easy to see that the summation factorizes and reduces to

$$\frac{1}{(1-x)^d}$$