Generating Functions in Discrete Mathematics in Computer Science

Question

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\;$.

Answer 1

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".)

Answer 2

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)$.