Problem with understanding generating functions.

Question

I am given generating functions $f(x)= \frac{x}{1-x}$ or $f(x)=\frac{1}{1+x^{2}}$ or $f(x)=\frac{1}{x^2-5x+6}$ and I am obliged to write sequence which are generated by this functions. What is the fastest algorithm to solve these problems? I have problem with even starting. I will be glad if anyone would be so nice to explain me algorithm to solve this kind of exercises or post any reference that is related with my problem.

Answer 1

Hint: $\frac{1}{1-x}=(1-x)^{-1}=\sum_{k=0}^{\infty} 1 \cdot x^k$, so the sequence this GF generates is $<1,1, \ldots>$

EDIT: 'in general' you need to represent the GF in the form $\sum_{k=0}^{\infty} a_k x^k$, and $\{ a_k \}$ is the sequence that this GF generates.

Answer 2

Hint: For ordinary generating function, you need to find the coefficient of $x^n$, so you need to find the power series expansion of these functions. See this technique.

Answer 3

In general given the ratio of two polynomials, apply partial fraction decomposition to the ratio so as to obtain a sum of terms that can be expanded as a binomial series, then collect the coefficients.

Answer 4

$$\frac{x}{1-x}=x\frac{1}{1-x}=x\sum_{n=0}^{\infty}x^n=\sum_{n=0}^{\infty}x^{n+1}=\sum_{n=1}^{\infty}x^{n}$$ $$\frac{1}{1+x^2}=\frac{1}{1-(-x^2)}=\sum_{n=0}^{\infty}(-x^2)^n=\sum_{n=0}^{\infty}(-1)^nx^{2n}$$

Answer 5

By the fundamental theorem of algebra, any real-valued polynomial can be factorised into real quadratics. Sometimes these quadratics can be factored further into linear binomials, and if not they are writeableas a sum of two squares.

Given a ratio of polynomials, $\frac{p(x)}{q(x)}$ (where we take the degree of $p$ to be less; if that is not the case then we can use polynomial division to make it the case), we can factor $q(x)$ into a product of linear terms and quadratics which are the sum of two squares. For now we assume the roots of $q$ are distinct, but the case of multiple roots can be dealt with.

We can then use partial fraction decomposition to write this as a sum of constants over linear terms, and linear terms over quadratic terms. These can be expressed as series using the geometric series expansion, viz: $$\frac{1}{1-x}=1+x+x^{2} +\ldots; \quad \frac{1}{1+x^{2}}=\frac{1}{1-(-x^{2})}=1-x^{2}+x^{4}-\ldots$$

With generating functions, we are looking to find the coefficient on $x^{n}$, which the method I've described above allows us to do. If you're unfamiliar with any of these techniques, let me know in a comment.