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).

  • $\begingroup$ Well, certainly we do get $f(x)\geq 1000x$ at some point, since at every stage we are multiplying the previous value by a number greater than $1$, and then adding more. $\endgroup$ – Arturo Magidin Feb 4 '11 at 4:30
  • $\begingroup$ The backstory of the problem is this: an ant is travelling along a string a 1 cm/sec and the string is extended by 1 kilometer at the end of every second. Assume uniform stretching and no general relativity, etc. Does he reach the end of the string? $\endgroup$ – eternalmatt Feb 4 '11 at 5:17

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$.

  • $\begingroup$ I would upvote this if I didn't have 6 rep. $\endgroup$ – eternalmatt Feb 4 '11 at 5:27

$$\frac{f(n)}{n}=\frac{f(n-1)}{n-1}+\frac{.01}{n}$$ Define $g(n)=100\frac{f(n)}{n}$ with $g(1)=1$ Then $g(n)=g(n-1)+\frac{1}{n}=\sum_{i=1}^{n}\frac{1}{i}=H_{n}$ where $H_n$ are the harmonic numbers. So we want $H_{n}\gt 1000$ so $n=\exp(1000-\gamma) \pm 1$ (cuz I took the limit of $H_n$ to be true at this point. It's probably right without the $\pm 1$)

  • $\begingroup$ Could you elaborate a little on Harmonic numbers and how you got n = exp(999−γ)? I'm just not extremely familiar with them. $\endgroup$ – eternalmatt Feb 4 '11 at 5:25
  • $\begingroup$ Take a look at en.wikipedia.org/wiki/Harmonic_number They are the sum of 1/n and are well approximated by the natural log + Euler's $\gamma$ $\endgroup$ – Ross Millikan Feb 4 '11 at 6:21
  • $\begingroup$ @Noah Stein: I realized I had an error of one position in the series and fixed it. $\endgroup$ – Ross Millikan Feb 4 '11 at 18:08

Well, it can be proved by induction that a "closer" form for that sequence is $f(n) = \frac{H_n}{100}$, where $H_n$ is the nth harmonic number. Since the harmonic series diverges, so does your function, which will grow logarithmically.

  • $\begingroup$ $\frac{H_n}{100}$ will never equal $1000n$, but this is not a problem because $f(n) = \frac{n\cdot H_n}{100}$, not $\frac{H_n}{100}$. $\endgroup$ – Noah Stein Feb 4 '11 at 12:20
  • $\begingroup$ Oh, you're right. I missed that factor. $\endgroup$ – Abel Feb 4 '11 at 18:37

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.