Find the limit of a recurrence relation

Question

For given a sequence $\{b_k\}_{k\ge1}$, consider the following recurrence relation: $$ \begin{cases} u_0=1,\\ u_n=1-\sum_{j=0}^{n-1}u_jb_{n-j},\;n=1,2,\dots \end{cases} $$ It is known that $0<b_k<1$ for all $k$, and I would like to study $\lim_{n\to\infty}u_n$. After some calculations, I feel that $$ \lim_{n\to\infty}u_n=\left(1+\sum_{j=1}^{\infty}b_{j}\right)^{-1}. $$ But, I don't know how to get a closed form of $u_n$ so as to prove the existence of the limit, or get the limit. Is there any method to study the asymptotic behavior of a recurrence relation? Please give me some help. Thanks a lot.

Answer 1

Let $b_0=1$, and consider $B(z)=\sum_{n=0}^{\infty}b_n z^n$ and $U(z)=\sum_{n=0}^{\infty}u_n z^n$ in the formal sense. The recurrence, written as $\sum_{j=0}^{n}u_j b_{n-j}=1$, holds for all $n\geqslant 0$ and implies $B(z)U(z)=(1-z)^{-1}$. Now $B(z)$ can be thought of as a function of $z\in\mathbb{C}$ regular in $|z|<1$ (at least). Thus, $U(z)$ is analytic (its series converges) at least in $|z|<\min\{1,r\}$, where $r=\inf\{|z| : B(z)=0\}$ (if $B(z)\neq 0$ for all $z\in\mathbb{C}$ such that $B(z)$ converges, we take $r$ to be the radius of convergence).

In particular, if $\color{blue}{r>1}$, then the function $$\sum_{n=0}^{\infty}\big(u_n-1/B(1)\big)z^n=\frac{1}{1-z}\left(\frac{1}{B(z)}-\frac{1}{B(1)}\right)$$ is analytic in $|z|<r$; thus, the series is convergent at $z=1$, and your claim $\lim\limits_{n\to\infty}u_n=1/B(1)$ holds.

But $r>1$ may well fail to hold. Let $b_{2n}=a^n$ and $b_{2n+1}=b^n$, where $0<a,b<1$. Then $$B(z)=\frac{1}{1-az^2}+\frac{z}{1-bz^2},$$ and we choose $a$ and $b$ so that $B(-r)=0$ for some $r<1$ (this can be done if $r>(\sqrt{5}-1)/2$; say, for $r=2/3$ we can take $a=1/8$ and $b=5/6$). Then $U(z)$ has a pole at $z=-r$, and $|u_n|$ grows like $r^{-n}$. The same applies to $r=1$; we can take $a=b=1/2$ and get $u_n=(-1)^n/2$ for $n>1$.

Still, an interesting question (that I would ask separately) is: what happens if $B(z)$ is analytic and $\neq 0$ in some open set containing $\{z\in\mathbb{C} : |z|\leqslant 1,\ z\neq 1\}$? I could not build a counterexample, but I'm not sure the claim always holds in this case.