Looking for a function $f$ such that $f(i)=2(f(i-1)+f(\lceil i/2\rceil))$

Question

I'm looking for a solution $f$ to the difference equation $$f(i)=2(f(i-1)+f(\lceil i/2\rceil))$$ with $f(2)=4$. Very grateful for any ideas.

PS. I've tried plotting the the initial values into "Sloan", but it doesn't seem to recognize the sequence.

Answer 1

Since $f$ is always positive, $f(i) \gt 2f(i-1)$ and so by induction $f(n) \gt 2^n$. $f(\lceil i/2\rceil)$ is then exponentially smaller than $f(i)$, so $2^n$ is the dominant term. Divide out $f$ by the exponential and define $g(n) = 2^{-n}f(n)$; then $g(i) = g(i-1) + 2^{1-\lfloor i/2\rfloor}g(\lceil i/2\rceil)$, with $g(2)=1$. It's easy to see by induction that $g(n) \lt n$ and in fact that $g(n) = O(n^\epsilon)$ for any $\epsilon$ (the differences for a series of $\Theta(n^\epsilon)$ are $\Theta(n^{\epsilon-1}) = {n^\epsilon\over n}$, which is eventually larger than $n^{\epsilon}\over2^\epsilon2^{n/2}$ for any $\epsilon$). In fact, the form of the series loosely suggests that $g(n)$ may be some exponentially damped constant, roughly $C+\Theta(2^{-kn})$ for some $k$ and $C$; you might try from that perspective...

Answer 2

For the asymptotic behavior, only the first term in the right hand side is important; Imagine that the series is growing rapidly -- as we will soon see this is true -- then the term $f(i/2)$ is much smaller than $f(i-1)$. The equation $$f(i) \sim 2 f(i-1)$$ can be solve easily and yields $$f(i) \sim c\, 2^i$$ where $c$ is some constant. Therefore $f(i) = \Theta(2^i)$.

Answer 3

By numerical methods I calculated the first 10000, and $f(n)$ converged very rapidly to $$C2^n$$ where $C=6.431946109729$. In other words, $$f(n)\sim 1.607986527432\cdot 2^{n+2}.$$ My hope was that if $C$ was a known constant, this would tell us more about the problem. Unfortunately, neither of the constants above appeared on the inverse symbolic calculator.