8
$\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$
  • $\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 Jun 26 '15 at 17:30
  • $\begingroup$ @MichaelGaluza That matches what I know. $\endgroup$ – NovaDenizen Jun 26 '15 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 Jun 26 '15 at 17:53
3
+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$
  • $\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 Jun 29 '15 at 21:20
  • $\begingroup$ Thanks, but I already can calculate arbitrary $a_n$. I'm looking for a closed form of $G$. $\endgroup$ – NovaDenizen Jul 2 '15 at 17:01
  • $\begingroup$ It's rather unlikely that there is a closed form. $\endgroup$ – Robert Israel Jul 2 '15 at 17:44

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.