Power series with stars and bars coefficient How is the following identity derived, and how is it related to the stars and bars problem here?
$(1-x)^{-n} = \displaystyle \sum_{r=0}^{\infty} \binom{n+r-1}{n-1} x^r$
I saw this identity in the forum here without justification given.
 A: We have $$(1-x)^{-n} = \left( \sum_{k \geq 0} x^k\right)^n$$
The coefficient of $x^r$ here is the number of ordered $n$ tuples of non negative integers which sums to $r$, which by the stars and bars problem is $\binom{n+r-1}{n-1}$
A: From geometric series, we know that
$$\frac{1}{1-x} = 1 + x + x^2 + x^3 + \dots$$
You can see this by using a telescoping series or any other number of standard techniques.
What we want is an expression for this, raised to the $n$'th power. I.e.,
\begin{align}
(1-x)^{-n} &= \underbrace{(1 + x + x^2 + x^3 + \dots) \cdot (1 + x + x^2 + x^3 + \dots) \cdot \dots \cdot (1 + x + x^2 + x^3 + \dots)}_{n~\text{times}} \\
&= c_0 x^0 + c_1 x^1 + c_2 x^2 + c_3 x^3 + \dots,
\end{align}
where the coefficients $c_r$ are found by multiplying out these infinite series up to a given order and collecting terms. (See Cauchy product)


*

*Zeroth order terms ($x^0=1$) can only be created by choosing the $1$ term from each of these multiplicands within the product, so $c_0=1$.

*First order terms ($x^1$) can be created by choosing $x$ from one of the multiplicands, and ones from the rest. Since there are $n$ multiplicands, there are $n$ possible choices, so $c_1 = n$.

*Second order terms ($x^2$) can be created by either choosing two $x^1$'s from two diferent multiplicands, or by choosing one $x^2$ from one of the multiplicands.
More generally, for the $r$'th coefficient, $c_r$, we have $r$ copies of $x$, and distribute them into the $n$ multiplicands. If we distribute, say, 3 copies of $x$ into the second bin, that means we are considering a term associated with choosing $x^3$ from the second multiplicand. Each way of distributing these $r$ copies of $x$ corresponds to a distinct term in the series when multiplied out.
But the number of ways to distribute $r$ items into $n$ bins is precisely the complicated choosing formula in the original post, from which the formula follows.
