Non linear recursion of the form $a_{n+1} \leq b_{n} \cdot a_{n} + c_{n}$ During my research I encountered the need to solve a non linear recursion of the form 
$$a_{n+1} \leq b_{n} \cdot a_{n} + c_{n}$$
Where $b_n$ and $c_n$ are known. More specifically, I'm interested not in $a_n$ itself but in a bound for $a_n$, i.e., I need to find $M_n$ so that $|a_n| \leq M_n$.
I have tried to bound $|b_n| \leq b$ and $|c_n| \leq c$ and solve $a_{n+1} \leq b \cdot a_{n} + c$ but the results are not good enough.
Is there a way to solve such recursions? Would it help to assume that $b_n \rightarrow b$ and $c_n \rightarrow c$?
 A: Let's consider first of all the recurrence with the equal sign
$$
x_{\,n + 1}  = b_{\,n} \,x_{\,n}  + c_{\,n} 
$$
then we have
$$
\eqalign{
  & x_{\,n + 1}  = b_{\,n} \,x_{\,n}  + c_{\,n}  = b_{\,n} \,b_{\,n - 1} x_{\,n - 1}  + \left( {c_{\,n}  + b_{\,n - 1} c_{\,n - 1} } \right) =  \cdots  =   \cr 
  &  = \left( {\prod\limits_{0\, \le \,j\, \le \,n} {b_{\,j} } } \right)x_{\,0}  + \left( {\sum\limits_{0\, \le \,k\, \le \,n} {c_{\,k} \prod\limits_{k + 1\, \le \,j\, \le \,n} {b_{\,j} } } } \right) =   \cr 
  &  = \left( {\prod\limits_{0\, \le \,j\, \le \,n} {b_{\,j} } } \right)x_{\,0}  + \prod\limits_{0\, \le \,j\, \le \,n} {b_{\,j} } \left( {\sum\limits_{0\, \le \,k\, \le \,n} {{{c_{\,k} } \over {\prod\limits_{0\, \le \,j\, \le \,k} {b_{\,j} } }}} } \right) =   \cr 
  &  = x_{\,0} \left( {\prod\limits_{0\, \le \,j\, \le \,n} {b_{\,j} } } \right)\left( {1 + \sum\limits_{0\, \le \,k\, \le \,n} {{{c_{\,k} /x_{\,0} } \over {\prod\limits_{0\, \le \,j\, \le \,k} {b_{\,j} } }}} } \right) = f(n) \cr} 
$$
So are clear the conditions that the coefficients $b$ and $c$ should respect
for $x(n)$ to converge, and what is the influence of the starting point $x(0)$.
If you can express $b$ and $c$ as a function of their index, you might
be able and get a closed form for $f(n)$.
Now the original disequality can be expressed in multiplicative way 
or in a subtractive way
$$
\eqalign{
  & a_{\,n + 1}  \le x_{\,n + 1}  = \beta _{\,n + 1} \,x_{\,n + 1}  = \beta _{\,n + 1} b_{\,n} \,x_{\,n}  + \beta _{\,n + 1} c_{\,n} \quad \left| {\;\beta _{\,n + 1}  \le 1\left( {{\rm if}\;0 \le x_{\,n + 1} } \right)} \right.  \cr 
  & a_{\,n + 1}  \le x_{\,n + 1}  = \,x_{\,n + 1}  - \gamma _{\,n + 1}  = b_{\,n} \,x_{\,n}  + \left( {c_{\,n}  - \gamma _{\,n + 1} } \right)\quad \left| {\;0 \le \gamma _{\,n + 1} } \right. \cr} 
$$
and then you can evaluate the effect of the modified $b$'s and $c$'s on the above
formula.
To evaluate the starting of the sequence, and possibly also to grasp the convergence of it, 
it will be useful to graph some of the first lines $y_n(x)=b_nx+c_n$, together with the line 
$y=x$, and trace there the first steps. 
We take an example to illustrate the procedure: let's put
$$
b_{\,n}  = \left( {n + 1} \right)/\left( {n + 3} \right)\quad c_{\,n}  = 10/\left( {n + 1} \right)
$$
which gives
$$
b_{\,\infty }  = 1_{\, - } \quad c_{\,\infty }  = 0_{\, + } 
$$
and
$$
\prod\limits_{0\, \le \,j\, \le \,n} {b_{\,j} }  = {{2\left( {n + 1} \right)!} \over {\left( {n + 3} \right)!}} = {2 \over {\left( {n + 3} \right)^{\,\underline {\,2\,} } }} = {2 \over {\left( {n + 3} \right)\left( {n + 2} \right)}}
$$
$$
\eqalign{
  & \sum\limits_{0\, \le \,k\, \le \,n} {{{c_{\,k} } \over {\prod\limits_{0\, \le \,j\, \le \,k} {b_{\,j} } }}}  = 5\sum\limits_{0\, \le \,k\, \le \,n} {{{\left( {k + 3} \right)\left( {k + 2} \right)} \over {\left( {k + 1} \right)}}}  =   \cr 
  &  = 5\sum\limits_{0\, \le \,k\, \le \,n} {k + 4 + {2 \over {\left( {k + 1} \right)}}}  = 5\left( {{{n\left( {n + 1} \right)} \over 2} + 4\left( {n + 1} \right) + 2H(n + 1)} \right) \cr} 
$$
Therefore for $f(n)$ we obtain
$$
f(n) = {1 \over {\left( {n + 3} \right)\left( {n + 2} \right)}}\left( {5\left( {n + 8} \right)\left( {n + 1} \right) + 20H(n + 1) + 2\,x_{\,0} } \right)
$$
which in the limit gives
$$
f(\infty ) = 5
$$
The sequence evolves as shown in this graph

At this point we can see that, taking the recurrence with the disequality
is equivalent to shift or rotate   to the left the line $y(x)$, and the graph helps to visualize
what that would mean.
