1

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.

Marcin Majewski
  • 487
  • 3
    You just need to know the formula for a geometric series: $\sum_{n \geq 0} x^n = \frac{1}{1-x}$. In the second one, replace $x$ with $-x^2$, i.e., $\frac{1}{1 + x^2} = \frac{1}{1 - (-x^2)}$. For the last, factor and then use partial fractions. – Viktor Vaughn Jan 24 '14 at 22:43
  • 1
    $\large{\frac{1}{x^2-5x+6}=\frac{1}{x-3}-\frac{1}{x-2}=\frac{-1/3}{1-(x/3)}- \frac{-1/2}{1-(x/2)}} $ – K. Rmth Jan 24 '14 at 22:47
  • @SpamIAm So for $\sum_{n \geq 0} x^n = \frac{1}{1-x}$ I got the sequence $a_{n}=1$ ? – Marcin Majewski Jan 24 '14 at 23:11
  • experiment with Taylor series, with a "robot" like [ http://www.wolframalpha.com/input/?i=series+2%E2%88%9A%28t%2F%28t-1%29%29arctan%28%E2%88%9A%28t%2F%28t-1%29%29%29 ] – janmarqz Jan 24 '14 at 23:16
  • 1
    @MarcinMajewski Yes, that's right, just as Alex stated in his answer below. – Viktor Vaughn Jan 24 '14 at 23:22
  • @K.Rmth So I find formula for sequence $\large\frac{-1/3}{1-(x/3)}$ and for $\frac{-1/2}{1-(x/2)}$ and then subtract this formulas and I am done? – Marcin Majewski Jan 24 '14 at 23:29
  • 1
    @MarcinMajewski Yes, resulting in ${\large{\frac{1}{x^2-5x+6}=\frac{1}{x-3}-\frac{1}{x-2}=\frac{-1/3}{1-(x/3)}- \frac{-1/2}{1-(x/2)}}}={-1\over 3}\sum_{n=0}^{\infty} ({x\over 3})^n+{1\over 2}\sum_{n=0}^{\infty} ({x\over 2})^n$ – K. Rmth Jan 26 '14 at 20:17

5 Answers5

2

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.

preferred_anon
  • 17,121
  • I understand what you try to explain me. But I am somehow confused. $\frac{1}{1-x}=1+x+x^{2} +\ldots;$ You write this but the task was to find a sequence for example : $a_{n}=\frac{-1}{3^{n}}$ How to achive that? I am not familiar with this method. How to find this coefficient of $x^{n}$ ? I will be glad if you could elaborate and help me on this topic. – Marcin Majewski Jan 24 '14 at 23:01
  • Are you saying you want to find a generating function which generates $a_{n}=\frac{-1}{3^{n}}$? That would just be a geometric series. – preferred_anon Jan 24 '14 at 23:39
1

$$\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}$$

Adi Dani
  • 16,949
0

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.

Alex
  • 19,262
0

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.

Community
  • 1
Mhenni Benghorbal
  • 47,431
0

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.

Ethan Splaver
  • 10,613