0
$\begingroup$

Given a sequence of natural numbers $(c_n)_{n \in \mathbb{N_0}}$ that are stored in a generating function $$P(x) := \sum_{n=0}^{\infty} c_n x^n.$$

In the case that we can compute a closed form of $P(x)$, we can often recompute the $c_n$ up to a given bound using Taylor expansion, e.g. $P(x) = \frac{1}{1-x}$ gives $c_n = 1$ for all $n$.

However, generating functions might also be given as continued fractions $$P(x) = p_0(x) + \frac{1}{p_1(x) + \frac{1}{p_2(x) + \frac{1}{\ldots}}}$$ where the $p_i$ are polynomials in $x$. My question now is:

How to recompute the $c_n$ up to some bound $N \in \mathbb{N}_0$, given the sequence $(p_i)_{i \in \mathbb{N}_0}$?

Of course we assume that no closed form for the continued fraction is known, for example the $p_i$ might be the output of some algorithm and thus we only know finitely many of them.

If someone could furthermore point me towards some good literature on the topic, that would help a lot.

edit: As this seems to be not so easy, I will also give the special case I'm currently interested in. Here, we have $p_i \in \mathbb{Z}[t,z]$ and want to expand $P(t,z)$ with respect to powers of $z$, that is the $c_n$ are not natural numbers but rather polynomials in $t$ (still, that should not make a difference). The sequence in this case will be $p_0 = 0$, $p_1 = -z$, $p_2 = -tz$, $p_3 = -2tz$, $p_4 = -2t^2z$, $p_5 = -3t^2z$, $p_6 = -3p^3z$, etc., so you first increase the coefficient, then the power of $t$. In closed form this would be $$p_n = - \left\lfloor \frac{n+1}{2}\right\rfloor t^{\left\lfloor \frac{n}{2}\right\rfloor}z.$$ Thus all $p_i$ are linear in $z$, the variable taking the place of the $x$ above (no idea if that helps...).

$\endgroup$
  • $\begingroup$ I think you mean $P(x)=\tfrac{1}{1-x}$ in the example you gave. Based on an extremely limited background, and staring at the expressions for the convergents, I doubt this can be done with simple continued fractions, excluding very specific cases like rational functions. You might have more luck with generalized continued fractions (e.g., en.wikipedia.org/wiki/Gauss%27s_continued_fraction). I would love to be shown incorrect on this as I think this would be a fascinating intersection of fields. $\endgroup$ – adfriedman May 2 '17 at 11:51
  • $\begingroup$ Yes of course I meant $1-x$, thanks. I added the special case I currently want to compute, maybe at least in this special case there is something to be done... $\endgroup$ – Dirk May 2 '17 at 13:24

Your Answer

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

Browse other questions tagged or ask your own question.