# Convergence of sequence: $f(n+1) = f(n) + \frac{f(n)^2}{n(n+1)}$

I am trying to work out a problem on some old analysis qual exam, and managed to reduce it to this question, but I can't seem to figure out this final step:

Consider the sequence defined by the recurrence relation $$f(n+1) = f(n) + \frac{f(n)^2}{n(n+1)}$$ with initial condition $f(1) = 1$. Does this sequence converge or diverge?

• You can try to take the closed form and analyze it... maybe more long but if you dont remember some theorem of analysis maybe easier after all xD – Masacroso Jul 22 '15 at 22:56
• the first thing to observe is the sequence is monotone increasing: $f(n+1) = f(n) + \frac{f(n)^2}{n(n+1)}\Leftrightarrow f(n+1)-f(n)=\frac{f(n)^2}{n(n+1)}>0$, but i have a hard time to show boundedness/un-boudedness – user190080 Jul 22 '15 at 23:20

We know that $\{ f(k) \}_{k=1}^{\infty}$ is monotone increasing. This means that the sequence either diverges to $+\infty$ or converges. In order to determine which option is the case, we do the following trick: First we write

$$f(k+1) - f(k) = \frac{f(k)^2}{k(k+1)} \leq \frac{f(k)f(k+1)}{k(k+1)}.$$

Dividing both sides by $f(k)f(k+1)$ and writing $g(k) = 1/f(k)$, we have

$$g(k) - g(k+1) \leq \frac{1}{k} - \frac{1}{k+1}. \tag{1}$$

This is the key inequality for our argument. One the one hand, summing this for $k = 1, \cdots, n-1$, we get

$$1 - g(n) \leq 1 - \frac{1}{n} \quad \Longrightarrow \quad \frac{1}{n} \leq g(n).$$

On the other hand, summing $\text{(1)}$ for $k = n, n+1, \cdots$ and denoting $g(\infty) = \lim g(n)$, we have

$$g(n) - g(\infty) \leq \frac{1}{n} \quad \Longrightarrow \quad g(n) \leq g(\infty) + \frac{1}{n}.$$

When $g(\infty) = 0$, these two inequalities become saturated, hence we obtain $g(n) = 1/n$ and $f(n) = n$. But this is absurd, since this does not satisfy our recurrence relation. Therefore $g(\infty) > 0$ and

$$\lim_{n\to\infty} f(n) = \frac{1}{g(\infty)} < \infty.$$

Addendum. We prove the following claim:

Claim. There exists $R > 0$ such that the sequence $\{f(n)\}$ diverges if $f(1) \geq R$. We also have $R \approx 1.61473$.

Let us consider a more general situation: for any $z \in \Bbb{C}%$, define $a_n = a_n(z)$ by

$$a_1 = z, \qquad a_{n+1} = a_n + \frac{a_n^2}{n(n+1)}. \tag{2}$$

If we define $R$ by

$$R := \sup \{ r > 0 : \lim_{n\to\infty} a_n (r) < \infty \} \in [0, +\infty],$$

then we know that $R \geq 1$ by the previous proof. Also it is easy to prove that $a_n (z)$ converges to an analytic function $a_{\infty}(z)$ on the disc $|z| < R$ which has singularity at $z = R$. In particular, $a_n(r)$ diverges if $r \geq R$. Now differentiating the recurrence relation (2) and iterating it infinitely, we obtain

$$a_{\infty}' = \prod_{k=1}^{\infty} \left( 1 + \frac{2a_k}{k(k+1)} \right). \tag{3}$$

Now if $0 < r < R$, then the technique above shows that

$$a_k \geq \frac{k a_{\infty}(r)}{k + a_{\infty}(r)}$$

Plugging this to (2) and writing $w = a_{\infty}(r)$ for brevity, we have

$$\frac{dw}{dr} \geq \prod_{k=1}^{\infty} \left( 1 + \frac{2w}{(k+1)(k+w)} \right)$$

Using the separation of variables technique, this gives a bound for $R$ as follows:

$$R \leq \int_{0}^{\infty} \prod_{k=1}^{\infty} \frac{k^2 + (w+1)k + w}{k^2 + (w+1)k + 3w} \, dw \approx 1.61473.$$

The sequence is monotone(given in comment by user190080), let $g(n)=5-\frac{25}{n}$, we have $f(18)<g(18)$ and if $f(n)<g(n)$, $f(n+1)<f(n)+\frac{25}{n(n+1)}<5-\frac{25}{n}+\frac{25}{n(n+1)}=5-\frac{25}{n+1}=g(n+1)$, by induction $f(n)$ is bounded above by 5 therefore converge. However I suggest trying to find a better upper bound $g(n)$ for similar purpose so you don't need to calculate 18 terms.

• nice idea to bound it by another sequence – user190080 Jul 22 '15 at 23:43
• Can you just use a limit to prove the boundness of $g$? – YoTengoUnLCD Jul 23 '15 at 0:09

We can answer this question in the same manner as this answer.

Since $f(1)=1$ and $$f(n+1)=f(n)+\frac{f(n)^2}{n(n+1)}\tag{1}$$ we have that $f(n)$ is increasing and inductively we have that $$1\le f(n)\le n\tag{2}$$ Furthermore, $(1)$ implies that \begin{align} &\left(\frac1{f(n+1)}-\frac1{n+1}\right)-\left(\frac1{f(n)}-\frac1n\right)\\ &=\left(\frac1n-\frac1{n+1}\right)-\left(\frac1{f(n)}-\frac{n(n+1)}{n(n+1)f(n)+f(n)^2}\right)\\ &=\frac1{n(n+1)}-\left(\frac{n(n+1)+f(n)}{n(n+1)f(n)+f(n)^2}-\frac{n(n+1)}{n(n+1)f(n)+f(n)^2}\right)\\ &=\frac1{n(n+1)}-\frac1{n(n+1)+f(n)}\\ &=\frac{f(n)}{n(n+1)(n(n+1)+f(n))}\\ &\ge\frac{f(n)}{n^2(n+1)(n+2)}\\ &\ge\frac1{n^2(n+1)(n+2)}\tag{3} \end{align} Since $$\sum_{n=1}^\infty\frac1{n^2(n+1)(n+2)}=\frac{\pi^2}{12}-\frac58\tag{4}$$ we have \begin{align} \frac1{f(n)} &\ge\frac1n+\sum_{k=1}^{n-1}\frac1{n^2(n+1)(n+2)}\\ &\ge\frac{\pi^2}{12}-\frac58\tag{5} \end{align} Therefore, $$f(n)\le\frac{24}{2\pi^2-15}\tag{6}$$ Since $f(n)$ is increasing and bounded above, it converges.