2
$\begingroup$

I have been given a question that asks me to prove that $$\frac{1}{(1-x)^n}=1+\binom{1+n-1}{1}x+\binom{2+n-1}{2}x^2+\cdots+\binom{r+n-1}{r}x^r+\cdots$$ using a combinatorial proof. I know the equation can also be written as $$\biggr(\sum_{k=0}^\infty x^k\biggr)^n=\sum_{k=0}^\infty \binom{k+n-1}{k}x^k.$$ I really have troubles understanding problems that have infinite sums as combinatorial problems. We have been given the suggestion to write an integer solution problem and use it to solve the counting problem, but I have been staring at this problem and nothing is clicking. Any hints or tips would be amazing and greatly appreciated.

$\endgroup$
1
$\begingroup$

Just like how $$(1+x)^n=\sum_{k=0}^{\infty}\binom{n}{k}x^k$$ is the generating function for the number of sets of size $k$ drawn from $n$ symbols,

$$(1-x)^n=\sum_{k=0}^{\infty}\Big(\binom{n}{k}\Big)x^k$$ is the generating function for the number of multisets of size $k$ drawn from $n$ symbols.

The equality $$\Big(\binom{n}{k}\Big)=\binom{n+k-1}{k}$$ is proven by thinking of a multiset of size $k$ as $k$ "stars" in a row that have been separated by $n-1$ "bars"—"stars and bars".

$\endgroup$
1
$\begingroup$

Stars and bars. Since $\frac{1}{1-x}=1+x+x^2+x^3+\ldots$, the coefficient of $x^m$ in the Maclaurin series of $\frac{1}{(1-x)^n}$ equals the number of solutions of $a_1+a_2+\ldots+a_n=m$ with $a_j\in\mathbb{N}$, which is also the number of solutions of $b_1+b_2+\ldots+b_n=m+n$ with $b_k\in\mathbb{N}^+$. This is the number of ways for putting $n-1$ bars in the spaces between $m+n$ consecutive stars, i.e. $\binom{m+n-1}{n-1}=\binom{m+n-1}{m}$.

Summarizing: $$ \frac{1}{(1-x)^n} = \sum_{m\geq 0}\binom{m+n-1}{m} x^m.$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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