Convergence (rate) of a three term recurrence Suppose we have following recurrence relation for a positive real sequence $\{a_n\}$
\begin{align*}
a_{n+1} \le \left(q+\frac {c_1} {n+1}\right) a_n + \frac{c_2}{n} a_{n-1},
\end{align*}
where $c_1$ and $c_2$ are some positive constants and $0 < q < 1$. Will the sequence $\{a_n\}_{n=1}^{\infty}$ stay bounded (or better, converging to $0$)?
My intuition is: since there are only finitely many $n$ with $q+c_1/(n+1) > 1$, eventually the sequence will decrease and so converge to $0$. But I haven't come up a rigorous proof. I did some simulation by making the inequality to be equality, it seems like the sequence converges to $0$ even with $q=0.999$.

UPDATE:
Thanks to @Michael. I got one solution which is based on the observation pointed out by @Michael. He also gave another way to proceed based on this observation (see his answer.)
We observe for every $1 > r >0$, for sufficiently large $n$, the recurrence is equivalent to
\begin{align*}
a_{n+1} \le \frac{1+q}{2} a_n + r a_{n-1}.
\end{align*}
Without loss of generality, we may assume for all $n$, above relation holds. Now if we can find some parameters $0<q'<1$ and $c >0$ such that
\begin{align*}
a_{n+1} + c a_n \le q'(a_n + c a_{n-1}),
\end{align*}
it is clear $a_n \to 0$ since the sequence is positive. One choice is putting $q' = \frac{3+q} 4$ and $c=\frac{1-q} 4$. In this case, we can take $r = \frac{(1-q)(3+q)} {16}$.

The remaining question is whether it is possible to estimate the rate of convergence. Any comments are welcome. Thanks.

UPDATE on convergence rate:
@Michael pointed out some convergence rate when $c_1, c_2$ are sufficiently small. I think if using my method, we could give a convergence rate related to $\varepsilon > 0$.
For any $1-q>\varepsilon >0$, there exists $N$ such that $n \ge N$, 
\begin{align*}
a_{n+1} + c a_n \le (q+ \varepsilon) (a_n + c a_{n-1}).
\end{align*}
Let $N'$ be the smallest integer such that $c_1/N' \le \varepsilon$ and $M = \max_{j \le N'} (a_j + c a_{j-1})$.
Then $a_{n+1} \le a_{n+1} + ca_n \le (q+\varepsilon)^{n-N'} M$. Looks like some pseudo linear rate. 
Could we do better? Any comments will be helpful. Thanks.
 A: Suppose there is an integer $M>0$, constants $\alpha \geq 0, \beta \geq 0$ that satisfy $\alpha + \beta < 1$, and a nonnegative sequence $\{a_n\}_{n=1}^{\infty}$ such that 
$$  a_{n+1} \leq \alpha a_n + \beta a_{n-1} \quad, \forall n \geq M $$
Then $a_n \rightarrow 0$. 
Proof step 1: Define $\rho = \alpha + \beta$ and note that $0 \leq \rho < 1$. Then for all $n \geq M$ show that 
$$ a_{n+1} \leq \rho \max[a_n, a_{n-1}]$$
Proof step 2: Show that for all $n \geq M$:
$$ a_{n+2} \leq \rho \max[a_n, a_{n-1}]$$
Thus 
$$ \max[a_{n+2}, a_{n+1}] \leq \rho \max[a_n, a_{n-1}] \quad, \forall n \geq M$$
$\Box$

Here is a proof that $a_n \leq A(n+1) q^n$ for all $n \in\{1, 2, 3, ...\}$ whenever it holds for $a_1$ and $a_2$, and when $c_1, c_2$ are sufficiently small to ensure $c_1/q + c_2/q^2 \leq 1$. 
Claim: Let $q,c_1,c_2, A$ be positive constants. Suppose $c_1/q + c_2/q^2 \leq 1$.  If $\{a_n\}_{n=1}^{\infty}$ is a sequence of nonnegative numbers such that 
$$a_{n+1} \leq (q + c_1/(n+1))a_n + (c_2/n)a_{n-1} \quad, \forall n \in\{2, 3, 4, ...\} \quad \mbox{(Eq. *)}$$ 
and if $a_i \leq A(i+1)q^i$ for $i \in\{1, 2, ..., m\}$ (for some integer $m\geq 2$), then it also holds for $i=m+1$, that is, $a_{m+1} \leq A(m+2)q^{m+1}$.
Proof:
\begin{align}
a_{m+1} &\leq (q + c_1/(m+1))a_m + (c_2/m)a_{m-1}\\
&\leq (q + c_1/(m+1))A(m+1)q^m + (c_2/m)Amq^{m-1}\\
&=A(m+2)q^{m+1}\underbrace{\left[\frac{(m+1) + c_1/q + c_2/q^2}{m+2}\right]}_{\leq 1} \\
&\leq A(m+2)q^{m+1}
\end{align}
$\Box$

For $q>0$ and general $c_1, c_2 \geq 0$, define 
$$ b = \max\left[1, \frac{c_1}{q} + \frac{c_2}{q^2}\right]$$
Assume $\{a_n\}$ satisfies (Eq *). 
Define $A\geq 0$ large enough so that $a_1 \leq A (1+1)^bq$ and $a_2 \leq A(2+1)^bq^2$. 
Claim:  $a_n \leq A(n+1)^b q^n$ for all $n \in \{1, 2, 3, ...\}$.
Proof: It holds by assumption for $n=1, n=2$.  Suppose it holds for an integer $n\geq 2$.  We show it also holds for $n+1$. 
\begin{align}
a_{n+1} &\overset{(a)}{\leq} (q + c_1/(n+1))a_n + (c_2/n)a_{n-1} \\
&\overset{(b)}{\leq} (q + c_1/(n+1))A(n+1)^bq^n + (c_2/n)An^bq^{n-1}\\
&= A(n+1)^bq^{n+1} + Ac_1(n+1)^{b-1} q^n + Ac_2n^{b-1}q^{n-1}\\
&= Aq^{n+1}\left[(n+1)^b + \frac{c_1}{q}(n+1)^{b-1} + \frac{c_2}{q^2}n^{b-1}\right]\\
&\leq  Aq^{n+1}\left[(n+1)^b + \left(\frac{c_1}{q} + \frac{c_2}{q^2}\right)(n+1)^{b-1}\right]\\
&\overset{(c)}{\leq} Aq^{n+1}\left[(n+1)^b + b(n+1)^{b-1}\right]\\
&\overset{(d)}\leq Aq^{n+1}(n+2)^b
\end{align}
where (a) holds by (Eq. *); (b) holds by the induction hypothesis; (c) holds by definition of $b$; (d) holds by convexity of the function $f(x)=(n+1+x)^b$ for $x\geq 0$, so that 
$$ \underbrace{f(1)}_{(n+2)^b} \geq \underbrace{f(0) + f'(0)(1-0)}_{(n+1)^b + b(n+1)^{b-1}} $$
$\Box$
