2
$\begingroup$

If you are solving a problem and you encounter a generating function that you haven't seen before, is there a way to derive its underlying sequence representation?

For example I came across $\frac{1}{1+x}$ and had to look it up to see that it had coefficients $(-1)^n$, but what if I encounter something that doesn't have a lookup somewhere? Is there a way I can actually generate the coefficient representation from the generating function without needing to resort to internet lookups?

$\endgroup$
  • $\begingroup$ I think you mean sequence, not series. $\endgroup$ – Thomas Andrews Jan 9 '16 at 3:09
  • $\begingroup$ @ThomasAndrews What's the difference? $\endgroup$ – Sean Hill Jan 9 '16 at 3:13
  • $\begingroup$ A series is a sequence of the form $x_1,x_1+x_2,x_1+x_2+x_3,\dots$. If you are looking for the coefficients of a generating function, you are seeking a sequence which is not (in general) a series. $\endgroup$ – Thomas Andrews Jan 9 '16 at 3:15
  • $\begingroup$ @ThomasAndrews Oh ok, then yes I am looking for the sequence $\endgroup$ – Sean Hill Jan 9 '16 at 3:35
  • $\begingroup$ for what sequence do you want a generating function? $\endgroup$ – janmarqz Jan 9 '16 at 3:57
1
$\begingroup$

This math.SE question has a good example of the technique when you can decompose your function into partial fractions.

Edit: Using the example from your comment, $\dfrac{1-x+x^2}{1+3x-x^2} = -1-\dfrac{2x+2}{x^2-3x-1}$.

Solving $\dfrac{2x+2}{x^2-3x-1} = \dfrac{A}{x-\alpha}+\dfrac{B}{x-\beta}$ where $\alpha,\beta = \dfrac{3\pm\sqrt{13}}{2}$ yields $A=\dfrac{2\alpha+2}{\alpha-\beta},B=\dfrac{2\beta+2}{\beta-\alpha}$. Then $$-1-\dfrac{A}{x-\alpha}-\dfrac{B}{x-\beta} = -1+\dfrac{A}{\alpha}\dfrac{1}{1-\frac{1}{\alpha}x}+\dfrac{B}{\beta}\dfrac{1}{1-\frac{1}{\beta}x}=-1+\dfrac{A}{\alpha}\sum_{n=0}^\infty\frac{1}{\alpha^n}x^n+\dfrac{B}{\beta}\sum_{n=0}^\infty\frac{1}{\beta^n}x^n$$ $$=-1+\sum_{n=0}^\infty\left(\frac{A}{\alpha^{n+1}}+\frac{B}{\beta^{n+1}}\right)x^n$$ so the sequence is $a_0=1, a_{n\ge1} = \dfrac{A}{\alpha^{n+1}}+\dfrac{B}{\beta^{n+1}}=\dfrac{2^{n+1}}{\sqrt{13}}\left[\dfrac{5+\sqrt{13}}{(3+\sqrt{13})^{n+1}}-\dfrac{5-\sqrt{13}}{(3-\sqrt{13})^{n+1}}\right]$, which looks like it came from some fibonacci-like recurrence.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.