Approximating a recursively-defined function - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T17:07:45Z http://mathoverflow.net/feeds/question/34788 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34788/approximating-a-recursively-defined-function Approximating a recursively-defined function Robin Houston 2010-08-06T17:04:26Z 2010-08-06T19:09:43Z <p>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}^{+}$.</p> <p>So $f(1) = 1$, $f(2) = 3/4$, $f(3) = 35/72$, etc.</p> <p>(This function arises when calculating an upper bound for the worst-case behaviour of the first-fit algorithm for dynamic storage allocation.)</p> <p>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) &lt; 2/n$?</p> http://mathoverflow.net/questions/34788/approximating-a-recursively-defined-function/34791#34791 Answer by Daniel Krenn for Approximating a recursively-defined function Daniel Krenn 2010-08-06T18:19:22Z 2010-08-06T19:09:43Z <p>Rewriting the recursion yields $$1 = \sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1}.$$ By assuming $f(k)=\frac{1}{k \ln 2} (1+o(1))$ --- where the little o-Notation $o(1)$ simply means that it is smaller than every constant for large $k$ --- and inserting this, we get $$\sum\limits_{1\leq i \leq k} \frac{i\ f(i)}{k+i-1} = \frac{1}{\ln 2} \sum\limits_{1\leq i \leq k} \frac{1+o(1)}{k+i-1} = \frac{1+o(1)}{\ln 2} \left(\ln (2k-1)-\ln(k)\right) = \frac{1+o(1)}{\ln 2} \ln\left(2-\frac1k\right) \to 1$$ for $k\to\infty$. I used $\sum_{1\leq i \leq k} \frac1i = \ln k + \gamma + o(1)$. Therefore the assumtion holds asymptotically, since it fulfils the recursion.</p> <p>The bound $f(k)&lt;2/k$ follows from that --- at least, there is an $K$, such that for all $k\geq K$ the inequality $f(k)&lt;2/k$ holds.</p>