Bounding the $n$'th term of a sequence given a recursive, non-linear bound.

Question

Let $a,b\in\mathbb{R}^+$. Suppose that $\{x_n\}_{n=0}^\infty$ is a sequence satisfying $$|x_n|\leq a|x_{n-1}|+b|x_{n-1}|^2, $$ for all $n\in\mathbb{N}$. How can we bound $|x_n|$ with a number $M_n$ depending on $n$, $a$, $b$, and $x_0$?

That $|x_{n-1}|^2$ term is rather cumbersome to handle. Is there a combinatorial trick to overcome messy computations?

---

To make the problem a bit easier, I am going to assume that $$x_n=ax_{n-1}+bx_{n-1}^2.$$ This implies the above inequality. Based on the answer of this question, we can reduce the problem to $$\hat x_n=\hat x_{n-1}^2+c,$$ where $\hat x$ is some linear image of $x_n$ and $c$ is a constant depending on $a$ and $b$. Maybe this is easier to bound $\hat x_n$.

Answer 1

Here is a way to bound the $x_n$ for the sequence $x_n = a x_{n-1}+bx_{n-1}^2$, assuming $x_n \ge 0$ for all $n$ (which is the case if $x_0 \ge 0$). It's a very rapidly growing bound, but I think any bound will have to be.

By replacing $x_{n-1}$ with $\max(x_{n-1},1)$, we may assume $x_{n-1} \le x_{n-1}^2$ so it is sufficient to bound $x_n = (a+b) x_{n-1}^2$. Let $y_n := \ln(x_n)$ so $y_n = \ln (a+b) + 2 y_{n-1}.$ This is a standard linear recurrence, and is solved with $y_n = 2^n - \ln (a+b)$. This implies $x_n = \exp(2^n - \ln (a+b)) = \frac 1{a+b} e^{2^n}$. Hence the bound you want is $$x_n \le \max\left(\frac {e^{2^n}}{a+b},1\right).$$

Answer 2

Let us define the sequence $y_n$ by $y_0=|x_0|$, $y_{n+1}=ay_n+by_n^2$. Then we have $|x_n|\leq y_n$ for all $n$, since $ay+by^2$ is increasing for positive $a,b$, and it is enough to estimate the positive sequence $y_n$. Setting $z_n=by_n$, we obtain a simpler recurrent relation $z_{n+1}=az_n+z_n^2.$ For this last relation, the behavior depends on $a$. If $a\geq 1$, all orbits tend to $+\infty$ and $z_n\sim \exp(2^nu(a,z_0))$ where $u$ is a positive function. If $a<1$, then there is a positive fixed point $z^*=1-a$. When $z_0>z^*$ the behavior is as above, when $z_0<z^*$, the orbit tends to $0$ as the geometric progression: $z_n\sim a^n$, and when $z_0=z^*$ then $z_n=z^*$.

For the function $u(a,z)$, there is no explicit expression, it is variously known as the Green function of the complement of the Julia set, or the equilibrium potential of the Julia set. This function is actually easy to compute by the formula $$u(a,z)=\lim_{n\to\infty}2^{-n}\log|f^n(z)|,$$ where $f^n$ is the $n$-th iteration of the function $f^1(z)=az+z^2.$ This expression converges very fast.