Find the n-th number from the generating function

Question

Is there any way to find the n-th number in the series, by knowing it's genereting function.

For example, I found that the closed form solution for a generating function $\displaystyle\frac{(1+x)^2}{(1-x)^3}$ can be expressed as $2n^2 + 2n + 1$.

I am interested how can I derive similar formula $\displaystyle\frac{(1+x)^5}{(1-x)^6}$.

Answer 1

In other words, you want to find the coefficient of $x^n$ in the Maclaurin series for the function $$f(x)=\frac{(1+x)^5}{(1-x)^6}=(1+x)^5(1-x)^{-6}.$$ To do that, first expand each factor using the binomial formula $$(1+u)^m=\sum_{n=1}^\infty\binom mnu^n$$ and then multiply the two binomial series together using $$\left(\sum_{n=0}^\infty a_nx^n\right)\cdot\left(\sum_{n=0}^\infty b_nx^n\right)=\sum_{n=0}^\infty c_nx^n\text{ where }c_n=a_0b_n+a_1b_{n-1}+\cdots+a_nb_0.$$ For your function $$f(x)=(1+x)^5(1-x)^{-6}$$ I get $$\sum_{k=0}^5\binom5k\binom{n+5-k}5$$ as the coefficent of $x^n$. For the function $(1+x)^2(1-x)^{-3}$ the corresponding formula is $$\sum_{k=0}^2\binom2k\binom{n+2-k}2=\binom{n+2}2+2\binom{n+1}2+\binom n2=2n^2+2n+1.$$

Answer 2

Yes, yours $n$-th numbers are called the Hilbert polynomials or quasi-polynomials. See details in Chapter 4 of the book:

R. Stanley, Enumerative combinatorics. Vol. 1., Cambridge Studies in Advanced Mathematics. 49. Cambridge: Cambridge University Press.

The following theorem ( in some corrected form) holds

Theorem. Let \begin{gather*} \frac{R(z)}{Q(z)}=H(0)+H(1)z+H(2)z^2+\cdots+H(n)z^n+\cdots, \end{gather*} and the polynomials $R(z),Q(z),$ $\deg R(z) < \deg Q(z)$ are coprime and let $\lambda_1, \lambda_2, \ldots \lambda_r$ are the roots of the denominator $Q(z)$ with the multiplicities $k_1,k_2, \ldots, k_r.$ Then the Hilbert polynomials $H(n)$ has the form $$ \mathcal{H}(n)=\tau_{k_1}(n)\lambda_1^{k_1}+\tau_{k_2}(n)\lambda_1^{k_2}+\cdots+\tau_{k_r}(n)\lambda_1^{k_r}, n=0,1,2,\ldots, $$ here $\tau_{k_i}(n)$ is a polynomial of $n$ with rational coefficients of degree $ \leq k_i-1.$

Answer 3

My approach has been extremely empirical; so, please, forgive me for the lack of rigor !

What I first did was to develop as Taylor series (at $x=0$) to get $$\frac{(1+x)^5}{(1-x)^6}=1+11 x+61 x^2+231 x^3+681 x^4+1683 x^5+3653 x^6+7183 x^7+13073 x^8+22363 x^9+36365 x^{10}+O\left(x^{11}\right)$$ in which the coefficients are those given in both's answer.

I then reported the numbers on a graph and noticed a perfect fit using a polynomial of degree $5$ $$a_n=\frac{1}{15} \left(4 n^5+10 n^4+40 n^3+50 n^2+46 n+15\right)$$ ... and all of that to find later that this is sequence $A001847$ at $OEIS$ !!