I want to find the generating function of the following recurrence relation

$$ a_n = \binom{k}{n} $$

I already know that in the case of $a_n=\binom{n}{k}$, the generating function $A(x)$ can be given as

$$ \begin{align*} A(z)&=&\sum_{n=0}^{\infty}\binom{n}{k}x^n\\ &=&\frac{z^k}{(1-z)^{k+1}} \end{align*}$$

How do I do this in the case that I am choosing n element from k?


  • 1
    $\begingroup$ Unless $k$ varies as well, it will just be a polynomial (since $\binom{k}{n}=0$ for $n>k$). $\endgroup$ – Clayton May 1 '18 at 23:06
  • $\begingroup$ Well how did you obtain the generating function in the other case? Try examining the method used in that case and see how to modify it for this case. $\endgroup$ – Dave May 1 '18 at 23:06

$$G(x) = \sum_{n=0}^{\infty}\binom{k}{n}x^n\\ = \sum_{n=0}^{k}\binom{k}{n}x^n 1^{k-n}\\ =(1+x)^k$$


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.