Solving the recurrence relation $y_{n+1}=y_n+a+\frac{b}{y_n}$

Question

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

$$y_{n+1}=y_n+a+\frac{b}{y_n}$$

Any help would be very much appreciated!

Answer 1

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.

Answer 2

Set $y_n = P_n(y,1)/Q_n(y,1)$ with: $$P_0(y,z) = y,\quad Q_0(y,z) = z.$$ Then $$ P_{n+1}(y,z) = {P_n(y,z)}^2 + a P_n(y,z)Q_n(y,z) + b {Q_n(y,z)}^2,\\ Q_{n+1}(y,z) = P_n(y,z)Q_n(y,z) $$ provides a generalization of, and replacement for, the original recurrence relation. Note the property: $$P_{n+k}(y,z) = P_k\left(P_n(y,z),Q_n(y,z)\right), \quad Q_{n+k} = Q_k\left(P_n(y,z),Q_n(y,z)\right),$$ and also: $$Q_n(y,z) = P_{n-1}(y,z) ⋯ P_1(y,z) P_0(y,z) z\quad (n>0).$$ Thus, $$y_n = \frac{P_n(y,1)}{P_{n-1}(y,1) ⋯ P_1(y,1) P_0(y,1)}\quad (n>0).$$

These are all homogeneous polynomials of degrees $\text{deg}(P_n) = 2^n = \text{deg}(Q_n)$. The lowest orders are: $$ P_0(y,z) = y,\\ P_1(y,z) = y^2 + ayz + bz^2,\\ P_2(y,z) = y^4 + 3ay^3z + \left(2a^2+3b\right)y^2z^2 + 3abyz^3 + b^2z^4. $$ and $$ Q_0(y,z) = z,\\ Q_1(y,z) = yz,\\ Q_2(y,z) = (y^2 + ayz + bz^2)yz. $$

Note also the properties $$P_n(ky,kz) = k^{2^n} P_n(y,z), \quad Q_n(ky,kz) = k^{2^n} Q_n(y,z),$$ follow from homogeneity so that $$P_n(y,z) = z^{2^n} P_n\left(\frac{y}{z},1\right), \quad Q_n(y,z) = z^{2^n} Q_n\left(\frac{y}{z},1\right)\quad (z ≠ 0),$$ while $$P_n(y,0) = y^{2^n},\quad Q_n(y,0) = 0.$$

For the rational function, there is the following normalization $$\frac{P_n(y,z)}{Q_n(y,z)} = \frac{P_n(y/z,1)}{Q_n(y/z,1)}\quad (z ≠ 0),$$ and the following reduction to a polynomial + proper rational function: $$\frac{P_n(y,1)}{Q_n(y,1)} = y + na + b\frac{R_n(y,1)}{Q_n(y,1)},\quad \text{deg}_y\left(R_n(y,1)\right) < \text{deg}_y\left(Q_n(y,1)\right).$$ This can be expanded as a series in $1/y$: $$\frac{P_n(y,1)}{Q_n(y,1)} = y + na - \frac{n(n-1)}{2}\frac{ab}{y} + \frac{n(n-1)}{6}\frac{ab}{y}\frac{(2n-1)a+(n-2)b}{y} + ⋯.$$ You can cut the series off at any finite order by writing the remainder term in the form ${R_n}'(y,1)/Q_n(y,1)$ for a suitably-defined polynomial ${R_n}'(y,z)$.

There is no magic that I can see that will reduce this to anything simpler. You'll just have to take these primitives as things in their own right, and make a whole new subject out of them.