9
$\begingroup$

I'm working on a math/programming puzzle that involves an integer series defined as having a recurrence relating values $a(n)$ to $a(\lfloor\frac{n}{2}\rfloor)$ and $a(\lfloor\frac{n}{4}\rfloor)$. From the definition I've found this expression involving the series's generating function $G$:

$$G(x) = x + G(x^2)(3 + 2x) + G(x^4)(2 + 3x)(1 + x^2)$$

I'm hoping to find a closed form for $G$ which will give me insight on how to address the larger problem, but I haven't found a way to do that. I can sort of see how $G$ might be a ratio of polynomials, but I have not figured out how to find them.

$G$ grows more slowly than the generating function for Fibonacci, so it should have a reasonable range of convergence.

A value for $G$ can be calculated for any complex $n$th root of unity (by setting up a linear system along with all the other associated $n$th roots of unity), but I'm not sure it's useful to do this, or even if it's permitted to do this with this kind of formal power series. I'm also pretty sure $1$ and $-1$ are outside the range of convergence. But then again, it is a formal power series.

$$G(1) = 1 + G(1)(5) + G(1)(5)(2)\\ G(1) = -\frac1{14}$$

$$G(-1) = -1 + G(1)(1) + G(1)(-1)(2)\\ G(-1) = -1 - G(1) = -\frac{13}{14}$$

The even and odd portions of G can be distinguished.

$$G_\text{even}(x) = 3G(x^2) + 2(1+x^2)G(x^4)\\ G_\text{odd}(x) = x + 2xG(x^2) + 3x(1 + x^2)G(x^4)$$

$\endgroup$
3
  • $\begingroup$ Good question. Experiments with Maple says that $G=x+3x^2+2x^3+11x^4+9x^5+8x^6+7x^7+39x^8+\ldots$ $\endgroup$
    – Michael Galuza
    Commented Jun 26, 2015 at 17:30
  • $\begingroup$ @MichaelGaluza That matches what I know. $\endgroup$
    – NovaDenizen
    Commented Jun 26, 2015 at 17:37
  • 2
    $\begingroup$ $G(x)$ cannot be a ratio of polynoms. If it's true, $G(x)\sim x^n$ at $x\to\infty$ for some $n$; but you can see from definition that isn't possible. $\endgroup$
    – Michael Galuza
    Commented Jun 26, 2015 at 17:53

1 Answer 1

Reset to default
4
+75
$\begingroup$

If $G(x) = \sum_{j=0}^\infty a_n x^n$, I get $$ \eqalign{ a_{4k} &= 3 a_{2k} + 2 a_k\cr a_{4k+1} &= 2 a_{2k} + 3 a_k\cr a_{4k+2} &= 3 a_{2k+1} + 2 a_k\cr a_{4k+3} &= 2 a_{2k+1} + 3 a_k\cr} $$ In particular, $a_{2^m} = 3 a_{2^{m-1}} + 2 a_{2^{m-2}}$, and with $a_1 = 1$ and $a_2 = 3$, this implies $$ a_{2^m} = \left(-\dfrac{3\sqrt{17}}{34} + \dfrac{1}{2}\right) \left(\dfrac{3-\sqrt{17}}{2}\right)^m + \left(\dfrac{3\sqrt{17}}{34} + \dfrac{1}{2}\right) \left(\dfrac{3+\sqrt{17}}{2}\right)^m$$ It looks to me like $G$ will have radius of convergence $1$, and I very much suspect it will have a natural boundary at $|z|=1$.

$\endgroup$
3
  • $\begingroup$ In support of the last line: The functional equation in the problem above is strongly reminiscent of $f(x)=f(x^2)+x$, which satisfied by the lacunary function $f(x)=\sum_{n=1}^\infty x^{2^n}$. But that's essentially the canonical example of a function with natural boundary at $|z|=1$. $\endgroup$
    – Semiclassical
    Commented Jun 29, 2015 at 21:20
  • 1
    $\begingroup$ Thanks, but I already can calculate arbitrary $a_n$. I'm looking for a closed form of $G$. $\endgroup$
    – NovaDenizen
    Commented Jul 2, 2015 at 17:01
  • 1
    $\begingroup$ It's rather unlikely that there is a closed form. $\endgroup$
    – Robert Israel
    Commented Jul 2, 2015 at 17:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .