Skip to main content
Add tag computer-science
Link
Robin Houston
  • 2.9k
  • 1
  • 30
  • 49
Source Link
Robin Houston
  • 2.9k
  • 1
  • 30
  • 49

Approximating a recursively-defined function

Let $$f(k) := \frac{2k-1}{k}\bigl(1-\sum\limits_{i\lt k}\frac{i\ f(i)}{k+i-1}\bigr)$$ for $k\in\mathbb{N}^{+}$.

So $f(1) = 1$, $f(2) = 3/4$, $f(3) = 35/72$, etc.

(This function arises when calculating an upper bound for the worst-case behaviour of the first-fit algorithm for dynamic storage allocation.)

Numerically it appears that $f(n)$ is approximately $1/(n\ ln(2))$. Can anyone give me any hints as to how one might try to prove that, or even a bound like $f(n) < 2/n$?