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?

  • $\begingroup$ 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 $\endgroup$ – Masacroso Jul 22 '15 at 22:56
  • 1
    $\begingroup$ 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 $\endgroup$ – 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.

  • $\begingroup$ nice idea to bound it by another sequence $\endgroup$ – user190080 Jul 22 '15 at 23:43
  • $\begingroup$ Can you just use a limit to prove the boundness of $g$? $\endgroup$ – 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.


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.