Growth rate from nonlinear recurrence

Question

I am working with the following recurrence relation $$z_nx_{n-1} - z_{n-1}x_{n} = w_ny_{n-1} + w_{n-1}y_n$$ where $w,x,y$ are all non-decreasing, positive integer-valued sequences. I'd like to show that if $w\sim n^a,\, x\sim n^b,\, y\sim n^c$ (here I mean $f\sim g$ iff $\frac{f}{g}\rightarrow k$ for some nonzero constant $k$), then $z\sim n^{a + c - b + 1}$. Is there a way to isolate $z_n - z_{n-1}$ from the left hand side of the recurrence, perhaps by using some asymptotic assumptions on $w,x,y$ as above? Thanks in advance for your help.

Answer 1

Your conjectures are partially true and partially not.

For each $n$ put $y’_n=y_n/x_n$, $z’_n=z_n/x_n$, and $w’_n=w_n/x_n$.

Dividing both parts of the recurrence relation by $x_{n-1}x_n$, we obtain

$$z’_n – z’_{n-1}= w’_ny’_{n-1} + w’_{n-1}y’_n.\tag{1}\label{1}$$

Assume that there exist non-zero limits $k_w=\lim_{n\to\infty} w_n/n^a$, $k_x=\lim_{n\to\infty} x_n/n^b$, and $k_y=\lim_{n\to\infty} y_n/n^c$.

Multiplying both parts of Equality \eqref{1} by $n^{2b-a-c}$ and next taking the limit, we obtain that $$\lim_{n\to\infty} (z’_n-z’_{n-1})n^{2b-a-c}=2k_wk_yk_x^{-2}=l\ne 0.$$

Assume first that $a+c-2b+1=0$. Then $\lim_{n\to\infty}(z’_n-z’_{n-1})n=l$. Since

$$\lim_{n\to\infty} (\ln n-\ln (n-1))n =1,$$

$$\lim_{n\to\infty}\frac{z’_n-z’_{n-1}}{\ln n-\ln (n-1)}=l.\tag{2}\label{2}$$

Since a sequence $\{\ln n\}$ is strictly increasing and tends to infinity, by Equlaity \eqref{2} and Stolz-Cesàro theorem

$$\lim_{n\to\infty} \frac{z’_n}{\ln n}=l.$$

Then

$$\lim_{n\to\infty}\frac{z_n}{n^{a+c-b+1}\ln n }=$$ $$\lim_{n\to\infty} \frac{z’_nx_n}{n^{a+c-b+1}\ln n }=$$ $$\lim_{n\to\infty} \frac{z’_n}{n^{a+c-2b+1}\ln n}\frac{ x_n}{n^b}=$$ $$\lim_{n\to\infty} \frac{z’_n}{\ln n}\frac{x_n}{n^b}=lk_x\ne 0,$$ so $z\sim n^{a + c - b + 1}\ln n$.

Now assume that $a+c-2b+1\ne 0$. Since

$$\lim_{n\to\infty} \frac{n^{a+c-2b}}{n^{a+c-2b+1}-(n-1)^{a+c-2b+1}}=\frac{1}{2b-a-c+1}, $$

$$\lim_{n\to\infty} \frac{z’_n-z’_{n-1}}{n^{a+c-2b+1}-(n-1)^{a+c-2b+1}}=\frac{2k_wk_y}{k_x^{2}(2b-a-c+1)}=l.\tag{3}\label{3}$$

If $a+c-2b+1>0$ then a sequence $\{n^{a+c-2b+1}\}$ is strictly increasing and tends to infinity, so by Equality \eqref{3} and Stolz-Cesàro theorem

$$\lim_{n\to\infty} \frac{z’_n}{n^{a+c-2b+1}}=l.$$

Then

$$\lim_{n\to\infty}\frac{z_n}{n^{a+c-b+1}}=$$ $$\lim_{n\to\infty} \frac{z’_nx_n}{n^{a+c-b+1}}=$$ $$\lim_{n\to\infty} \frac{z’_n}{n^{a+c-2b+1}}\frac{ x_n}{n^b}=$$ $$\lim_{n\to\infty} z’_n\frac{x_n}{n^b}=lk_x\ne 0,$$ so $z\sim n^{a + c - b + 1}$.

If $a+c-2b+1<0$ then the sequence $\{z_n\}$ can grow faster than $n^{a + c - b + 1}$. For instance, put $w_n=y_n=1$ and $x_n=n$ for each $n$. Then $a=0$, $c=0$, $b=1$, but for any real $\alpha$ a sequence $\{z_n\}\equiv \{\alpha n-2\}$ satisfies the recurrence relation.