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.
  • $\begingroup$ 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? $\endgroup$ – Demi Townson Apr 16 '18 at 12:25
  • $\begingroup$ I have added a sketch of the proof by induction. If it is not enough I would post the complete version. $\endgroup$ – user Apr 16 '18 at 12:44
  • $\begingroup$ 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. $\endgroup$ – Demi Townson Apr 17 '18 at 11:44
  • $\begingroup$ @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)$. $\endgroup$ – user Apr 17 '18 at 13:18

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.