Proof of a generating functions formula

Question

I recently found a formula to help find a sequence given a generating function:

$(\frac{1}{1-x})^k=\sum_{n=0}^{\infty}\binom{n+k-1}{n}x^n, k \in \mathbb{N}$

I just wondered if there was a known proof for this, or if anyone knows of a way to prove it.

Answer 1

The formula is nothing else as a generalization of binomial theorem on negative $k$ with: $$ \binom{-k}{i}\equiv(-1)^i\binom{k+i-1}{i}. $$

Alternatively it can be proved by induction over $k$.

A sketch of the proof by induction:

1. Define $S(k)=\sum_{i=0}^\infty\binom{k+i-1}{i}x^i$. Introduce induction hypothesis (I.H.): $S(k)=\frac{1}{(1-x)^k}$.
2. Consider the case $k=1$ (hint: geometric series).
3. Assume I.H. valid for $k$. Use $\binom{k+i}{i}=\binom{k+i-1}{i}+\binom{k+i-1}{i-1}.$ Arrive at $S(k+1)=S(k)+xS(k+1)$. Make a conclusion.