Finding A Particular generation function

Question

I am trying to find a generating function for the sequence $$a_n = \binom{n+3}{3}.$$

I can see that $\binom{n+3}{3} = \frac{(n+3)!}{(n)!3!} = \frac{(n+3)(n+2)(n+1)}{ 6}.$ This gives me a very direct template to work with for my generating function. I see that by the geometric series,

$$\sum_{i=0}^{\infty} x^i = \frac{1}{1-x}$$ $$\implies \sum_{i=0}^{\infty} x^{i+3} = \frac{x^3}{1-x},$$ which if we differentiate with respect to $x$, $$\implies \sum_{i=0}^{\infty} (i+3)x^{i+2} = \frac{(3-2x)x^2}{(1-x)^2}.$$

I am starting to realize that if I continue on this path, I will have significantly more difficult derivatives to consider as I approach dealing with the triple derivative of $\frac{x^2}{1-x}$. Is there potentially a simpler way to handle this problem in relation to the geometric series?

Answer 1

I would probably go this route:

Start with $$ A(x):=\sum_{n=0}^{\infty}\binom{n+3}{3}x^n=\frac{1}{6}\sum_{n=0}^{\infty}(n+1)(n+2)(n+3)x^n $$ Note that this looks an awful lot like $$ \begin{align*} A(x)&=\frac{1}{6}\sum_{n=0}^{\infty}(n+1)(n+2)(n+3)x^n\\ &=\frac{d}{dx}\left[C_1+\sum_{n=0}^{\infty}(n+2)(n+3)x^{n+1}\right]\\ &=\frac{d^2}{dx^2}\left[C_2+C_1x+\sum_{n=0}^{\infty}(n+3)x^{n+2}\right]\\ &=\frac{d^3}{dx^3}\left[C_3+C_2x+\frac{C_1x^2}{2}+\sum_{n=0}^{\infty}x^{n+3}\right], \end{align*} $$ for any choice of the constants $C_1,C_2,C_3$. We could take, for instance, $C_1=2$ and $C_2=C_3=1$, and re-index the sum, to say that $$ A(x)=\frac{d^3}{dx^3}\left[\sum_{n=0}^{\infty}x^n\right]=\frac{d^3}{dx^3}\left[\frac{1}{1-x}\right]. $$ But, of course, we can take derivatives of this easily enough: $$ \begin{align*} A(x)&=\frac{d^3}{dx^3}\left[\frac{1}{1-x}\right]=\frac{6}{(1-x)^4}. \end{align*} $$

Answer 2

Observe, formally we have \begin{align} \frac{6}{(1-x)^4}=\frac{d^3}{dx^3}\frac{1}{1-x} = \sum_{n=3}n(n-1)(n-2)x^{n-3} = \sum_{n=0}(n+3)(n+2)(n+1)x^n. \end{align} Hence \begin{align} \frac{1}{(1-x)^4} = \sum_{n=0}\binom{n+3}{3}x^n. \end{align}

Answer 3

Sometimes, you can solve a problem by generalization.

For $k \in \mathbb{N}$, consider following generalization of your OGF: $$g_k(x) = \sum_{n=0}^\infty \binom{n+k}{k} x^n$$

The OGF of these OGFs equals to:

$$ \sum_{k=0}^\infty g_k(x)t^k = \sum_{n=0}^\infty \sum_{k=0}^\infty \binom{n+k}{k} x^n t^k = \sum_{m=0}^\infty \sum_{k=0}^m \binom{m}{k}x^{m-k}t^k = \sum_{m=0}^\infty (x+t)^m\\ = \frac{1}{1-(x+t)} = \frac{1}{(1-x)(1-\frac{t}{1-x})} = \frac{1}{1-x}\sum_{k=0}^\infty \left(\frac{t}{1-x}\right)^k = \sum_{k=0}^\infty \frac{t^k}{(1-x)^{k+1}}$$ Compare coefficient of $t^k$ on both sides, we get

$$g_k(x) = \frac{1}{(1-x)^{k+1}}$$

In particular, the OGF you seek is $\displaystyle\;g_3(x) = \frac{1}{(1-x)^4}$.