I am hoping to obtain a closed-form solution or an asymptotic result for the recurrence relation


Any help would be very much appreciated!

  • $\begingroup$ Do you have any indication that such a closed form exists, or just hoping? $\endgroup$ – AlexanderJ93 Sep 13 '18 at 18:40
  • 1
    $\begingroup$ I have no indication that a closed-form expression is possible, but an asymptotic result in the limit of large n seems likely. A plot seems to suggest that the difference y[n+1]-y[n] decays hyperbolically in n. $\endgroup$ – Alex Sep 13 '18 at 18:58

I'm going to assume that $a, b, y_0$ are all positive.

From $y_{n+1} =y_n+a+\frac{b}{y_n+a} $ it follows that $y_{n+1}-y_n =a+\frac{b}{y_n+a} $ so that $y_n \gt na+y_0 $. Therefore $y_{n+1}-y_n \lt a+\frac{b}{(n+1)a+y_0} $.

Summing, $y_{n}-y_0 \lt na+b\sum_{k=0}^{n-1} \frac1{(n+1)a+y_0} \lt na+\frac{b}{a}(\ln(n)+c) $ so $y_n \lt na+\frac{b}{a}\ln(n)+d $ where $d$ is a computable constant.

From this lower bound, we get

$\begin{array}\\ y_{n+1}-y_n &\gt a+\frac{b}{na+\frac{b}{a}\ln(n)+d+a}\\ &= a+\frac{b}{(n+1)a+(b/a)\ln(n)+d}\\ &= a+\frac{b}{(n+1)a}\frac1{1+\frac{(b/a)\ln(n)+d}{(n+1)a}}\\ &= a+\frac{b}{(n+1)a}\frac1{1+\frac{b\ln(n)+da}{(n+1)a^2}}\\ &> a+\frac{b}{(n+1)a}(1-\frac{b\ln(n)+da}{(n+1)a^2}) \quad\text{since }\frac1{1+x} > 1-x\\ &= a+\frac{b}{(n+1)a}-\frac{b(b\ln(n)+da)}{(n+1)^2a^3}\\ \end{array} $

Since $\sum \frac{\ln(n)}{n^2}$ converges, summing this gives $y_n \gt na+\frac{b}{a}\ln(n) + C$ for come constant $C$.

More effort might yield $\lim_{n \to \infty} y_n- na-\frac{b}{a}\ln(n) $ existing (and it probably does), but I'll stop here.

Note: This is a fairly standard upper-lower bound technique for getting asymptotics.

  • 1
    $\begingroup$ Thank you so much for this nice write-up. I really appreciate it. $\endgroup$ – Alex Sep 13 '18 at 19:40

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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