3
$\begingroup$

I am analyzing the average time complexity of some algorithm on some probabilistic model, and I've come to a doubly exponential sequence for which I cannot find corresponding generating function. I have been struggling with this for a few weeks now and I also briefly checked standard textbooks like [1,2,3], but had no luck.

It comes down to finding a closed form of $\sum_{i=0}^nx^{2^i}$, where $x$ is some probability, i.e. $x\in [0,1]$. I am also happy with just $\sum_{i\geq 0} x^{2^i}$. Set $F(x)=\sum_{i\geq 0} x^{2^i}$.

From [4] I found two properties, that don't help much (but might help you):

  • Obviously, $F(x^{2}) = F(x)-x$. (This corresponds to a shift of a sequence.)
  • $\frac{x}{1-x} = \sum_{i\geq 1; 2\nmid i}F(x^{i})$

I am surprised that there seems to be no easy answer, and I really hope that something useful will pop up here :)

EDIT: As pointed out in the comments, since $F(x)$ is transcendental for some values of $x$, there is no hope for it to be algebraic.

References:

[1] Aigner, Martin. A course in enumeration. Vol. 238. Springer Science & Business Media, 2007.

[2] Wilf, Herbert S. generatingfunctionology. Elsevier, 2013.

[3] Cameron, Peter J. Notes on counting. PJ Cameron, 2010.

[4] mjqxxxx (https://math.stackexchange.com/users/5546/mjqxxxx), What is known about doubly exponential series?, URL (version: 2014-01-20): https://math.stackexchange.com/q/645573

Improve this question
$\endgroup$
6
  • $\begingroup$ maybe $F(p,x):=\sum_{i\ge0} p^{2^i}x^i$ allows more relations? $\endgroup$
    – Pietro Majer
    Commented Feb 9, 2015 at 15:36
  • 1
    $\begingroup$ The Wikipedia entry on lacunary function says Weierstrauss looked at that function: en.wikipedia.org/wiki/Lacunary_function. What do you mean by solving it? That many particular values of this function are transcendental has been proved. $\endgroup$
    – Douglas Zare
    Commented Feb 9, 2015 at 17:47
  • $\begingroup$ By solving it, I mean expressing $F(x)$ in a closed form; without the $\sum$ symbol (I then want to derive and further change it). Thank you for very insightful wiki-link! It's good to know when to stop pushing calculations in some direction. $\endgroup$
    – Matjaž Krnc
    Commented Feb 9, 2015 at 21:11
  • 2
    $\begingroup$ There is no closed form for this $F(x)$. $\endgroup$
    – Gerry Myerson
    Commented Feb 9, 2015 at 22:18
  • 1
    $\begingroup$ Not only "algebraic". Any "explicit formula" in any minimally decent sense of this word defines a function that can be analytically continued along almost every path on the complex plane while $F$ has the unit circle as its natural boundary. $\endgroup$
    – fedja
    Commented Feb 14, 2015 at 0:06

0

Reset to default

You must log in to answer this question.