# Proof of a generating functions formula

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.

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.
• Thank you! This may be a silly question, but using the method of proof by induction as suggested, how would I link that back to the original equation? – Demi Townson Apr 16 '18 at 12:25
• I have added a sketch of the proof by induction. If it is not enough I would post the complete version. – user Apr 16 '18 at 12:44
• Again thank you. I agree, 1. is obvious, however I'm struggling with how to get to S(k+1)... I can see a general idea but explicitly I'm not sure I understand. Any help you can provide is much appreciated. – Demi Townson Apr 17 '18 at 11:44
• @DemiTownson $S(k):=\sum_{i=0}^\infty \binom{k+i-1}{i}x^i \Rightarrow \sum_{i=0}^\infty \binom{k+i}{i}x^i=\sum_{i=0}^\infty \binom{(k+1)+i-1}{i}x^i \equiv S(k+1)$. – user Apr 17 '18 at 13:18