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.

$\endgroup$
  • 3
    $\begingroup$ Are you only interested in the asymptotics for $i\to\infty$? A closed form expression seems to be unlikely... $\endgroup$ – Fabian Apr 7 '11 at 21:38
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Apr 7 '11 at 22:00
  • 1
    $\begingroup$ 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. $\endgroup$ – Michael Lugo Apr 7 '11 at 22:03
  • 1
    $\begingroup$ @Michael Lugo: the constant has to come from the initial condition as the difference equation is linear. $\endgroup$ – Fabian Apr 7 '11 at 22:09
  • $\begingroup$ @Fabian: I know that. But that just reduces the question to where one-fourth of my constant comes from. $\endgroup$ – Michael Lugo Apr 7 '11 at 22:14
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.