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.

  • $\begingroup$ 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? $\endgroup$ Jul 26 '20 at 15:10
  • $\begingroup$ 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. $\endgroup$ Jul 26 '20 at 15:33
  • $\begingroup$ 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. $\endgroup$ Jul 26 '20 at 15:35
  • 2
    $\begingroup$ 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. $\endgroup$ Jul 26 '20 at 17:55

Your Answer

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

Browse other questions tagged or ask your own question.