Asymptotics to $f(2n) = f(2n-1) + \frac{f(2n-2)}{f(n)}$ or $ \ln(f(x)) = \int \frac{1}{f(x/2)} + C $?

Question

Consider the sequence $f(i)$ for integer $i>0$ :

$f(1) = f(2) = 1 $

$f(3) = 2$

define the remaining by

$f(2n) = f(2n-1) + \frac{f(2n-2)}{f(n)}$

$f(2n+1) = f(2n) + \frac{2n-1}{f(n)}$

How fast does this function grow ? What are the best asymptotics ?

How to answer such similar questions in general ?

The sequence reminds me of the similar equation

$$ f'(x) = \frac{f(x)}{f(x/2)} $$

Or equivalently :

$$ \ln(f(x)) = \int \frac{1}{f(x/2)} + C $$

And those look familiar but I could be wrong.

Also I know the solution to the equation $g'(x) = g(x/2)$ maybe that could help ?

Does this equation or very similar occur in the literature , for instance difference-differential equations or delay-differential equations ?

Answer 1

I don't know anything about how one should treat the problem in general, but here's some rather rough answer for someone who doesn't care much about proofs.

The following code in Mathematica allows one to experiment with this recurrence relation:

f[1] = 1;
f[2] = 1;
f[3] = 2;
f[n_Integer?EvenQ] := f[n] = f[n - 1] + N[f[n - 2]/f[n/2]];
f[n_Integer?OddQ] := f[n] = f[n - 1] + N[f[n - 2]/f[(n - 1)/2]];

Let's look at how the sequence grows:

Looks like it simply doubles, and indeed, it turns out to be a valid hypothesis:

Now that we know the answer, let's try to understand it. First af all, it's worth noticing that $\frac{f(2n-2)}{f(n)} \ll f(2n-1)$. Therefore, it certainely doesn't grow exponentially and our first estimate is that $f(n+1) \sim f(n) + \lambda (n)$, where $\lambda$ is something constant. But then $f(2n) \sim 2 f(n)$ and $\lambda \sim 2$