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.
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.
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...
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.
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)$.