I'm looking for an asymptotic upper bound for the function f(x), which is recursively defined as follows: $$f(x) = f(x-1) + 2f\left(\lceil\frac{x}{2}\rceil \right)+2$$
with $f(1)=1$. I am pretty sure that $f(x) \in x^{O(log x)}$, and this is the best one can get, but I don't know how to prove it analytically. Any ideas?
Set $f(x)=\exp(g(\ln x))$. Then $$ f(x+1)-f(x)\approx f'(x)\approx f(x/2), $$ or $$ \exp(g(\ln x))\cdot\frac{g'(\ln x)}x\approx \exp(g(\ln x-\ln 2)). $$ Setting $y=\ln x$, $c=\ln 2$ and taking logarithm we get $$ y-\ln g'(y)\sim g(y)-g(y-c)\approx cg'(y). $$ This allows us to find $$ g(y)=\frac{y^2}{2c}+O(y\ln y), $$ hence $$ f(x)\approx \exp((\ln^2x)/(2c)(1+o(1)))=x^{(\ln x)/(2c)(1+o(1))}, $$ as required.
Since one may easily achieve some rough estimates for $f$ (and thus $g$), it is easy to see that all `$\approx$' signs hold up to a multiplicaive constant of the form $1+o(1)$. After taking the exponent at the last step, this results in such factor at the exponent.
Setting appropriate constants, one may work out some explicit (both upper and lower) bounds of the form $x^{O(\ln x)}$.
