# What is a solution to the recurrence relation $f(n) = f(n-1) +f\Big(\left\lfloor \frac{n}{2} \right\rfloor\Big)$?

Let $$\mathbb{N}=\{1,2,3,\ldots\}$$. Find a closed form or an asymptotic form of $$f: \mathbb{N} \to \mathbb{N}$$, where $$f$$ satisfies $$f(1) = 1$$ and $$f(n) = f(n-1) + f\bigg(\left\lfloor \frac{n}{2} \right\rfloor\bigg)\,.$$

What is a closed-form solution to this recurrence relation?

Neither the Master theorem, nor its generalization, the Akra-Bazzi method, seem to be applicable.

• Is this your question? It wasn't clear what you wanted to me. I realized after making the edit. Do you want a closed form, or an asymptotic form? Jul 26 '20 at 15:10
• I was thinking of a closed form, but now that you say it, an asymptotic solution would be sufficient as well. Or even a decent lower bound. Really anything that gives some intuition about the growth rate of this function. Jul 26 '20 at 15:33
• I tried to see whether there is a nice analytic approximation, but then I encountered the differential equation $p'(x)=p\left(\dfrac{x}{2}\right)$, which seems to be quite difficult to solve. Jul 26 '20 at 15:35
• This is OEIS A033485, about which not much seems to be known. It’s half of OEIS A000123 (with first term omitted), about which a bit more seems to be available. Jul 26 '20 at 17:55