Generating Functions in Discrete Mathematics in Computer Science Hey Guys can anyone help me with the following question in Discrete Structures in Mathematics, relating generating functions
Find a closed form for the generating function for the sequence $\{a_n\}$, where
$$a_n=\binom{n+4}n$$
for $n=0,1,2,\dots\;$.
 A: So the generating function is, by definition
$$g(x):=\sum_{n \geq 0} \binom{n+4}{n} x^n = \sum_{n \geq 0} \binom{n+4}{4} x^n$$
using the binomial identity $\binom{x}{y}=\binom{x}{x-y}$ for natural numbers $0 \leq y \leq x$
We can rewrite this as $$g(x)=\sum_{n \geq 0} \frac{1}{4!}(n+1)(n+2)(n+3)(n+4) x^n.$$  Since $\frac{d}{dx}x^{n+1}=(n+1)x^n$, we find $$g(x)=\sum_{n \geq 0} \frac{1}{4!}(n+2)(n+3)(n+4) \frac{d}{dx} x^{n+1}$$ and if we keep doing this, we get $$g(x)=\sum_{n \geq 0} \frac{1}{4!}\frac{d^4}{dx^4} x^{n+4}.$$
We can rearrange this to obtain $$g(x)=\frac{1}{4!} \frac{d^4}{dx^4} \sum_{n \geq 0} x^{n+4}.$$
We know the generating function for $(1,1,1,\ldots,)$ is $$\frac{1}{(1-x)}=\sum_{n \geq 0} x^n,$$ which we substitute into the above to give $$g(x) = \frac{1}{4!} \frac{d^4}{dx^4} \frac{x^4}{(1-x)}=\frac{1}{4!}\frac{24}{(1-x)^5}=\frac{1}{(1-x)^5}.$$
(We can check this using Wolfram|Alpha: "Taylor series for 1/(1-x)^5".)
A: HINT: Note that
$$a_n=\binom{n+4}n=\frac1{4!}(n+4)(n+3)(n+2)(n+1)\;.$$
Thus, your generating function is
$$g(x)=\sum_{n\ge 0}a_nx^n=\frac1{24}\sum_{n\ge 0}(n+4)(n+3)(n+2)(n+1)x^n\;.$$


*

*The term $(n+4)(n+3)(n+2)(n+1)x^n$ is the fourth derivative of something rather simple; what?


Let me call the answer to that question $u_n(x)$; then your $g(x)$ is the fourth derivative of $\sum_{n\ge 0}u_n(x)$, and if you’ve correctly identified $u_n(x)$, the series $\sum_{n\ge 0}u_n(x)$ is one for which you already know a closed form. Differentiate that closed form four times with respect to $x$, and you’ll have your $g(x)$.
A: Note that:
$\begin{align*}
  \sum_{n \ge 0} \binom{n + 4}{n} z^n
    &= \sum_{n \ge 0} \binom{n + 4}{4} z^n \\
    &= \sum_{n \ge 0} (-1)^n \binom{-(4 + 1)}{n} z^n \\
    &= (1 - z)^{-5}
\end{align*}$
This because:
$\begin{equation*}\
  \dbinom{-r}{n}
    = (-1)^n \dbinom{n + r - 1}{r - 1}
\end{equation*}$
