[Math] Converting recursive function to closed form

algorithmspuzzlerecurrence-relations

My professor gave us a puzzle problem that we discussed in class that I could elaborate on if requested. But I interpreted the puzzle and formed a recursive function to model it which is as follows:
$$f(n) = \frac{n f(n-1)}{n – 1} + .01 \hspace{1cm} \textrm{where } f(1) = .01\text{ and } n\in\mathbb{N}.$$

The question that is asked is when (if ever) does $f(x) = 1000x$. About half of the students concluded that it eventually will equal (they didn't have the formula I made) and that x would be near infinity.

My personal question is, can the function be reduced so that it isn't recursive? And so that it doesn't need to be solved by brute force computer algorithm (which would be about 3 lines of code).

Best Answer

If you define $g(n) = \frac{f(n)}{n}$ then your expression is $g(n) = g(n-1) + \frac{0.01}{n}$ and $g(0) = 0$. So $g(n) = 0.01\sum_{i=1}^n \frac{1}{n} = 0.01 h(n)$ where $h(n)$ is the $n^{\text{th}}$ harmonic number. Therefore $f(n) = 0.01n \cdot h(n)$. I think this is about as closed of a form as you're going to get.

Since the sequence $h(n)$ diverges, you will eventually get $h(n)\geq 100000$ so $g(n) \geq 1000$, which means $f(n)\geq 1000n$.

Related Question