5
$\begingroup$

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.

  • 3
    Are you only interested in the asymptotics for $i\to\infty$? A closed form expression seems to be unlikely...2011-04-07
  • 0
    If asymptotics are OK, the last term drops away fairly quickly and it just grows like 2^n. At i=40, it is 6.4319*2^40.2011-04-07
  • 1
    I agree that a closed-form solution is unlikely. Numerically one gets $f(i) \sim 6.4319461097 \times 2^i$. This seems like what one would expect but I have no idea where that constant comes from. One strategy for guessing a closed-form solution would be to try to divide out the largest power of 2 dividing each $f(i)$, but even that leaves you with some pretty big numbers.2011-04-07
  • 1
    @Michael Lugo: the constant has to come from the initial condition as the difference equation is linear.2011-04-07
  • 0
    @Fabian: I know that. But that just reduces the question to where one-fourth of my constant comes from.2011-04-07
  • 0
    @Michael Lugo: the constant in $f(n)=c 2^n$ is picked up at the first few steps (where the asymptotics does not hold).2011-04-07

3 Answers 3

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

4

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.

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