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.
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$